Cod sursa(job #1415103)

Utilizator klbraduRadu Capalb klbradu Data 3 aprilie 2015 19:29:09
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
using namespace std;
int n, m, x, C[302][302], is, ij, j, sum, maxim, p, t;
char A[302][302];
ifstream fin("teren.in");
ofstream fout("teren.out");

int main(){
    fin>>n>>m>>x;
    for(int i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            fin>>t;
            A[i][j] = t;
            C[i][j] = C[i-1][j] + A[i][j];
        }
    }

    for (is = 1; is <=n; is++)
        for (ij = is; ij <=n; ij++) {
            // caut dreptunghiuri convenabile cu linia de sus fixata pe is si cea de jos fixata pe ij
            sum = 0;
            p = 1;
            for (j=1;j<=m;j++) {
                sum += (C[ij][j] - C[is-1][j]);
                while (sum > x) {
                    sum -= (C[ij][p] - C[is-1][p]);
                    p++;
                }

                if (p <= j && (ij - is + 1) * (j-p+1) > maxim)
                    maxim = (ij - is + 1) * (j-p+1);
            }
        }
    fout<<maxim;
}