比赛 10101115 评测结果 WWWWWWWWWW
题目名称 牛宫 最终得分 0
用户昵称 lc 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-15 11:02:47
显示代码纯文本
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<algorithm>
  5. using namespace std;
  6. const int maxn = 210,INF = 100000000;
  7. int N,M,Ans;
  8. int Map[maxn][maxn],S[maxn][maxn];
  9. int res[maxn],Maxres[maxn];
  10.  
  11.  
  12. void prep()
  13. {
  14. scanf("%d%d",&N,&M);
  15. for (int i=1; i<=N; i++)
  16. for (int j=1; j<=M; j++)
  17. scanf("%d",&Map[i][j]);
  18. for (int i=1; i<=N; i++)
  19. for (int j=1; j<=M; j++)
  20. S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + Map[i][j];
  21. }
  22.  
  23. int find(int i,int j,int p)
  24. {
  25. int L = 1,R = j;
  26. int S1 = S[i][j] - S[p-1][j];
  27. if (S1 + Maxres[L-1] >0) return L;
  28. if (S1 + Maxres[R-1]<=0) return -1;
  29. while (R-L >1)
  30. {
  31. int Mid = (L + R)/2;
  32. if (S1 + Maxres[Mid-1] >0) R = Mid; else L = Mid;
  33. }
  34. return R;
  35. }
  36.  
  37. void work()
  38. {
  39. for (int i=1; i<=N; i++)
  40. for (int p=1; p<=i; p++)
  41. {
  42. for (int x=1; x<=M; x++) res[x] = S[p-1][x] - S[i][x];
  43. Maxres[0] = 0;
  44. for (int x=1; x<=M; x++) Maxres[x] = max(Maxres[x-1],res[x]);
  45. for (int j=1; j<=M; j++)
  46. {
  47. int q = find(i,j,p);
  48. //printf("%d %d %d %d\n",i,j,p,q);
  49. if (q==-1) continue;
  50. Ans = max(Ans , (i-p+1)*(j-q+1));
  51. }
  52. }
  53. printf("%d\n",Ans);
  54. }
  55.  
  56.  
  57. int main()
  58. {
  59. freopen("long.in","r",stdin);
  60. freopen("long.out","w",stdout);
  61. prep();
  62. work();
  63. return 0;
  64. }