Pagini recente » Cod sursa (job #794833) | Cod sursa (job #1130072) | Cod sursa (job #2395598) | Cod sursa (job #1718476) | Cod sursa (job #2968514)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int NMAX = 202;
int h[NMAX],s[NMAX];
int m,n,sz,rasp;
bool v[NMAX][NMAX];
string str;
int raspSus[NMAX];
int raspJos[NMAX];
int raspSt[NMAX];
int raspDr[NMAX];
void calcLin(int i, bool sus)
{
for(int j=1; j<=m; j++)
{
if(v[i][j]) h[j] = 0;
else h[j]++;
}
sz = rasp = 0;
for(int j=1; j<=m; j++)
{
for(; sz>0 && h[s[sz]] >= h[j]; sz--)
rasp = max(rasp, h[s[sz]] * (j - s[sz-1] - 1));
s[++sz] = j;
}
for(; sz>=0; sz--)
rasp = max(rasp, h[s[sz]] * (m - s[sz-1]));
if(sus) raspSus[i] = rasp;
else raspJos[i] = rasp;
}
void calcCol(int j, bool st)
{
for(int i=1; i<=n; i++)
{
if(v[i][j]) h[i] = 0;
else h[i]++;
}
sz = rasp = 0;
for(int i=1; i<=n; i++)
{
for(; sz>0 && h[s[sz]] >= h[j]; sz--)
rasp = max(rasp, h[s[sz]] * (i - s[sz-1] - 1));
s[++sz] = i;
}
for(; sz>=0; sz--)
rasp = max(rasp, h[s[sz]] * (n - s[sz-1]));
if(st) raspSt[j] = rasp;
else raspDr[j] = rasp;
}
int main()
{
fin>>n>>m;
for(int i=1; i<=n; i++)
{
fin>>str;
for(int j=1; j<=m; j++)
{
v[i][j] = (str[j-1] == '1');
}
}
for(int i=1; i<=n; i++) calcLin(i,1);
memset(h,0,sizeof h);
for(int i=n; i>=1; i--) calcLin(i,0);
memset(h,0,sizeof h);
for(int j=1; j<=m; j++) calcCol(j,1);
memset(h,0,sizeof h);
for(int j=m; j>=1; j--) calcCol(j,0);
memset(h,0,sizeof h);
for(int i=2; i<=n; i++) raspSus[i] = max(raspSus[i], raspSus[i-1]);
for(int i=n-1; i>=1; i--) raspJos[i] = max(raspJos[i], raspJos[i+1]);
for(int j=2; j<=m; j++) raspSt[j] = max(raspSt[j], raspSt[j-1]);
for(int j=m-1; j>=1; j--) raspDr[j] = max(raspDr[j], raspDr[j+1]);
rasp=0;
for(int i=1; i<n; i++)
{
rasp = max(rasp, raspSus[i] + raspJos[i+1]);
}
for(int j=1; j<m; j++)
{
rasp = max(rasp, raspSt[j] + raspDr[j+1]);
}
fout<<rasp;
return 0;
}