Pagini recente » Cod sursa (job #3354640) | Cod sursa (job #2267320) | Cod sursa (job #1994640) | Borderou de evaluare (job #3331181) | Cod sursa (job #3317848)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
const int NMAX = 2e2;
int ma[NMAX + 1][NMAX + 1], h[NMAX + 1][NMAX + 1], st[NMAX + 1], sus[NMAX + 1], jos[NMAX + 1];
int stg[NMAX + 1], dr[NMAX + 1];
int m, n, vf;
int skyline(int l){
int maxa = 0;
vf = 0;
st[0] = 0;
for(int i = 1; i <= n; i++){
while(vf > 0 && h[l][st[vf]] >= h[l][i]){
int j = st[vf--];
int L = i - st[vf] - 1;
int a = h[l][j] * L;
maxa = max(maxa, a);
}
st[++vf] = i;
}
while(vf > 0){
int j = st[vf--];
int L = n - st[vf];
int a = h[l][j] * L;
maxa = max(maxa, a);
}
return maxa;
}
int main(){
fin >> m >> n;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
char c;
fin >> c;
ma[i][j] = c - '0';
}
}
for(int j = 1; j <= n; j++){
h[0][j] = 0;
for(int i = 1; i <= m; i++){
if(ma[i][j] == 0)
h[i][j] = h[i - 1][j] + 1;
else
h[i][j] = 0;
}
}
sus[0] = 0;
for(int i = 1; i <= m; i++){
sus[i] = max(sus[i - 1], skyline(i));
}
for(int j = 1; j <= n; j++){
h[m + 1][j] = 0;
for(int i = m; i >= 1; i--){
if(ma[i][j] == 0)
h[i][j] = h[i + 1][j] + 1;
else
h[i][j] = 0;
}
}
jos[m + 1] = 0;
for(int i = m; i >= 1; i--){
jos[i] = max(jos[i + 1], skyline(i));
}
int ago = 0;
for(int i = 1; i < m; i++){
ago = max(ago, sus[i] + jos[i + 1]);
}
for(int i = 1; i <= m; i++){
h[i][0] = 0;
for(int j = 1; j <= n; j++){
if(ma[i][j] == 0)
h[i][j] = h[i][j - 1] + 1;
else
h[i][j] = 0;
}
}
stg[0] = 0;
for(int j = 1; j <= n; j++){
int maxa = 0;
vf = 0;
st[0] = 0;
for(int i = 1; i <= m; i++){
while(vf > 0 && h[st[vf]][j] >= h[i][j]){
int k = st[vf--];
int he = i - st[vf] - 1;
int a = h[k][j] * he;
maxa = max(maxa, a);
}
st[++vf] = i;
}
while(vf > 0){
int k = st[vf--];
int he = m - st[vf];
int a = h[k][j] * he;
maxa = max(maxa, a);
}
stg[j] = max(stg[j - 1], maxa);
}
for(int i = 1; i <= m; i++){
h[i][n + 1] = 0;
for(int j = n; j >= 1; j--){
if(ma[i][j] == 0)
h[i][j] = h[i][j + 1] + 1;
else
h[i][j] = 0;
}
}
dr[n + 1] = 0;
for(int j = n; j >= 1; j--){
int maxa = 0;
vf = 0;
st[0] = 0;
for(int i = 1; i <= m; i++){
while(vf > 0 && h[st[vf]][j] >= h[i][j]){
int k = st[vf--];
int he = i - st[vf] - 1;
int a = h[k][j] * he;
maxa = max(maxa, a);
}
st[++vf] = i;
}
while(vf > 0){
int k = st[vf--];
int he = m - st[vf];
int a = h[k][j] * he;
maxa = max(maxa, a);
}
dr[j] = max(dr[j + 1], maxa);
}
int agv = 0;
for(int j = 1; j < n; j++){
agv = max(agv, stg[j] + dr[j + 1]);
}
fout << max(ago, agv);
return 0;
}