#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(),s.end()
//#define int long long
using namespace std;
const int N = (2500 + 12);
const int mod = (1e9 + 7);
const int INF = (0x3f3f3f3f);
char a[N][N], b[N][N];
int up[N][N], down[N][N], leftt[N][N], rightt[N][N];
int n, m;
bool solve(int x,int y){
for(int i = 1;i <= n; i++){
for(int j = 1;j <= m; j++){
b[i][j] = '0';
}
}
for(int i = 1;i <= n; i++){
for(int j = 1;j <= m; j++){
if(a[i][j] == '1' && i >= x && j >= y){
int cnt = 0;
for(int k = i - x + 1; k <= i; k++){
for(int l = j - y + 1; l <= j; l++){
cnt += (a[k][l] == '1');
}
}
if(cnt == x * y){
for(int k = i - x + 1; k <= i; k++){
for(int l = j - y + 1; l <= j; l++){
b[k][l] = '1';
}
}
}
}
}
}
for(int i = 1;i <= n; i++){
for(int j = 1;j <= m; j++){
if(a[i][j] != b[i][j]){
return false;
}
}
}
return true;
}
main()
{
cin >> n >> m;
for(int i = 1;i <= n; i++){
for(int j = 1;j <= m; j++){
cin >> a[i][j];
}
}
int mnx = INF, mny = INF;
for(int i = 1;i <= n; i++){
int cnt = 0;
for(int j = 1;j <= m; j++){
cnt = (a[i][j] == '0' ? 0 : cnt + 1);
leftt[i][j] = cnt;
mny = min(mny, leftt[i][j]);
}
}
for(int i = 1;i <= n; i++){
int cnt = 0;
for(int j = m;j >= 1; j--){
cnt = (a[i][j] == '0' ? 0 : cnt + 1);
rightt[i][j] = cnt;
mny = min(mny, rightt[i][j]);
}
}
for(int i = 1;i <= m; i++){
int cnt = 0;
for(int j = 1;j <= n; j++){
cnt = (a[j][i] == '0' ? 0 : cnt + 1);
up[j][i] = cnt;
mnx = min(mnx, up[j][i]);
}
}
for(int i = 1;i <= m; i++){
int cnt = 0;
for(int j = n;j >= 1; j--){
cnt = (a[j][i] == '0' ? 0 : cnt + 1);
down[j][i] = cnt;
}
}
int ans = 0;
for(int i = 1;i <= n; i++){
for(int j = 1;j <= m; j++){
if(solve(i,j)){
ans = max(ans, i * j);
}
}
}
cout << ans;
}
/*
20 20
11111000000000000000
11111000000000000000
11111100000000000000
11111111111000000000
00000111111000000000
00000111111000000000
00000011111000000000
00000001111100000000
00000000111110000000
00000000111110000000
00000000111110000000
00000000111110000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
*/
Compilation message
bomb.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
760 KB |
Output is correct |
3 |
Execution timed out |
1081 ms |
52728 KB |
Time limit exceeded |
4 |
Execution timed out |
1087 ms |
52856 KB |
Time limit exceeded |
5 |
Execution timed out |
1085 ms |
376 KB |
Time limit exceeded |
6 |
Correct |
186 ms |
436 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
760 KB |
Output is correct |
9 |
Correct |
3 ms |
760 KB |
Output is correct |
10 |
Correct |
2 ms |
632 KB |
Output is correct |
11 |
Correct |
3 ms |
760 KB |
Output is correct |
12 |
Correct |
2 ms |
632 KB |
Output is correct |
13 |
Correct |
2 ms |
632 KB |
Output is correct |
14 |
Correct |
3 ms |
764 KB |
Output is correct |
15 |
Correct |
3 ms |
760 KB |
Output is correct |
16 |
Correct |
5 ms |
760 KB |
Output is correct |
17 |
Execution timed out |
1074 ms |
1784 KB |
Time limit exceeded |
18 |
Correct |
41 ms |
1912 KB |
Output is correct |
19 |
Correct |
365 ms |
2552 KB |
Output is correct |
20 |
Correct |
478 ms |
2444 KB |
Output is correct |
21 |
Correct |
37 ms |
1656 KB |
Output is correct |
22 |
Correct |
84 ms |
2040 KB |
Output is correct |
23 |
Execution timed out |
1091 ms |
2552 KB |
Time limit exceeded |
24 |
Correct |
469 ms |
2188 KB |
Output is correct |
25 |
Execution timed out |
1047 ms |
2552 KB |
Time limit exceeded |
26 |
Execution timed out |
1089 ms |
2552 KB |
Time limit exceeded |
27 |
Execution timed out |
1091 ms |
7800 KB |
Time limit exceeded |
28 |
Execution timed out |
1084 ms |
8056 KB |
Time limit exceeded |
29 |
Execution timed out |
1089 ms |
10488 KB |
Time limit exceeded |
30 |
Execution timed out |
1090 ms |
12408 KB |
Time limit exceeded |
31 |
Execution timed out |
1090 ms |
9720 KB |
Time limit exceeded |
32 |
Execution timed out |
1085 ms |
11260 KB |
Time limit exceeded |
33 |
Execution timed out |
1090 ms |
12924 KB |
Time limit exceeded |
34 |
Execution timed out |
1080 ms |
9080 KB |
Time limit exceeded |
35 |
Execution timed out |
1085 ms |
12924 KB |
Time limit exceeded |
36 |
Execution timed out |
1074 ms |
12920 KB |
Time limit exceeded |
37 |
Correct |
3 ms |
760 KB |
Output is correct |
38 |
Execution timed out |
1089 ms |
111052 KB |
Time limit exceeded |
39 |
Correct |
3 ms |
760 KB |
Output is correct |
40 |
Execution timed out |
1086 ms |
30840 KB |
Time limit exceeded |
41 |
Correct |
4 ms |
760 KB |
Output is correct |
42 |
Execution timed out |
1068 ms |
2552 KB |
Time limit exceeded |
43 |
Execution timed out |
1095 ms |
111096 KB |
Time limit exceeded |
44 |
Execution timed out |
1085 ms |
12920 KB |
Time limit exceeded |
45 |
Execution timed out |
1087 ms |
110932 KB |
Time limit exceeded |
46 |
Execution timed out |
1085 ms |
111060 KB |
Time limit exceeded |
47 |
Execution timed out |
1092 ms |
110972 KB |
Time limit exceeded |
48 |
Execution timed out |
1084 ms |
111232 KB |
Time limit exceeded |
49 |
Execution timed out |
1097 ms |
111004 KB |
Time limit exceeded |
50 |
Execution timed out |
1089 ms |
111160 KB |
Time limit exceeded |
51 |
Execution timed out |
1084 ms |
111120 KB |
Time limit exceeded |
52 |
Execution timed out |
1093 ms |
111224 KB |
Time limit exceeded |
53 |
Execution timed out |
1085 ms |
111208 KB |
Time limit exceeded |
54 |
Execution timed out |
1085 ms |
111096 KB |
Time limit exceeded |
55 |
Execution timed out |
1092 ms |
111164 KB |
Time limit exceeded |
56 |
Execution timed out |
1089 ms |
111352 KB |
Time limit exceeded |
57 |
Execution timed out |
1088 ms |
111236 KB |
Time limit exceeded |
58 |
Execution timed out |
1088 ms |
111256 KB |
Time limit exceeded |
59 |
Execution timed out |
1091 ms |
111232 KB |
Time limit exceeded |
60 |
Execution timed out |
1072 ms |
111176 KB |
Time limit exceeded |
61 |
Execution timed out |
1090 ms |
111224 KB |
Time limit exceeded |
62 |
Execution timed out |
1077 ms |
111252 KB |
Time limit exceeded |
63 |
Execution timed out |
1078 ms |
111236 KB |
Time limit exceeded |
64 |
Execution timed out |
1087 ms |
111212 KB |
Time limit exceeded |
65 |
Execution timed out |
1093 ms |
111224 KB |
Time limit exceeded |
66 |
Execution timed out |
1093 ms |
111224 KB |
Time limit exceeded |
67 |
Execution timed out |
1078 ms |
111120 KB |
Time limit exceeded |
68 |
Execution timed out |
1085 ms |
111176 KB |
Time limit exceeded |
69 |
Execution timed out |
1079 ms |
111272 KB |
Time limit exceeded |
70 |
Execution timed out |
1071 ms |
89192 KB |
Time limit exceeded |
71 |
Execution timed out |
1089 ms |
111352 KB |
Time limit exceeded |
72 |
Execution timed out |
1080 ms |
111072 KB |
Time limit exceeded |
73 |
Execution timed out |
1088 ms |
111196 KB |
Time limit exceeded |
74 |
Execution timed out |
1083 ms |
111124 KB |
Time limit exceeded |
75 |
Execution timed out |
1084 ms |
111144 KB |
Time limit exceeded |
76 |
Execution timed out |
1089 ms |
111352 KB |
Time limit exceeded |
77 |
Execution timed out |
1087 ms |
111352 KB |
Time limit exceeded |
78 |
Execution timed out |
1088 ms |
111208 KB |
Time limit exceeded |
79 |
Execution timed out |
1091 ms |
111272 KB |
Time limit exceeded |
80 |
Execution timed out |
1071 ms |
111168 KB |
Time limit exceeded |
81 |
Execution timed out |
1083 ms |
111096 KB |
Time limit exceeded |
82 |
Execution timed out |
1099 ms |
111096 KB |
Time limit exceeded |
83 |
Execution timed out |
1093 ms |
111096 KB |
Time limit exceeded |
84 |
Execution timed out |
1079 ms |
111128 KB |
Time limit exceeded |
85 |
Execution timed out |
1090 ms |
111096 KB |
Time limit exceeded |
86 |
Execution timed out |
1084 ms |
111096 KB |
Time limit exceeded |
87 |
Execution timed out |
1089 ms |
111076 KB |
Time limit exceeded |
88 |
Execution timed out |
1088 ms |
111024 KB |
Time limit exceeded |
89 |
Execution timed out |
1095 ms |
111092 KB |
Time limit exceeded |
90 |
Execution timed out |
1084 ms |
88952 KB |
Time limit exceeded |
91 |
Execution timed out |
1090 ms |
111028 KB |
Time limit exceeded |
92 |
Execution timed out |
1091 ms |
110968 KB |
Time limit exceeded |
93 |
Execution timed out |
1093 ms |
111096 KB |
Time limit exceeded |
94 |
Execution timed out |
1090 ms |
111224 KB |
Time limit exceeded |
95 |
Execution timed out |
1078 ms |
111112 KB |
Time limit exceeded |
96 |
Execution timed out |
1091 ms |
111180 KB |
Time limit exceeded |
97 |
Execution timed out |
1082 ms |
111096 KB |
Time limit exceeded |
98 |
Execution timed out |
1094 ms |
111152 KB |
Time limit exceeded |
99 |
Execution timed out |
1082 ms |
111128 KB |
Time limit exceeded |
100 |
Execution timed out |
1094 ms |
110972 KB |
Time limit exceeded |