Cod sursa(job #1364955)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 27 februarie 2015 22:04:26
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <cstdio>
#define DIM 256
#define INF 2000000000
using namespace std;

FILE *fin = fopen("bmatrix.in" ,"r");
FILE *fout= fopen("bmatrix.out","w");

int D[DIM][DIM]; char S[DIM];
int best[5][DIM],A[DIM][DIM];
int E[3][DIM], d, maxim, aux;
int N, M, i, j, k;

void SetUp(){
     fscanf(fin, "%d%d", &N, &M);
     for(i = 1; i <= N; i ++){
          fscanf(fin, "%s", &S);
          for(j = 0; j < M; j ++)
               A[i][j+1] = S[j] - '0';
     }
     return;
}

void Rotate_Matrix(){
     for(i = 1; i <= N; i ++)
          for(j = 1; j <= M; j ++){
               aux = A[i][j];
               A[i][j] = A[j][N-i];
               A[j][N-i] = aux;
          }
     return;
}

void Partial(){
     for(i = 1; i <= N; i ++)
          for(j = 1; j <= M; j ++)
               if(A[i][j] == 0)
                    D[i][j] = D[i-1][j] + 1;
               else
                    D[i][j] = 0;
     return;
}

void BMatrix(){
     E[1][0] = 1;
     for(d = 1; d <= 4; d ++){
          Partial();
          for(i = 1; i <= N; i ++){
               maxim = 0; k = 0;
               for(j = 1; j <= M + 1; j ++){
                    if(D[i][j] >= E[1][k]){
                         k ++;
                         E[1][k] = D[i][j];
                         E[2][k] = j;
                    }
                    else{
                         while(D[i][j] <= E[1][k] && k != 0){
                              if(maxim < E[1][k] * (j - E[2][k]))
                                   maxim = E[1][k] * (j - E[2][k]);
                              k --;
                         }
                         if(D[i][j] != 0){
                              k ++;
                              E[1][k] = D[i][j];
                              E[2][k] = j;
                         }
                    }
               }
               best[d][i] = maxim;
          }
          Rotate_Matrix();
          aux = N; N = M; M = aux;
     }
     return;
}

void Finish(){
     maxim = 0;
     for(i = 1; i < N; i ++)
          if(maxim < best[1][i] + best[3][i+1])
               maxim = best[1][i] + best[3][i+1];
     for(j = 1; j < M; j ++)
          if(maxim < best[2][j] + best[4][j+1])
               maxim = best[2][j] + best[4][j+1];
     fprintf(fout, "%d", maxim);
     return;
}

int main(){
     SetUp();
     BMatrix();
     Finish();
     return 0;
}