Pagini recente » Cod sursa (job #2274779) | Cod sursa (job #1278693) | Cod sursa (job #2711748) | Cod sursa (job #3264840) | Cod sursa (job #2694232)
#include <bits/stdc++.h>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
//------------------------------------------------
///Globale
const int NMAX = 202;
int n,m,v[NMAX][NMAX],rasp,rasp2,d[NMAX][NMAX],d2[NMAX][NMAX],dp[NMAX],dp2[NMAX],st[NMAX],v2[NMAX][NMAX];
//------------------------------------------------
///Functii
void citire();
void rezolvare();
void afisare();
//------------------------------------------------
int main()
{
citire();
rezolvare();
afisare();
return 0;
}
//------------------------------------------------
void afisare()
{
g << max(rasp,rasp2);
}
//------------------------------------------------
void roteste()
{
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
v2[j][i] = v[i][j];
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
v[i][j] = v2[i][j];
}
//------------------------------------------------
void curata(int n,int m)
{
for(int i = 0; i <= n + 1; ++i)
for(int j = 0; j <= m + 1; ++j)
{
d[i][j] = 0;
d2[i][j] = 0;
}
n = max(n,m);
for(int j = 0; j <= n + 1; ++j)
{
dp[j] = 0;
dp2[j] = 0;
}
}
//------------------------------------------------
int calculeaza(int n,int m)
{
int rasp = 0,nr = 0;
curata(n,m);
for(int j = 1; j <= m; ++j)
{
nr = 0;
dp[j] = dp[j - 1];
for(int i = 1; i <= n; ++i)
{
if(v[i][j] == 0)
d[i][j] = d[i][j - 1] + 1;
else
d[i][j] = 0;
while(nr > 0 && d[i][j] <= d[st[nr]][j])
nr--;
dp[j] = max(dp[j],d[i][j] * (i - st[nr]));
nr++;
st[nr] = i;
}
}
for(int j = m; j >= 1; --j)
{
nr = 0;
dp2[j] = dp2[j + 1];
for(int i = 1; i <= n; ++i)
{
if(v[i][j] == 0)
d2[i][j] = d2[i][j + 1] + 1;
else
d2[i][j] = 0;
while(nr > 0 && d2[i][j] <= d2[st[nr]][j])
nr--;
dp2[j] = max(dp2[j],d2[i][j] * (i - st[nr]));
nr++;
st[nr] = i;
rasp = max(rasp,dp2[j] + dp[j - 1]);
}
}
return rasp;
}
//------------------------------------------------
void rezolvare()
{
rasp = calculeaza(n,m);
roteste();
rasp2 = calculeaza(m,n);
}
//------------------------------------------------
void citire()
{
f >> n >> m;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
char c;
f >> c;
if(c == '1')
v[i][j] = 1;
}
}