Pagini recente » Cod sursa (job #133375) | Cod sursa (job #443409) | Cod sursa (job #1443531) | Cod sursa (job #2893122) | Cod sursa (job #1995730)
#include <bits/stdc++.h>
using namespace std;
int v[205];
int a[203][203];
int rotit[203][203];
int dp[4][203];
stack <int> sol;
int functie (int n)
{
int maxim = 0;
sol.push(0);
for (int i = 1; i<=n+1; ++i)
{
while (v[sol.top()]>v[i])
{
int x = sol.top();
sol.pop();
maxim = max(maxim, v[x]*(i-sol.top()-1));
}
sol.push(i);
}
return maxim;
}
void roteste (int n, int m)
{
for (int i = 0; i<=200; ++i)
for (int j = 0; j<=200; ++j)
rotit[i][j] = 0;
for (int j = 1; j<=n; ++j)
for (int i = 1; i<=m; ++i)
rotit[i][j] = a[j][m-i+1];
for (int i = 0; i<=200; ++i)
for (int j = 0; j<=200; ++j)
a[i][j] = 0;
for (int i = 1; i<=m; ++i)
for (int j = 1; j<=n; ++j)
a[i][j] = rotit[i][j];
}
int main()
{
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
int n, m;
fin >> n >> m;
fin.get();
for (int i = 1; i<=n; ++i)
{
for (int j = 1; j<=m; ++j)
{
char c;
c = fin.get();
a[i][j] = (int)(c-'0')^1;
}
fin.get();
}
int x = n, y = m;
for (int d = 0; d<4; ++d)
{
for (int i = 1; i<=y; ++i)
v[i] = 0;
for (int i = 1; i<=x; ++i)
{
for (int j = 1; j<=y; ++j)
{
if (a[i][j])
++v[j];
else v[j] = 0;
}
dp[d][i] = max (dp[d][i-1], functie(y));
}
roteste(x, y);
swap(x, y);
}
int raspuns = 0;
for (int i = 0; i<=n; ++i)
raspuns = max(raspuns, dp[0][i]+dp[2][n-i]);
for (int i = 0; i<=m; ++i)
raspuns = max (raspuns, dp[1][i]+dp[3][m-i]);
fout << raspuns;
return 0;
}