Cod sursa(job #457307)

Utilizator vladiiIonescu Vlad vladii Data 18 mai 2010 20:56:00
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <iostream>
using namespace std;
#define maxn 210
#define inf 999999999

//M linii si N coloane
int M, N;
char A[maxn][maxn];
int sus[maxn][maxn], jos[maxn][maxn]; 
int linsus[maxn], linjos[maxn];
int st[maxn][maxn], dr[maxn][maxn];
int colst[maxn], coldr[maxn];

int main() {
    FILE *f1=fopen("bmatrix.in", "r"), *f2=fopen("bmatrix.out", "w");
    int i, j, p, q;
    fscanf(f1, "%d %d\n", &M, &N);
    for(i=1; i<=M; i++) {
         fscanf(f1, "%s\n", A[i] + 1);
    }
    for(i=1; i<=M; i++) {
         for(j=1; j<=N; j++) {
              if(A[i][j] == '0') sus[i][j] = sus[i-1][j] + 1;
         }
    }
    for(i=M; i>=1; i--) {
         for(j=1; j<=N; j++) {
              if(A[i][j] == '0') jos[i][j] = jos[i+1][j] + 1;
         }
    }
    for(i=1; i<=M; i++) {
         for(j=1; j<=N; j++) {
              if(A[i][j] == '0') st[i][j] = st[i][j-1] + 1;
         }
    }
    for(i=1; i<=M; i++) {
         for(j=N; j>=1; j--) {
              if(A[i][j] == '0') dr[i][j] = dr[i][j+1] + 1;
         }
    }
    for(i=1; i<=M; i++) {
         int asmax = 0, hsmax = inf;
         int ajmax = 0, hjmax = inf;
         for(j=1; j<=N; j++) {
              if(A[i][j] == '0') {
                   p = j; hsmax = inf; hjmax = inf;
                   while(p && A[i][p] == '0') {
                        hsmax = min(hsmax, sus[i][p]);
                        asmax = max(asmax, (j - p + 1)*hsmax);
                        hjmax = min(hjmax, jos[i][p]);
                        ajmax = max(ajmax, (j - p + 1)*hjmax);
                        p--;
                   }
              }
         }
         linsus[i] = asmax;
         linjos[i] = ajmax;
    }
    for(i=1; i<=N; i++) {
         int asmax = 0, hsmax = inf;
         int ajmax = 0, hjmax = inf;
         for(j=1; j<=M; j++) {
              if(A[j][i] == '0') {
                   p = j; hsmax = inf; hjmax = inf;
                   while(p && A[p][i] == '0') {
                        hsmax = min(hsmax, st[p][i]);
                        asmax = max(asmax, (j - p + 1)*hsmax);
                        hjmax = min(hjmax, dr[p][i]);
                        ajmax = max(ajmax, (j - p + 1)*hjmax);
                        p--;
                   }
              }
         }
         colst[i] = asmax;
         coldr[i] = ajmax;
    }
    int sol = 0;
    for(i=1; i<=M; i++) {
         for(j=i+1; j<=M; j++) {
              sol = max(sol, linsus[i] + linjos[j]);
         }
    }
    for(i=1; i<=N; i++) {
         for(j=i+1; j<=N; j++) {
              sol = max(sol, colst[i] + coldr[j]);
         }
    }
    fprintf(f2, "%d\n", sol);
    fclose(f1); fclose(f2);
    return 0;
}