#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define MP make_pair
#define ft first
#define sd second
#define pii pair<int, int>
#define PB push_back
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2510;
const int oo = 2e9;
int n, m, ans, a[N][N], mx = oo, pr[N][N], best[N], nt[N][N];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("in.txt","r",stdin);
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
char c; cin >> c;
a[i][j] = (c == '1' ? 1 : 0);
}
for (int j = 1; j <= m; j++){
for (int i = 1; i <= n; ){
if (a[i][j] == 0)
i++;
else {
int i1 = i;
while (i1 <= n && a[i1][j] == 1)
i1++;
mx = min(mx, i1 - i);
i = i1;
}
}
}
if (mx == oo){
cout << n * m;
return 0;
}
fill(best, best + n + 1, oo);
for (int i = 1; i <= n; i++){
int pre = 0;
for (int j = 1; j <= m; j++){
if (a[i][j] == 0)
pre = j;
pr[i][j] = pre + 1;
}
pre = m + 1;
for (int j = m; j > 0; j--){
if (a[i][j] == 0)
pre = j;
nt[i][j] = pre - 1;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
int mn = oo, mn1 = oo;
int MN = oo, MN1 = oo;
bool bd1 = 0, bd2 = 0;
// if (i == 5 && j == 5){
// cerr << "OK\n";
// }
for (int h = 1; h <= mx; h++){
int ii = i - h + 1;
int i2 = i + h - 1;
if (i < h) bd1 = 1;
if (i + h - 1 > n) bd2 = 1;
if (!bd1 && a[ii][j] == 0) bd1 = 1;
if (!bd2 && a[i2][j] == 0) bd2 = 1;
if (bd1 && bd2) break;
int res = 0;
if (!bd1){
mn = min(mn, j - pr[ii][j] + 1);
mn1 = min(mn1, nt[ii][j] - j);
res = max(res, mn + mn1);
}
if (!bd2){
MN = min(MN, j - pr[i2][j] + 1);
MN1 = min(MN1, nt[i2][j] - j);
res = max(res, MN + MN1);
}
best[h] = min(best[h], res);
}
}
for (int i = 1; i <= mx; i++) {
if (best[i] == oo) return -1;
ans = max(ans, best[i] * i);
}
cout << ans << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
632 KB |
Output is correct |
3 |
Correct |
26 ms |
30564 KB |
Output is correct |
4 |
Correct |
26 ms |
30448 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
632 KB |
Output is correct |
9 |
Correct |
2 ms |
632 KB |
Output is correct |
10 |
Correct |
2 ms |
504 KB |
Output is correct |
11 |
Correct |
2 ms |
632 KB |
Output is correct |
12 |
Correct |
2 ms |
504 KB |
Output is correct |
13 |
Correct |
2 ms |
504 KB |
Output is correct |
14 |
Correct |
2 ms |
504 KB |
Output is correct |
15 |
Correct |
2 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
632 KB |
Output is correct |
17 |
Incorrect |
3 ms |
1272 KB |
Output isn't correct |
18 |
Correct |
3 ms |
1272 KB |
Output is correct |
19 |
Correct |
3 ms |
1528 KB |
Output is correct |
20 |
Incorrect |
3 ms |
1528 KB |
Output isn't correct |
21 |
Correct |
2 ms |
1016 KB |
Output is correct |
22 |
Correct |
3 ms |
1272 KB |
Output is correct |
23 |
Incorrect |
3 ms |
1656 KB |
Output isn't correct |
24 |
Incorrect |
3 ms |
1400 KB |
Output isn't correct |
25 |
Incorrect |
4 ms |
1656 KB |
Output isn't correct |
26 |
Correct |
4 ms |
1656 KB |
Output is correct |
27 |
Correct |
7 ms |
4776 KB |
Output is correct |
28 |
Correct |
8 ms |
5204 KB |
Output is correct |
29 |
Incorrect |
77 ms |
6520 KB |
Output isn't correct |
30 |
Incorrect |
34 ms |
7800 KB |
Output isn't correct |
31 |
Incorrect |
20 ms |
6264 KB |
Output isn't correct |
32 |
Incorrect |
21 ms |
7160 KB |
Output isn't correct |
33 |
Incorrect |
63 ms |
8204 KB |
Output isn't correct |
34 |
Correct |
8 ms |
5624 KB |
Output is correct |
35 |
Correct |
13 ms |
8184 KB |
Output is correct |
36 |
Correct |
107 ms |
8204 KB |
Output is correct |
37 |
Correct |
2 ms |
632 KB |
Output is correct |
38 |
Execution timed out |
1083 ms |
74036 KB |
Time limit exceeded |
39 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
40 |
Execution timed out |
1066 ms |
19968 KB |
Time limit exceeded |
41 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
42 |
Incorrect |
4 ms |
1656 KB |
Output isn't correct |
43 |
Execution timed out |
1083 ms |
74240 KB |
Time limit exceeded |
44 |
Incorrect |
222 ms |
8204 KB |
Output isn't correct |
45 |
Execution timed out |
1025 ms |
73972 KB |
Time limit exceeded |
46 |
Correct |
699 ms |
74168 KB |
Output is correct |
47 |
Execution timed out |
1056 ms |
74132 KB |
Time limit exceeded |
48 |
Execution timed out |
1026 ms |
74020 KB |
Time limit exceeded |
49 |
Correct |
626 ms |
74248 KB |
Output is correct |
50 |
Execution timed out |
1086 ms |
74100 KB |
Time limit exceeded |
51 |
Execution timed out |
1056 ms |
74104 KB |
Time limit exceeded |
52 |
Execution timed out |
1081 ms |
74044 KB |
Time limit exceeded |
53 |
Execution timed out |
1068 ms |
73976 KB |
Time limit exceeded |
54 |
Execution timed out |
1050 ms |
74104 KB |
Time limit exceeded |
55 |
Correct |
960 ms |
74104 KB |
Output is correct |
56 |
Execution timed out |
1080 ms |
74016 KB |
Time limit exceeded |
57 |
Correct |
842 ms |
74104 KB |
Output is correct |
58 |
Execution timed out |
1035 ms |
74108 KB |
Time limit exceeded |
59 |
Correct |
942 ms |
74196 KB |
Output is correct |
60 |
Execution timed out |
1082 ms |
74092 KB |
Time limit exceeded |
61 |
Execution timed out |
1093 ms |
73976 KB |
Time limit exceeded |
62 |
Execution timed out |
1084 ms |
73976 KB |
Time limit exceeded |
63 |
Execution timed out |
1091 ms |
74104 KB |
Time limit exceeded |
64 |
Execution timed out |
1079 ms |
74100 KB |
Time limit exceeded |
65 |
Execution timed out |
1087 ms |
74104 KB |
Time limit exceeded |
66 |
Correct |
539 ms |
74020 KB |
Output is correct |
67 |
Execution timed out |
1085 ms |
74088 KB |
Time limit exceeded |
68 |
Execution timed out |
1089 ms |
74104 KB |
Time limit exceeded |
69 |
Correct |
781 ms |
73976 KB |
Output is correct |
70 |
Execution timed out |
1071 ms |
59524 KB |
Time limit exceeded |
71 |
Execution timed out |
1047 ms |
74232 KB |
Time limit exceeded |
72 |
Execution timed out |
1079 ms |
74196 KB |
Time limit exceeded |
73 |
Execution timed out |
1063 ms |
74104 KB |
Time limit exceeded |
74 |
Execution timed out |
1092 ms |
73976 KB |
Time limit exceeded |
75 |
Execution timed out |
1051 ms |
74104 KB |
Time limit exceeded |
76 |
Execution timed out |
1066 ms |
74076 KB |
Time limit exceeded |
77 |
Execution timed out |
1076 ms |
74104 KB |
Time limit exceeded |
78 |
Execution timed out |
1050 ms |
74204 KB |
Time limit exceeded |
79 |
Incorrect |
255 ms |
74848 KB |
Output isn't correct |
80 |
Incorrect |
258 ms |
75260 KB |
Output isn't correct |
81 |
Incorrect |
535 ms |
75768 KB |
Output isn't correct |
82 |
Execution timed out |
1063 ms |
76512 KB |
Time limit exceeded |
83 |
Execution timed out |
1080 ms |
76664 KB |
Time limit exceeded |
84 |
Incorrect |
231 ms |
77072 KB |
Output isn't correct |
85 |
Execution timed out |
1080 ms |
77308 KB |
Time limit exceeded |
86 |
Execution timed out |
1086 ms |
77476 KB |
Time limit exceeded |
87 |
Execution timed out |
1091 ms |
77304 KB |
Time limit exceeded |
88 |
Execution timed out |
1073 ms |
77432 KB |
Time limit exceeded |
89 |
Execution timed out |
1084 ms |
77688 KB |
Time limit exceeded |
90 |
Execution timed out |
1088 ms |
61304 KB |
Time limit exceeded |
91 |
Execution timed out |
1082 ms |
78328 KB |
Time limit exceeded |
92 |
Execution timed out |
1088 ms |
76536 KB |
Time limit exceeded |
93 |
Execution timed out |
1082 ms |
74104 KB |
Time limit exceeded |
94 |
Execution timed out |
1087 ms |
73976 KB |
Time limit exceeded |
95 |
Execution timed out |
1095 ms |
74120 KB |
Time limit exceeded |
96 |
Execution timed out |
1094 ms |
74104 KB |
Time limit exceeded |
97 |
Execution timed out |
1098 ms |
74104 KB |
Time limit exceeded |
98 |
Execution timed out |
1084 ms |
74104 KB |
Time limit exceeded |
99 |
Execution timed out |
1090 ms |
74104 KB |
Time limit exceeded |
100 |
Execution timed out |
1095 ms |
74104 KB |
Time limit exceeded |