fork download
copy 
  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
comments (?)
stdin
copy 
2
5 7
0110110
0000010
1000001
0100001
1100010
3 3
001
100
101
stdout
copy 
Case 1: 12
Case 2: 3
https://ideone.com/2eUIav
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!