比赛 |
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;
- }