Cod sursa(job #1822616)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 5 decembrie 2016 11:04:23
Problema BMatrix Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream in ("bmatrix.in");
ofstream out ("bmatrix.out");
int const NMAX = 201;
int n , m;
char matrix[NMAX][NMAX];
int cangoup[NMAX];
void avansarecangoup(int line){
  for(int i = 0 ;i < m ;i++){
    if(matrix[line][i] == 0)
      cangoup[i]++;
    else
      cangoup[i] = 0;
  }
}

int height[NMAX],start[NMAX];
int areamax1 = 0, areamax2 = 0 , p = 0;

void rezolvskyline(){
  int pointer = 1;
  height[0] = cangoup[0];
  start[0] = 0;
  for(int i = 1 ; i <= m ;i++){
    if(height[i - 1] <= cangoup[i]){
      height[pointer] = cangoup[i];
      start[pointer] = i;
      pointer++;
    }
    else{
      while(cangoup[i] < height[pointer - 1] && pointer > 0){
        p = height[pointer - 1] * (i - start[pointer - 1 ]);
        if(areamax1 < p){
          areamax1 = p;
        }
        else if (areamax2 < p)
          areamax2 = p;
        pointer--;
      }
      height[pointer] = cangoup[i];
      pointer++;
    }
  }

}
int main()
{
    int i ,j;
    bool ok = 0;
    in>>n>>m;
    for(i = 0 ; i < n ;i++){
      for(j = 0 ; j < m ;j++){
        in>>matrix[i][j];
        matrix[i][j]-='0';
        if(matrix[i][j] == 1)
          ok = 1;
      }
    }
    if(ok == 0){
      out<<n*m;
      return 0;
    }
    for(i = 0 ; i < n ;i++){
      avansarecangoup(i);
      rezolvskyline();
    }
    out<<areamax1 + areamax2;
    return 0;
}