# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
173110 |
2020-01-03T11:30:55 Z |
VEGAnn |
Bomb (IZhO17_bomb) |
C++14 |
|
1000 ms |
104568 KB |
#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], pref[N][N], vl[N][N], pl[N][N];
bool ok(int ht, int wd){
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
pl[i][j] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
if (i + ht - 1 > n || j + wd - 1 > m)
break;
int i1 = i + ht - 1, i2 = i - 1;
int j1 = j + wd - 1, j2 = j - 1;
int kol = pref[i1][j1] - pref[i2][j1] - pref[i1][j2] + pref[i2][j2];
if (kol > 0) continue;
pl[i][j]++; pl[i][j + wd]--;
pl[i + ht][j]--; pl[i + ht][j + wd]++;
}
for (int i = 1; i <= n; i++){
int cr = 0;
for (int j = 1; j <= m; j++){
cr += pl[i][j];
vl[i][j] = cr;
}
}
for (int j = 1; j <= m; j++){
int cr = 0;
for (int i = 1; i <= n; i++){
cr += vl[i][j];
if (a[i][j] == 1 && cr == 0)
return 0;
}
}
return 1;
}
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);
pref[i][j] = (a[i][j] ^ 1) + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
}
int wd = m;
for (int ht = 1; ht <= n; ht++){
while (wd > 0 && !ok(ht, wd))
wd--;
if (wd == 0) break;
if (n * wd <= ans) break;
ans = max(ans, ht * wd);
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
632 KB |
Output is correct |
3 |
Correct |
46 ms |
40568 KB |
Output is correct |
4 |
Correct |
50 ms |
40568 KB |
Output is correct |
5 |
Correct |
14 ms |
376 KB |
Output is correct |
6 |
Correct |
4 ms |
376 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 |
636 KB |
Output is correct |
10 |
Correct |
2 ms |
504 KB |
Output is correct |
11 |
Correct |
2 ms |
636 KB |
Output is correct |
12 |
Correct |
3 ms |
632 KB |
Output is correct |
13 |
Correct |
3 ms |
632 KB |
Output is correct |
14 |
Correct |
2 ms |
632 KB |
Output is correct |
15 |
Correct |
2 ms |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
632 KB |
Output is correct |
17 |
Correct |
4 ms |
1504 KB |
Output is correct |
18 |
Correct |
4 ms |
1528 KB |
Output is correct |
19 |
Correct |
6 ms |
2040 KB |
Output is correct |
20 |
Correct |
6 ms |
2040 KB |
Output is correct |
21 |
Correct |
4 ms |
1272 KB |
Output is correct |
22 |
Correct |
5 ms |
1656 KB |
Output is correct |
23 |
Correct |
7 ms |
2168 KB |
Output is correct |
24 |
Correct |
5 ms |
1784 KB |
Output is correct |
25 |
Correct |
8 ms |
2168 KB |
Output is correct |
26 |
Correct |
7 ms |
2168 KB |
Output is correct |
27 |
Correct |
68 ms |
6520 KB |
Output is correct |
28 |
Correct |
102 ms |
6908 KB |
Output is correct |
29 |
Correct |
214 ms |
8952 KB |
Output is correct |
30 |
Correct |
340 ms |
10360 KB |
Output is correct |
31 |
Correct |
192 ms |
8268 KB |
Output is correct |
32 |
Correct |
244 ms |
9472 KB |
Output is correct |
33 |
Correct |
262 ms |
11000 KB |
Output is correct |
34 |
Correct |
56 ms |
7416 KB |
Output is correct |
35 |
Correct |
270 ms |
11008 KB |
Output is correct |
36 |
Correct |
357 ms |
11000 KB |
Output is correct |
37 |
Correct |
2 ms |
632 KB |
Output is correct |
38 |
Execution timed out |
1078 ms |
103868 KB |
Time limit exceeded |
39 |
Correct |
2 ms |
632 KB |
Output is correct |
40 |
Execution timed out |
1059 ms |
27280 KB |
Time limit exceeded |
41 |
Correct |
2 ms |
632 KB |
Output is correct |
42 |
Correct |
8 ms |
2168 KB |
Output is correct |
43 |
Execution timed out |
1077 ms |
103516 KB |
Time limit exceeded |
44 |
Correct |
460 ms |
11008 KB |
Output is correct |
45 |
Execution timed out |
1067 ms |
103544 KB |
Time limit exceeded |
46 |
Execution timed out |
1041 ms |
102844 KB |
Time limit exceeded |
47 |
Execution timed out |
1028 ms |
102748 KB |
Time limit exceeded |
48 |
Execution timed out |
1036 ms |
102904 KB |
Time limit exceeded |
49 |
Execution timed out |
1057 ms |
102776 KB |
Time limit exceeded |
50 |
Execution timed out |
1070 ms |
103324 KB |
Time limit exceeded |
51 |
Execution timed out |
1087 ms |
103344 KB |
Time limit exceeded |
52 |
Execution timed out |
1065 ms |
103616 KB |
Time limit exceeded |
53 |
Execution timed out |
1068 ms |
103672 KB |
Time limit exceeded |
54 |
Execution timed out |
1081 ms |
103580 KB |
Time limit exceeded |
55 |
Execution timed out |
1075 ms |
103416 KB |
Time limit exceeded |
56 |
Execution timed out |
1082 ms |
103656 KB |
Time limit exceeded |
57 |
Execution timed out |
1086 ms |
103416 KB |
Time limit exceeded |
58 |
Execution timed out |
1091 ms |
103416 KB |
Time limit exceeded |
59 |
Execution timed out |
1092 ms |
103416 KB |
Time limit exceeded |
60 |
Execution timed out |
1088 ms |
103532 KB |
Time limit exceeded |
61 |
Execution timed out |
1087 ms |
103444 KB |
Time limit exceeded |
62 |
Execution timed out |
1081 ms |
103416 KB |
Time limit exceeded |
63 |
Execution timed out |
1071 ms |
103432 KB |
Time limit exceeded |
64 |
Execution timed out |
1084 ms |
103416 KB |
Time limit exceeded |
65 |
Execution timed out |
1073 ms |
103416 KB |
Time limit exceeded |
66 |
Execution timed out |
1078 ms |
103324 KB |
Time limit exceeded |
67 |
Execution timed out |
1077 ms |
101368 KB |
Time limit exceeded |
68 |
Execution timed out |
1076 ms |
101828 KB |
Time limit exceeded |
69 |
Execution timed out |
1083 ms |
101928 KB |
Time limit exceeded |
70 |
Execution timed out |
1092 ms |
81144 KB |
Time limit exceeded |
71 |
Execution timed out |
1070 ms |
102008 KB |
Time limit exceeded |
72 |
Execution timed out |
1085 ms |
102392 KB |
Time limit exceeded |
73 |
Execution timed out |
1082 ms |
102648 KB |
Time limit exceeded |
74 |
Execution timed out |
1083 ms |
102516 KB |
Time limit exceeded |
75 |
Execution timed out |
1077 ms |
102264 KB |
Time limit exceeded |
76 |
Execution timed out |
1077 ms |
102520 KB |
Time limit exceeded |
77 |
Execution timed out |
1057 ms |
102620 KB |
Time limit exceeded |
78 |
Execution timed out |
1082 ms |
102904 KB |
Time limit exceeded |
79 |
Execution timed out |
1080 ms |
103032 KB |
Time limit exceeded |
80 |
Execution timed out |
1078 ms |
103672 KB |
Time limit exceeded |
81 |
Execution timed out |
1086 ms |
103544 KB |
Time limit exceeded |
82 |
Execution timed out |
1085 ms |
103672 KB |
Time limit exceeded |
83 |
Execution timed out |
1093 ms |
103544 KB |
Time limit exceeded |
84 |
Execution timed out |
1080 ms |
103800 KB |
Time limit exceeded |
85 |
Execution timed out |
1082 ms |
103800 KB |
Time limit exceeded |
86 |
Execution timed out |
1079 ms |
104232 KB |
Time limit exceeded |
87 |
Execution timed out |
1083 ms |
104472 KB |
Time limit exceeded |
88 |
Execution timed out |
1080 ms |
104568 KB |
Time limit exceeded |
89 |
Execution timed out |
1084 ms |
104368 KB |
Time limit exceeded |
90 |
Execution timed out |
1073 ms |
82680 KB |
Time limit exceeded |
91 |
Execution timed out |
1085 ms |
104084 KB |
Time limit exceeded |
92 |
Execution timed out |
1082 ms |
104184 KB |
Time limit exceeded |
93 |
Execution timed out |
1089 ms |
104184 KB |
Time limit exceeded |
94 |
Execution timed out |
1085 ms |
104440 KB |
Time limit exceeded |
95 |
Execution timed out |
1088 ms |
104440 KB |
Time limit exceeded |
96 |
Execution timed out |
1088 ms |
104312 KB |
Time limit exceeded |
97 |
Execution timed out |
1086 ms |
104312 KB |
Time limit exceeded |
98 |
Execution timed out |
1078 ms |
104284 KB |
Time limit exceeded |
99 |
Execution timed out |
1087 ms |
104332 KB |
Time limit exceeded |
100 |
Execution timed out |
1078 ms |
104184 KB |
Time limit exceeded |