Pagini recente » Cod sursa (job #895333) | Cod sursa (job #1421459) | Cod sursa (job #2370624) | Cod sursa (job #24236) | Cod sursa (job #2433894)
#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));
for(int j = 0; j < m; j++)
cut2[j] = max(cut2[j], skyline(j, m));
for(int j = 0;j < m;j++)
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;
}