| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 100577 | 2019-03-12T12:40:23 Z | alexpetrescu | Bomb (IZhO17_bomb) | C++14 | 541 ms | 60280 KB |
#include <cstdio>
#include <algorithm>
//FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w");
#define fin stdin
#define fout stdout
#define MAXN 2500
int left[MAXN + 2][MAXN + 2], right[MAXN + 2][MAXN + 2];
int d[MAXN + 2];
char m[MAXN + 2][MAXN + 10];
int nrlin, nrcol;
inline void solve() {
for (int i = 1; i <= nrlin; i++) {
left[i][0] = 0;
for (int j = 1; j <= nrcol; j++)
if (m[i][j] == '1')
left[i][j] = left[i][j - 1];
else
left[i][j] = j;
right[i][nrcol + 1] = nrcol + 1;
for (int j = nrcol; j > 0; j--)
if (m[i][j] == '1')
right[i][j] = right[i][j + 1];
else
right[i][j] = j;
for (int j = 1; j <= nrcol; j++)
if (m[i][j] == '1')
d[1] = std::min(d[1], right[i][j] - left[i][j] - 1);
}
for (int j = 1; j <= nrcol; j++) {
int st = 0, dr = nrcol + 1, cat = 0;
for (int i = 1; i <= nrlin; i++) {
if (m[i][j] == '1') {
st = std::max(st, left[i][j]);
dr = std::min(dr, right[i][j]);
cat++;
d[cat] = std::min(d[cat], dr - st - 1);
} else {
if (cat)
d[cat + 1] = 0;
st = 0, dr = nrcol + 1;
cat = 0;
}
}
if (cat)
d[cat + 1] = 0;
}
}
int main() {
fscanf(fin, "%d%d ", &nrlin, &nrcol);
for (int i = 1; i <= nrlin; i++)
fgets(m[i] + 1, MAXN + 5, fin), d[i] = nrcol;
solve();
for (int i = 1; i <= nrlin / 2; i++)
for (int j = 1; j <= nrcol; j++)
std::swap(m[i][j], m[nrlin - i + 1][j]);
solve();
for (int i = 2; i <= nrlin; i++)
d[i] = std::min(d[i], d[i - 1]);
int ans = d[1];
for (int i = 2; i <= nrlin; i++)
ans = std::max(ans, i * d[i]);
fprintf(fout, "%d\n", ans);
fclose(fin);
fclose(fout);
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 384 KB | Output is correct |
| 2 | Correct | 2 ms | 512 KB | Output is correct |
| 3 | Correct | 22 ms | 26624 KB | Output is correct |
| 4 | Correct | 21 ms | 26492 KB | Output is correct |
| 5 | Correct | 2 ms | 384 KB | Output is correct |
| 6 | Correct | 2 ms | 384 KB | Output is correct |
| 7 | Correct | 2 ms | 384 KB | Output is correct |
| 8 | Correct | 2 ms | 512 KB | Output is correct |
| 9 | Correct | 2 ms | 512 KB | Output is correct |
| 10 | Correct | 2 ms | 512 KB | Output is correct |
| 11 | Correct | 2 ms | 512 KB | Output is correct |
| 12 | Correct | 2 ms | 512 KB | Output is correct |
| 13 | Correct | 2 ms | 512 KB | Output is correct |
| 14 | Correct | 2 ms | 512 KB | Output is correct |
| 15 | Correct | 2 ms | 512 KB | Output is correct |
| 16 | Correct | 2 ms | 512 KB | Output is correct |
| 17 | Correct | 2 ms | 1024 KB | Output is correct |
| 18 | Correct | 4 ms | 1024 KB | Output is correct |
| 19 | Correct | 3 ms | 1408 KB | Output is correct |
| 20 | Correct | 2 ms | 1280 KB | Output is correct |
| 21 | Correct | 3 ms | 896 KB | Output is correct |
| 22 | Correct | 3 ms | 1152 KB | Output is correct |
| 23 | Correct | 4 ms | 1380 KB | Output is correct |
| 24 | Correct | 3 ms | 1152 KB | Output is correct |
| 25 | Correct | 4 ms | 1408 KB | Output is correct |
| 26 | Correct | 3 ms | 1408 KB | Output is correct |
| 27 | Correct | 7 ms | 4124 KB | Output is correct |
| 28 | Correct | 6 ms | 4352 KB | Output is correct |
| 29 | Correct | 8 ms | 5504 KB | Output is correct |
| 30 | Correct | 10 ms | 6520 KB | Output is correct |
| 31 | Correct | 8 ms | 5120 KB | Output is correct |
| 32 | Correct | 9 ms | 6016 KB | Output is correct |
| 33 | Correct | 11 ms | 6784 KB | Output is correct |
| 34 | Correct | 6 ms | 4736 KB | Output is correct |
| 35 | Correct | 10 ms | 6784 KB | Output is correct |
| 36 | Correct | 15 ms | 6912 KB | Output is correct |
| 37 | Correct | 2 ms | 512 KB | Output is correct |
| 38 | Correct | 516 ms | 60280 KB | Output is correct |
| 39 | Correct | 2 ms | 512 KB | Output is correct |
| 40 | Correct | 55 ms | 16376 KB | Output is correct |
| 41 | Correct | 2 ms | 512 KB | Output is correct |
| 42 | Correct | 3 ms | 1408 KB | Output is correct |
| 43 | Correct | 391 ms | 59740 KB | Output is correct |
| 44 | Correct | 13 ms | 6784 KB | Output is correct |
| 45 | Correct | 389 ms | 59640 KB | Output is correct |
| 46 | Correct | 314 ms | 59640 KB | Output is correct |
| 47 | Correct | 388 ms | 59768 KB | Output is correct |
| 48 | Correct | 326 ms | 59828 KB | Output is correct |
| 49 | Correct | 512 ms | 59768 KB | Output is correct |
| 50 | Correct | 346 ms | 59740 KB | Output is correct |
| 51 | Correct | 361 ms | 59640 KB | Output is correct |
| 52 | Correct | 349 ms | 59640 KB | Output is correct |
| 53 | Correct | 372 ms | 59708 KB | Output is correct |
| 54 | Correct | 262 ms | 59896 KB | Output is correct |
| 55 | Correct | 282 ms | 59640 KB | Output is correct |
| 56 | Correct | 500 ms | 59768 KB | Output is correct |
| 57 | Correct | 279 ms | 59760 KB | Output is correct |
| 58 | Correct | 256 ms | 59640 KB | Output is correct |
| 59 | Correct | 264 ms | 59512 KB | Output is correct |
| 60 | Correct | 358 ms | 59640 KB | Output is correct |
| 61 | Correct | 541 ms | 59608 KB | Output is correct |
| 62 | Correct | 529 ms | 59640 KB | Output is correct |
| 63 | Correct | 531 ms | 59512 KB | Output is correct |
| 64 | Correct | 221 ms | 59384 KB | Output is correct |
| 65 | Correct | 334 ms | 59512 KB | Output is correct |
| 66 | Correct | 345 ms | 59632 KB | Output is correct |
| 67 | Correct | 371 ms | 59512 KB | Output is correct |
| 68 | Correct | 384 ms | 59564 KB | Output is correct |
| 69 | Correct | 230 ms | 59512 KB | Output is correct |
| 70 | Correct | 107 ms | 48248 KB | Output is correct |
| 71 | Correct | 201 ms | 59512 KB | Output is correct |
| 72 | Correct | 223 ms | 59480 KB | Output is correct |
| 73 | Correct | 241 ms | 59640 KB | Output is correct |
| 74 | Correct | 257 ms | 59492 KB | Output is correct |
| 75 | Correct | 292 ms | 59572 KB | Output is correct |
| 76 | Correct | 261 ms | 59384 KB | Output is correct |
| 77 | Correct | 274 ms | 59256 KB | Output is correct |
| 78 | Correct | 257 ms | 59384 KB | Output is correct |
| 79 | Correct | 143 ms | 59384 KB | Output is correct |
| 80 | Correct | 126 ms | 59128 KB | Output is correct |
| 81 | Correct | 128 ms | 59256 KB | Output is correct |
| 82 | Correct | 251 ms | 59100 KB | Output is correct |
| 83 | Correct | 265 ms | 59128 KB | Output is correct |
| 84 | Correct | 145 ms | 59128 KB | Output is correct |
| 85 | Correct | 287 ms | 59108 KB | Output is correct |
| 86 | Correct | 523 ms | 59256 KB | Output is correct |
| 87 | Correct | 258 ms | 59000 KB | Output is correct |
| 88 | Correct | 262 ms | 58872 KB | Output is correct |
| 89 | Correct | 341 ms | 58972 KB | Output is correct |
| 90 | Correct | 150 ms | 48128 KB | Output is correct |
| 91 | Correct | 316 ms | 58872 KB | Output is correct |
| 92 | Correct | 344 ms | 59000 KB | Output is correct |
| 93 | Correct | 490 ms | 58872 KB | Output is correct |
| 94 | Correct | 317 ms | 58744 KB | Output is correct |
| 95 | Correct | 280 ms | 58748 KB | Output is correct |
| 96 | Correct | 261 ms | 58616 KB | Output is correct |
| 97 | Correct | 508 ms | 58616 KB | Output is correct |
| 98 | Correct | 267 ms | 58580 KB | Output is correct |
| 99 | Correct | 333 ms | 58616 KB | Output is correct |
| 100 | Correct | 492 ms | 58488 KB | Output is correct |