Cod sursa(job #458714)

Utilizator vladiiIonescu Vlad vladii Data 25 mai 2010 21:52:00
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <iostream>
using namespace std;
#define maxn 310

int N, M, X, sol;
short sus[maxn][maxn];
bool A[maxn][maxn];

int main() {
    FILE *f1=fopen("teren.in", "r"), *f2=fopen("teren.out", "w");
    int i, j, p, q;
    fscanf(f1, "%d %d %d\n", &N, &M, &X);
    for(i=1; i<=N; i++) {
         for(j=1; j<=M; j++) {
              fscanf(f1, "%d", &A[i][j]);
         }
    }
    for(i=1; i<=N; i++) {
         for(j=1; j<=M; j++) {
              if(A[i][j] == 1) {
                   sus[i][j] = sus[i-1][j] + 1;
              }
              else {
                   sus[i][j] = sus[i-1][j];
              }
         }
    }
    for(i=1; i<N; i++) {
         for(j=i+1; j<=N; j++) {
              //fixez linia i (de sus) si linia j (de jos)
              int sum = 0, last = 1;
              sum = sus[j][1] - sus[i-1][1];
              if(sum <= X) sol = max(sol, (j - i + 1));
              else { sum = 0; last = 2; }
              for(p=2; p<=M; p++) {
                   sum += (sus[j][p] - sus[i-1][p]);
                   if(sum <= X) sol = max(sol, (j - i + 1)*(p - last + 1));
                   else {
                        while(sum > X) {
                             sum -= (sus[j][last] - sus[i-1][last]);
                             last++;
                        }
                   }
              }
         }
    }
    fprintf(f2, "%d\n", sol);
    fclose(f1); fclose(f2);
    return 0;
}