# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
173102 |
2020-01-03T11:16:02 Z |
VEGAnn |
Bomb (IZhO17_bomb) |
C++14 |
|
1000 ms |
102280 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;
ans = max(ans, ht * wd);
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
632 KB |
Output is correct |
3 |
Correct |
47 ms |
40540 KB |
Output is correct |
4 |
Correct |
53 ms |
40568 KB |
Output is correct |
5 |
Correct |
10 ms |
504 KB |
Output is correct |
6 |
Correct |
4 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
508 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 |
636 KB |
Output is correct |
12 |
Correct |
2 ms |
632 KB |
Output is correct |
13 |
Correct |
2 ms |
636 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 |
3 ms |
1400 KB |
Output is correct |
18 |
Correct |
4 ms |
1540 KB |
Output is correct |
19 |
Correct |
5 ms |
1912 KB |
Output is correct |
20 |
Correct |
5 ms |
1912 KB |
Output is correct |
21 |
Correct |
3 ms |
1288 KB |
Output is correct |
22 |
Correct |
5 ms |
1784 KB |
Output is correct |
23 |
Correct |
6 ms |
2168 KB |
Output is correct |
24 |
Correct |
4 ms |
1784 KB |
Output is correct |
25 |
Correct |
7 ms |
2168 KB |
Output is correct |
26 |
Correct |
7 ms |
2168 KB |
Output is correct |
27 |
Correct |
61 ms |
6392 KB |
Output is correct |
28 |
Correct |
83 ms |
6912 KB |
Output is correct |
29 |
Correct |
189 ms |
8696 KB |
Output is correct |
30 |
Correct |
300 ms |
10456 KB |
Output is correct |
31 |
Correct |
197 ms |
8284 KB |
Output is correct |
32 |
Correct |
204 ms |
9464 KB |
Output is correct |
33 |
Correct |
350 ms |
11000 KB |
Output is correct |
34 |
Correct |
53 ms |
7416 KB |
Output is correct |
35 |
Correct |
225 ms |
11000 KB |
Output is correct |
36 |
Correct |
310 ms |
11008 KB |
Output is correct |
37 |
Correct |
1 ms |
660 KB |
Output is correct |
38 |
Execution timed out |
1068 ms |
102008 KB |
Time limit exceeded |
39 |
Correct |
2 ms |
632 KB |
Output is correct |
40 |
Execution timed out |
1014 ms |
27284 KB |
Time limit exceeded |
41 |
Correct |
2 ms |
672 KB |
Output is correct |
42 |
Correct |
8 ms |
2168 KB |
Output is correct |
43 |
Execution timed out |
1072 ms |
102136 KB |
Time limit exceeded |
44 |
Correct |
428 ms |
11000 KB |
Output is correct |
45 |
Execution timed out |
1067 ms |
102204 KB |
Time limit exceeded |
46 |
Execution timed out |
1077 ms |
102228 KB |
Time limit exceeded |
47 |
Execution timed out |
1084 ms |
102280 KB |
Time limit exceeded |
48 |
Execution timed out |
1078 ms |
102264 KB |
Time limit exceeded |
49 |
Execution timed out |
1076 ms |
102148 KB |
Time limit exceeded |
50 |
Execution timed out |
1090 ms |
102208 KB |
Time limit exceeded |
51 |
Execution timed out |
1086 ms |
102236 KB |
Time limit exceeded |
52 |
Execution timed out |
1084 ms |
102008 KB |
Time limit exceeded |
53 |
Execution timed out |
1066 ms |
101036 KB |
Time limit exceeded |
54 |
Execution timed out |
1082 ms |
100344 KB |
Time limit exceeded |
55 |
Execution timed out |
1072 ms |
100044 KB |
Time limit exceeded |
56 |
Execution timed out |
1065 ms |
100112 KB |
Time limit exceeded |
57 |
Execution timed out |
1071 ms |
99960 KB |
Time limit exceeded |
58 |
Execution timed out |
1080 ms |
100088 KB |
Time limit exceeded |
59 |
Execution timed out |
1061 ms |
100308 KB |
Time limit exceeded |
60 |
Execution timed out |
1071 ms |
100044 KB |
Time limit exceeded |
61 |
Execution timed out |
1057 ms |
99932 KB |
Time limit exceeded |
62 |
Execution timed out |
1045 ms |
100100 KB |
Time limit exceeded |
63 |
Execution timed out |
1075 ms |
99960 KB |
Time limit exceeded |
64 |
Execution timed out |
1058 ms |
99928 KB |
Time limit exceeded |
65 |
Execution timed out |
1079 ms |
100044 KB |
Time limit exceeded |
66 |
Execution timed out |
1039 ms |
99956 KB |
Time limit exceeded |
67 |
Execution timed out |
1082 ms |
99380 KB |
Time limit exceeded |
68 |
Execution timed out |
1044 ms |
99348 KB |
Time limit exceeded |
69 |
Execution timed out |
1053 ms |
99548 KB |
Time limit exceeded |
70 |
Execution timed out |
1061 ms |
79772 KB |
Time limit exceeded |
71 |
Execution timed out |
1029 ms |
100044 KB |
Time limit exceeded |
72 |
Execution timed out |
1064 ms |
99952 KB |
Time limit exceeded |
73 |
Execution timed out |
1108 ms |
99936 KB |
Time limit exceeded |
74 |
Execution timed out |
1060 ms |
99956 KB |
Time limit exceeded |
75 |
Execution timed out |
1061 ms |
100188 KB |
Time limit exceeded |
76 |
Execution timed out |
1073 ms |
99960 KB |
Time limit exceeded |
77 |
Execution timed out |
1066 ms |
99960 KB |
Time limit exceeded |
78 |
Execution timed out |
1073 ms |
99960 KB |
Time limit exceeded |
79 |
Execution timed out |
1083 ms |
100600 KB |
Time limit exceeded |
80 |
Execution timed out |
1091 ms |
101044 KB |
Time limit exceeded |
81 |
Execution timed out |
1075 ms |
101092 KB |
Time limit exceeded |
82 |
Execution timed out |
1082 ms |
100960 KB |
Time limit exceeded |
83 |
Execution timed out |
1066 ms |
100984 KB |
Time limit exceeded |
84 |
Execution timed out |
1077 ms |
100984 KB |
Time limit exceeded |
85 |
Execution timed out |
1077 ms |
100984 KB |
Time limit exceeded |
86 |
Execution timed out |
1055 ms |
101376 KB |
Time limit exceeded |
87 |
Execution timed out |
1041 ms |
101240 KB |
Time limit exceeded |
88 |
Execution timed out |
1084 ms |
101344 KB |
Time limit exceeded |
89 |
Execution timed out |
1084 ms |
101240 KB |
Time limit exceeded |
90 |
Execution timed out |
1085 ms |
81308 KB |
Time limit exceeded |
91 |
Execution timed out |
1086 ms |
101240 KB |
Time limit exceeded |
92 |
Execution timed out |
1091 ms |
101244 KB |
Time limit exceeded |
93 |
Execution timed out |
1074 ms |
101368 KB |
Time limit exceeded |
94 |
Execution timed out |
1084 ms |
101296 KB |
Time limit exceeded |
95 |
Execution timed out |
1076 ms |
101364 KB |
Time limit exceeded |
96 |
Execution timed out |
1067 ms |
101296 KB |
Time limit exceeded |
97 |
Execution timed out |
1071 ms |
101240 KB |
Time limit exceeded |
98 |
Execution timed out |
1092 ms |
101240 KB |
Time limit exceeded |
99 |
Execution timed out |
1081 ms |
101284 KB |
Time limit exceeded |
100 |
Execution timed out |
1083 ms |
101112 KB |
Time limit exceeded |