Cod sursa(job #1826106)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 10 decembrie 2016 10:00:59
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream in ("bmatrix.in");
ofstream out ("bmatrix.out");
int const NMAX = 201;
int matrix[NMAX][NMAX] , cangoup[NMAX];
int n,m,bestl1[NMAX] ,bestl2[NMAX] ,bestc1[NMAX] ,bestc2[NMAX] , minim;

int main(){
  in>>n>>m;
  char c = 0;
  for(register int i = 0 ;i < n ;i++){
    for(register int j = 0 ;j < m ;j++){
      in>>c;
      matrix[i][j] = c - '0';
    }
  }

  for(register int i = 0 ; i < n;i++){
    for(register int j = 0 ; j < m;j++){
      if(!matrix[i][j])
        cangoup[j]++;
      else
        cangoup[j] = 0;
      minim = NMAX;
      for(register int h = 1 ; j - h + 1 >= 0; h++){
        if(minim > cangoup[j-h+1]){
          minim = cangoup[j - h + 1];
        }
        if(bestl1[i] < h * minim){
          bestl1[i] = h * minim;
        }
        if(bestc1[j] < h * minim){
          bestc1[j] = h * minim;
        }
      }
    }
  }

  for(register int j = 0 ; j < m;j++)
    cangoup[j] = 0;

  for(register int i = n - 1 ; i >= 0 ;i--){
    for(register int j = m - 1 ; j >= 0;j--){
      if(!matrix[i][j])
        cangoup[j]++;
      else
        cangoup[j] = 0;
      minim = NMAX;
      for(register int h = 1 ; j + h - 1 <= m ; h++){
        if(minim > cangoup[j + h - 1]){
          minim = cangoup[j + h - 1];
        }
        if(bestl2[i] < h * minim){
          bestl2[i] = h * minim;
        }
        if(bestc2[j] < h * minim){
          bestc2[j] = h * minim;
        }
      }
    }
  }
  int rez = 0;
  for(register int l = 0 ; l < n ;l++){
    for(register int l2 = l + 1 ; l2 < n ;l2++){
       if(rez < bestl1[l] + bestl2[l2])
        rez = bestl1[l] + bestl2[l2];
    }
  }
  for(register int c = 0 ; c < m ;c++){
    for(register int c2 = c + 1 ; c2 < m ;c2++){
       if(rez < bestc1[c] + bestc2[c2])
        rez = bestc1[c] + bestc2[c2];
    }
  }
  out<<rez;
}