Cod sursa(job #2433983)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 30 iunie 2019 10:45:49
Problema BMatrix Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <iostream>

using namespace std;

ifstream in("bmatrix.in");
ofstream out("bmatrix.out");

int const nmax = 200;
char v[nmax][nmax];
char v90[nmax][nmax];

int height[nmax];

int cut1[1 + nmax];
int cut2[1 + nmax];

void Rotate90(int n, int m){
  for(int i = 0;i < n;i++){
    for(int j = 0;j < m;j++){
      v90[m - j - 1][i] = v[i][j];
    }
  }
  for(int i = 0;i < m;i++){
    height[i] = 0;
    cut1[i] = 0;
    cut2[i] = 0;
  }
}

struct block{
  int val, pos;
};

block st[1 + nmax];
int siz;

int skyline(int from, int to){
  int ans = 0, temp;
  siz = 0;
  for(int i = from;i < to;i++){
    temp = i;
    while(st[siz].val >= height[i] && siz > 0){
      temp = st[siz].pos;
      ans = max(ans, (i - temp) * st[siz].val);
      siz--;
    }
    siz++;
    st[siz] = {height[i], temp};
  }
  while(siz > 0){
    temp = st[siz].pos;
    ans = max(ans, (to - temp) * st[siz].val);
    siz--;
  }
  return ans;
}

int solve(int n, int m, char p[nmax][nmax]){
  int ans = 0;
  for(int i = 0;i < n;i++){
    for(int j = 0;j < m;j++){
      if(p[i][j] == '0'){
        height[j]++;
      }else{
        height[j] = 0;
      }
    }
    for(int j = 0; j < m; j++){
      cut1[j] = max(cut1[j], skyline(0, j));
      cut2[j] = max(cut2[j], skyline(j, m));
      ans = max(ans, cut1[j] + cut2[j]);
    }
  }


  return ans;
}
/*
10
01




*/
int main()
{
    int n, m, ans = 0;
    in >> n >> m;
    for(int i = 0;i < n;i++){
      for(int j = 0;j < m;j++){
        in >> v[i][j];
      }
    }
    ans = max(ans, solve(n, m, v));
    Rotate90(n, m);
    ans = max(ans, solve(m, n, v90));
    out << ans;
    return 0;
}