Pagini recente » Cod sursa (job #173294) | Cod sursa (job #2573774) | Cod sursa (job #574253) | Cod sursa (job #2742317) | Cod sursa (job #1995518)
#include <fstream>
#include <stack>
using namespace std;
int dp[202][202];
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int arielin(int lin, int m, int n){
stack<int> h;
h.push(0);
int ds[202][202];
int maxup = -1;
for(int i = 1; i <= lin; i++)
{
for(int j = 1; j <= n+1; j++)
{
while(dp[i][j] < dp[i][h.top()])
{
int val = dp[i][h.top()];
h.pop();
int arie = val*(j-h.top()-1);
if(arie > maxup) maxup = arie;
}
h.push(j);
}
}
int maxdown = -1;
while(h.size()) h.pop();
h.push(0);
for(int i = lin+1; i <= m; i++){
for(int j = 1; j <= n+1; j++){
if(dp[i][j] > i-lin) ds[i][j] = dp[i][j] - dp[lin][j];
else ds[i][j] = dp[i][j];
}
}
for(int i = lin+1; i <= m; i++)
{
for(int j = 1; j <= n+1; j++)
{
while(ds[i][j] < ds[i][h.top()])
{
int val = ds[i][h.top()];
h.pop();
int arie = val*(j-h.top()-1);
if(arie > maxdown) maxdown = arie;
}
h.push(j);
}
}
return maxup + maxdown;
}
int ariecol(int col, int m, int n)
{
stack<int> h;
int maxleft = -1;
h.push(0);
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= col; j++)
{
while(dp[i][j] < dp[i][h.top()])
{
int val = dp[i][h.top()];
h.pop();
int arie = val*(j-h.top()-1);
if(arie > maxleft) maxleft = arie;
}
h.push(j);
}
while(h.size() > 1)
{
int val = dp[i][h.top()];
h.pop();
int arie = val*(col - h.top());
if(arie > maxleft) maxleft = arie;
}
}
int maxright = -1;
h.push(0);
for(int i = 1; i <= m; i++)
{
for(int j = col + 1; j <= n+1; j++)
{
while(dp[i][j] < dp[i][h.top()])
{
int val = dp[i][h.top()];
h.pop();
int arie = val*(j-h.top()-1);
if(arie > maxright) maxright = arie;
}
h.push(j);
}
}
return maxleft + maxright;
}
int main()
{
int m, n;
f >> m >> n;
char nr;
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
f >> nr;
if(nr - '0' == 1) dp[i][j] = 0;
else dp[i][j] = dp[i-1][j] + 1;
}
}
int best = -1;
for(int i = 1; i < m; i++){
best = max(best, arielin(i, m, n));
}
for(int j = 1; j < n; j++){
best = max(best, ariecol(j, m, n));
}
g << best;
return 0;
}