Pagini recente » Cod sursa (job #1083628) | Cod sursa (job #3170085) | Cod sursa (job #420642) | Cod sursa (job #2937878) | Cod sursa (job #2473610)
#include <bits/stdc++.h>
#define lim 205
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int sol;
int n, m;
int lin[lim][lim], col[lim][lim];
int v[lim];
char c[2];
int dp1[lim], dp2[lim];
int mat1[lim][lim], mat2[lim][lim];
int st[lim], dr[lim];
stack <int> stk;
inline int sum()
{
st[1] = 0;
stk.push(1);
for (int i = 2; i <= m; i++)
{
while (!stk.empty() && v[i] <= v[stk.top()])
stk.pop();
if(v[i]==v[i-1]) st[i] = st[i-1] + 1;
else if(v[i] > v[i-1]) st[i] = 0;
else
{
if(stk.empty()) st[i] = i-1;
else st[i] = (i - stk.top()- 1);
}
stk.push(i);
}
while (!stk.empty()) stk.pop();
stk.push(m);
dr[m] = 0;
for (int i = m - 1; i >= 1; i--)
{
while (!stk.empty() && v[i] <= v[stk.top()])
stk.pop();
if(v[i]==v[i+1]) dr[i] = dr[i+1]+1;
else if(v[i] > v[i+1]) dr[i] = 0;
else
{
if(stk.empty()) dr[i] = (m-i);
else dr[i] = (stk.top()- i - 1);
}
stk.push(i);
}
while (!stk.empty()) stk.pop();
int s = 0;
for (int i = 1; i <= m; i++)
s = max(s, (st[i] + dr[i] + 1) * v[i]);
return s;
}
inline void solve(int a[205][205])
{
for (int i = 1; i <= m; i++)
dp1[i] = dp2[i] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i][j] == 1)
mat1[i][j] = 0;
else
mat1[i][j] = mat1[i - 1][j] + 1;
for (int i = n; i >= 1; i--)
for (int j = 1; j <= m; j++)
if (a[i][j])
mat2[i][j] = 0;
else
mat2[i][j] = mat2[i + 1][j] + 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
v[j] = mat1[i][j];
int x = sum();
dp1[i] = max(dp1[i - 1], x);
}
for (int i = n; i >= 1; i--)
{
for (int j = 1; j <= m; j++)
v[j] = mat2[i][j];
int x = sum();
dp2[i] = max(dp2[i + 1], x);
}
for (int i = 1; i <= n; i++)
sol = max(sol, dp1[i] + dp2[i + 1]);
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
fin >> c[0];
lin[i][j] = c[0] - '0';
col[j][i] = c[0] - '0';
}
}
solve(lin);
swap(n, m);
solve(col);
fout << sol;
return 0;
}