比赛 |
10101115 |
评测结果 |
WWWWWWWWWW |
题目名称 |
牛宫 |
最终得分 |
0 |
用户昵称 |
lc |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2010-11-15 11:02:47 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn = 210,INF = 100000000;
int N,M,Ans;
int Map[maxn][maxn],S[maxn][maxn];
int res[maxn],Maxres[maxn];
void prep()
{
scanf("%d%d",&N,&M);
for (int i=1; i<=N; i++)
for (int j=1; j<=M; j++)
scanf("%d",&Map[i][j]);
for (int i=1; i<=N; i++)
for (int j=1; j<=M; j++)
S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + Map[i][j];
}
int find(int i,int j,int p)
{
int L = 1,R = j;
int S1 = S[i][j] - S[p-1][j];
if (S1 + Maxres[L-1] >0) return L;
if (S1 + Maxres[R-1]<=0) return -1;
while (R-L >1)
{
int Mid = (L + R)/2;
if (S1 + Maxres[Mid-1] >0) R = Mid; else L = Mid;
}
return R;
}
void work()
{
for (int i=1; i<=N; i++)
for (int p=1; p<=i; p++)
{
for (int x=1; x<=M; x++) res[x] = S[p-1][x] - S[i][x];
Maxres[0] = 0;
for (int x=1; x<=M; x++) Maxres[x] = max(Maxres[x-1],res[x]);
for (int j=1; j<=M; j++)
{
int q = find(i,j,p);
//printf("%d %d %d %d\n",i,j,p,q);
if (q==-1) continue;
Ans = max(Ans , (i-p+1)*(j-q+1));
}
}
printf("%d\n",Ans);
}
int main()
{
freopen("long.in","r",stdin);
freopen("long.out","w",stdout);
prep();
work();
return 0;
}