Cod sursa(job #1219164)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 13 august 2014 16:35:02
Problema Teren Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
#define MAXN 300

int D[MAXN][MAXN];

int main () {
    FILE *f, *g;
    f = fopen( "teren.in", "r" );
    g = fopen("teren.out", "w");

    int n, m, x;

    fscanf(f, "%d%d%d", &n, &m, &x);

    for (int i = 0 ; i < n ; ++i)
        for (int j = 0 ; j < m ; ++j)
            fscanf(f, "%d", &D[i][j]);

    for(int j = 0 ; j < m ; ++j)
        for(int i = 1 ; i < n ; ++i)
            D[i][j] += D[i-1][j];

    int maxar = -1;

    for(int b = 0 ; b < n ; ++b)
        for(int h = 1 ; b - h + 1 >= 0 ; ++h) {
            int s = 0, start = 0;
            for( int c = 0 ; c < m ; ++c ) {
                s += D[b][c];
                if( b - h + 1 > 0 )
                    s -= D[b - h][c];

                while( s > x ) {
                    int k = D[b][start];
                    if( b - h + 1 > 0 )
                        k -= D[b - h][start];

                    ++start;
                    s -= k;
                }

                if( start <= c && maxar < ( c - start + 1 ) * h )
                    maxar = ( c - start + 1 ) * h;
            }
        }

    fprintf(g, "%d\n", maxar);

    fclose(f);
    fclose(g);
    return 0;
}