Cod sursa(job #2087567)

Utilizator cameleonGeorgescu Dan cameleon Data 13 decembrie 2017 20:36:15
Problema Teren Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<fstream>
using namespace std;
#define NMAX 305

ifstream fin("teren.in");
ofstream fout("teren.out");

int a[NMAX][NMAX], n, m, k, Amax;

int main()
{
    int i, j, i1, i2, j1, j2, x, s;
    fin >> n >> m >> k;
    for(i = 1;i <= n; ++i)
        for(j = 1; j <= m; ++j)
        {
            fin >> a[i][j];
            a[i][j] += a[i-1][j];
        }
    for( i1 = 1; i1 <= n; ++i1)
        for( i2 = i1; i2 <= n; ++i2)
        {
            s = 0; j1 = 1;
            for(j2 = 1; j2 <= m; ++j2){
                x=a[i2][j2]-a[i1-1][j2];
                while(j1 < j2 && s+x > k)
                {
                    s -= (a[i2][j1] - a[i1-1][j1]);
                    j1++;
                }
                if(s+x <= k)
                    s += x;
                else
                {
                    s = x;
                    j1 = j2;
                }

                Amax = max(Amax,(i2-i1+1)*(j2-j1+1));
            }

        }
        fout << Amax;
}