Cod sursa(job #2055079)

Utilizator ptudortudor P ptudor Data 2 noiembrie 2017 20:16:42
Problema Teren Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<iostream>
#include<fstream>
#include <queue>
using namespace std;
int main()
{
    ifstream in("teren.in");
    ofstream out("teren.out");
    int n,m,z;
    in>>n>>m>>z;
    int i,j,k;
    int v[301][301];
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
            in>>v[i][j];
    }
    for (j=1;j<=m;j++)
        for (i=1;i<=n;i++)
        v[i][j]=v[i-1][j]+v[i][j];

   int M=0;
   int s,x;
   int st=0;
   queue <int> q;
   for (i=1;i<=n;i++)
   {
       for (j=i;j<=n;j++)
       {
           while (!(q.empty()))
           {
            q.pop();
           }
           s=0;
           st=1;
           for (k=1;k<=m;k++)
           {
               x=v[j][k]-v[i-1][k];
               s=s+x;
               q.push(x);
               while (s>z)
               {
                   s=s-q.front();
                   q.pop();
                   st++;
               }
               if ((j-i+1)*(k-st+1)>M)
                M=(j-i+1)*(k-st+1);
           }
       }
   }
   out<<M;
   out.close();
   in.close();
   return 0;
}