| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 173132 |
2020-01-03T12:26:14 Z |
VEGAnn |
Bomb (IZhO17_bomb) |
C++14 |
|
1000 ms |
78336 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], 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;
}
}
}
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;
for (int h = 1; h <= mx; h++){
if (i < h) break;
int ii = i - h + 1;
if (a[ii][j] == 0) break;
mn = min(mn, j - pr[ii][j] + 1);
mn1 = min(mn1, nt[ii][j] - j);
best[h] = min(best[h], mn + mn1);
}
}
for (int i = 1; i <= mx; i++)
ans = max(ans, best[i] * i);
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
628 KB |
Output is correct |
| 3 |
Correct |
25 ms |
30456 KB |
Output is correct |
| 4 |
Correct |
26 ms |
30456 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
248 KB |
Output is correct |
| 8 |
Correct |
2 ms |
632 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
632 KB |
Output isn't 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 |
632 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 |
3 ms |
1016 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 23 |
Incorrect |
3 ms |
1660 KB |
Output isn't correct |
| 24 |
Incorrect |
3 ms |
1400 KB |
Output isn't correct |
| 25 |
Incorrect |
3 ms |
1656 KB |
Output isn't correct |
| 26 |
Incorrect |
3 ms |
1656 KB |
Output isn't correct |
| 27 |
Correct |
7 ms |
4984 KB |
Output is correct |
| 28 |
Correct |
8 ms |
5240 KB |
Output is correct |
| 29 |
Incorrect |
36 ms |
6672 KB |
Output isn't correct |
| 30 |
Incorrect |
19 ms |
7800 KB |
Output isn't correct |
| 31 |
Incorrect |
13 ms |
6264 KB |
Output isn't correct |
| 32 |
Incorrect |
14 ms |
7160 KB |
Output isn't correct |
| 33 |
Incorrect |
31 ms |
8184 KB |
Output isn't correct |
| 34 |
Correct |
8 ms |
5624 KB |
Output is correct |
| 35 |
Incorrect |
13 ms |
8184 KB |
Output isn't correct |
| 36 |
Incorrect |
54 ms |
8184 KB |
Output isn't correct |
| 37 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 38 |
Execution timed out |
1085 ms |
73960 KB |
Time limit exceeded |
| 39 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 40 |
Incorrect |
976 ms |
19960 KB |
Output isn't correct |
| 41 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 42 |
Incorrect |
4 ms |
1660 KB |
Output isn't correct |
| 43 |
Execution timed out |
1072 ms |
74104 KB |
Time limit exceeded |
| 44 |
Incorrect |
86 ms |
8184 KB |
Output isn't correct |
| 45 |
Execution timed out |
1081 ms |
74000 KB |
Time limit exceeded |
| 46 |
Correct |
403 ms |
73984 KB |
Output is correct |
| 47 |
Execution timed out |
1076 ms |
74016 KB |
Time limit exceeded |
| 48 |
Incorrect |
817 ms |
74104 KB |
Output isn't correct |
| 49 |
Correct |
327 ms |
74120 KB |
Output is correct |
| 50 |
Incorrect |
870 ms |
74084 KB |
Output isn't correct |
| 51 |
Incorrect |
851 ms |
74104 KB |
Output isn't correct |
| 52 |
Incorrect |
901 ms |
74136 KB |
Output isn't correct |
| 53 |
Incorrect |
868 ms |
74084 KB |
Output isn't correct |
| 54 |
Correct |
591 ms |
74136 KB |
Output is correct |
| 55 |
Correct |
548 ms |
74104 KB |
Output is correct |
| 56 |
Execution timed out |
1084 ms |
74076 KB |
Time limit exceeded |
| 57 |
Correct |
516 ms |
73976 KB |
Output is correct |
| 58 |
Correct |
568 ms |
74192 KB |
Output is correct |
| 59 |
Correct |
540 ms |
74108 KB |
Output is correct |
| 60 |
Correct |
597 ms |
74232 KB |
Output is correct |
| 61 |
Correct |
709 ms |
74128 KB |
Output is correct |
| 62 |
Execution timed out |
1083 ms |
73976 KB |
Time limit exceeded |
| 63 |
Execution timed out |
1080 ms |
74040 KB |
Time limit exceeded |
| 64 |
Execution timed out |
1090 ms |
73976 KB |
Time limit exceeded |
| 65 |
Incorrect |
902 ms |
74044 KB |
Output isn't correct |
| 66 |
Incorrect |
300 ms |
74240 KB |
Output isn't correct |
| 67 |
Incorrect |
820 ms |
74168 KB |
Output isn't correct |
| 68 |
Incorrect |
922 ms |
74232 KB |
Output isn't correct |
| 69 |
Correct |
451 ms |
73976 KB |
Output is correct |
| 70 |
Incorrect |
593 ms |
59512 KB |
Output isn't correct |
| 71 |
Execution timed out |
1078 ms |
74148 KB |
Time limit exceeded |
| 72 |
Execution timed out |
1089 ms |
73976 KB |
Time limit exceeded |
| 73 |
Execution timed out |
1086 ms |
74104 KB |
Time limit exceeded |
| 74 |
Execution timed out |
1086 ms |
74020 KB |
Time limit exceeded |
| 75 |
Execution timed out |
1077 ms |
74080 KB |
Time limit exceeded |
| 76 |
Execution timed out |
1079 ms |
74104 KB |
Time limit exceeded |
| 77 |
Execution timed out |
1080 ms |
73976 KB |
Time limit exceeded |
| 78 |
Execution timed out |
1082 ms |
74104 KB |
Time limit exceeded |
| 79 |
Incorrect |
221 ms |
74616 KB |
Output isn't correct |
| 80 |
Incorrect |
223 ms |
75384 KB |
Output isn't correct |
| 81 |
Incorrect |
320 ms |
76024 KB |
Output isn't correct |
| 82 |
Execution timed out |
1062 ms |
76520 KB |
Time limit exceeded |
| 83 |
Execution timed out |
1082 ms |
76664 KB |
Time limit exceeded |
| 84 |
Incorrect |
212 ms |
76920 KB |
Output isn't correct |
| 85 |
Execution timed out |
1057 ms |
77264 KB |
Time limit exceeded |
| 86 |
Execution timed out |
1033 ms |
77560 KB |
Time limit exceeded |
| 87 |
Execution timed out |
1057 ms |
77456 KB |
Time limit exceeded |
| 88 |
Execution timed out |
1081 ms |
77636 KB |
Time limit exceeded |
| 89 |
Execution timed out |
1072 ms |
77816 KB |
Time limit exceeded |
| 90 |
Execution timed out |
1083 ms |
61448 KB |
Time limit exceeded |
| 91 |
Execution timed out |
1077 ms |
78336 KB |
Time limit exceeded |
| 92 |
Execution timed out |
1062 ms |
78328 KB |
Time limit exceeded |
| 93 |
Execution timed out |
1066 ms |
74184 KB |
Time limit exceeded |
| 94 |
Execution timed out |
1088 ms |
73976 KB |
Time limit exceeded |
| 95 |
Execution timed out |
1070 ms |
74488 KB |
Time limit exceeded |
| 96 |
Execution timed out |
1080 ms |
75512 KB |
Time limit exceeded |
| 97 |
Execution timed out |
1084 ms |
76208 KB |
Time limit exceeded |
| 98 |
Execution timed out |
1086 ms |
77048 KB |
Time limit exceeded |
| 99 |
Execution timed out |
1073 ms |
76536 KB |
Time limit exceeded |
| 100 |
Execution timed out |
1073 ms |
78032 KB |
Time limit exceeded |
