Cod sursa(job #276698)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 11 martie 2009 12:15:17
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>
#define N 302

bool a[N][N];
int c[N][N], n, m, x, max;

void citire(), rezolva();


int main (){
    freopen("teren.in", "r", stdin);
    freopen("teren.out", "w", stdout);

    citire();
    rezolva();

    return 0;
}

void citire(){
int i, j;
    scanf("%d %d %d", &n, &m, &x);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            scanf("%d", &a[i][j]),
            c[i][j] = c[i-1][j] + a[i][j];
}

void rezolva(){
int i, j, k, nr, s, st, dr;
    for (i = 1; i < n; i++)
        for (j = i + 1; j <= n; j++){
            nr = 0; s = c[j][1] - c[i-1][1];
            for (st = 1, dr = 2; dr <= m; dr++){
                s += c[j][dr] - c[i-1][dr];
                while (s > x && st <= dr) s -= (c[j][st] - c[i-1][st++]);
                if ((dr - st + 1) * (j - i + 1) > max) max = ( dr - st + 1 ) * (j - i + 1);
            }
        }
    printf("%d\n", max);
}