fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MX = 2e3 + 5;
  5. int Arr[MX][MX], Sum[MX][MX];
  6. char line[MX];
  7.  
  8. void process(int r, int c){
  9. for(int i = 1; i <= r; i++){
  10. for(int j = 1; j <= c; j++){
  11. Sum[i][j] += Sum[i][j - 1] + Arr[i][j];
  12. }
  13.  
  14. for(int j = 1; j <= c; j++){
  15. Sum[i][j] += Sum[i - 1][j];
  16. }
  17. }
  18. }
  19.  
  20. int query(int x, int y){
  21. return Sum[x][y];
  22. }
  23.  
  24. int query(int x1, int y1, int x2, int y2){
  25. int Ans = query(x2, y2);
  26. Ans -= query(x2, y1 - 1);
  27. Ans -= query(x1 - 1, y2);
  28. Ans += query(x1 - 1, y1 - 1);
  29. return Ans;
  30. }
  31.  
  32. bool func(int r1, int r2, int c, int len){
  33. for(int i = 1, j = len; i <= c; i++, j++){
  34. int num = query(r1, i, r2, j);
  35. if(num == (r2 - r1 + 1) * len) return true;
  36. }
  37. return false;
  38. }
  39.  
  40. int b_search(int r1, int r2, int c){
  41. int lo = 0, hi = c + 5, mid;
  42. for(; hi - lo > 1 ;){
  43. mid = (hi + lo)/2;
  44. (func(r1, r2, c, mid)) ? lo = mid : hi = mid;
  45. }
  46.  
  47. return func(r1, r2, c, (hi + lo)/2) * ((hi + lo)/2);
  48. }
  49.  
  50. int solve(int r, int c){
  51. int Ans = 0;
  52. for(int i = 1; i <= r; i++){
  53. for(int j = i; j <= r; j++){
  54. int len = b_search(i, j, c);
  55. Ans = max(Ans, len * (j - i + 1));
  56. }
  57. }
  58. return Ans;
  59. }
  60.  
  61. int main(){
  62. int t, r, c;
  63. scanf("%d", &t);
  64. for(int i = 1; i <= t; i++){
  65. scanf("%d %d", &r, &c);
  66. memset(Arr, 0, sizeof(Arr));
  67. memset(Sum, 0, sizeof(Sum));
  68.  
  69. for(int j = 0; j < r; j++){
  70. scanf("%s", line);
  71. for(int k = 0; k < c; k++){
  72. if(line[k] == '0') Arr[j + 1][k + 1] = 1;
  73. }
  74. }
  75.  
  76. process(r, c);
  77. int Ans = solve(r, c);
  78. printf("Case %d: %d\n", i, Ans);
  79. }
  80. return 0;
  81. }
Success #stdin #stdout 0s 47472KB
stdin
2
5 7
0110110
0000010
1000001
0100001
1100010
3 3
001
100
101
stdout
Case 1: 12
Case 2: 3