Cod sursa(job #110698)

Utilizator DastasIonescu Vlad Dastas Data 27 noiembrie 2007 15:29:49
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>

const int maxn = 302;

FILE *in = fopen("teren.in","r"), *out = fopen("teren.out","w");

int n, m, x;
int a[maxn][maxn];
int s[maxn][maxn];

int t[maxn];

int maxx = 0;

void read()
{
    fscanf(in, "%d %d %d", &n, &m, &x);

    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
            fscanf(in, "%d", &a[i][j]);

    for ( int i = 1; i <= m; ++i )
        s[1][i] = a[1][i];

    for ( int i = 2; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
            s[i][j] = s[i-1][j] + a[i][j];
}

int main()
{
    read();

    for ( int i = 1; i <= n; ++i )
        for ( int j = i; j <= n; ++j )
        {
            for ( int p = 1; p <= m; ++p )
                t[p] = s[j][p] - s[i-1][p];

//            printf("%d %d: ", i, j);
//            for ( int p = 1; p <= m; ++p )
//                printf("%d ", t[p]);
//            printf("\n");

            int st = 1;
            int sum = 0;
            for ( int dr = 1; dr <= m; ++dr )
            {
                sum += t[dr];
                while ( st <= dr && sum > x )
                {
                    sum -= t[st];
                    ++st;
                }

                if ( st <= dr )
                    if ( (j-i+1)*(dr-st+1) > maxx )
                        maxx = (j-i+1)*(dr-st+1);
            }
        }

    fprintf(out, "%d\n", maxx);

	return 0;
}