oj.uz

Submission #96444

# Submission time Handle Problem Language Result Execution time Memory
96444 2019-02-09T13:22:43 Z choikiwon Bomb (IZhO17_bomb) C++17
37 / 100
 956 ms 111960 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MN = 2525;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int N, M;
char G[MN][MN];

int cc[MN][MN][4];
int dp(int r, int c, int d) {
    if(r < 0 || N <= r || c < 0 || M <= c) return 0;
    int &ret = cc[r][c][d];
    if(ret != -1) return ret;
    if(G[r][c] == '0') return ret = 0;
    return ret = dp(r + dy[d], c + dx[d], d) + 1;
}

vector<int> V[MN];
int mn[MN];

int main() {
    scanf("%d %d", &N, &M);

    for(int i = 0; i < N; i++) {
        scanf("\n");
        for(int j = 0; j < M; j++) {
            scanf("%c", &G[i][j]);
        }
    }

    memset(cc, -1, sizeof(cc));

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(G[i][j] == '1' && dp(i, j, 0) == 1) {
                V[i].push_back(j);
            }
        }
    }

    int mnw = 1e9;
    for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) if(G[i][j] == '1') {
        mnw = min(mnw, dp(i, j, 2) + dp(i, j, 3) - 1);
    }

    for(int i = 0; i <= mnw; i++) mn[i] = 1e9;
    for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) if(G[i][j] == '1') {
        int a = lower_bound(V[i].begin(), V[i].end(), j) - V[i].begin();
        int b = a - 1;

        if(a != V[i].size()) {
            mn[ V[i][a] - j + 1 ] = min(mn[ V[i][a] - j + 1 ], dp(i, j, 1));
        }
        if(b != -1) {
            mn[ j - V[i][b] + 1 ] = min(mn[ j - V[i][b] + 1 ], dp(i, j, 1));
        }
    }
    int ans = 0;
    for(int i = 1; i <= mnw; i++) {
        mn[i] = min(mn[i], mn[i - 1]);
        ans = max(ans, mn[i] * i);
    }
    printf("%d", ans);
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:56:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(a != V[i].size()) {
            ~~^~~~~~~~~~~~~~
bomb.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
bomb.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
bomb.cpp:32:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%c", &G[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
37.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 100216 KB Output is correct
2 Correct 72 ms 100344 KB Output is correct
3 Correct 76 ms 106360 KB Output is correct
4 Correct 80 ms 106360 KB Output is correct
5 Correct 72 ms 100216 KB Output is correct
6 Correct 70 ms 100216 KB Output is correct
7 Correct 72 ms 100188 KB Output is correct
8 Incorrect 70 ms 100216 KB Output isn't correct
9 Incorrect 70 ms 100344 KB Output isn't correct
10 Correct 73 ms 100216 KB Output is correct
11 Incorrect 72 ms 100216 KB Output isn't correct
12 Correct 98 ms 100216 KB Output is correct
13 Correct 86 ms 100216 KB Output is correct
14 Correct 86 ms 100236 KB Output is correct
15 Incorrect 83 ms 100188 KB Output isn't correct
16 Correct 70 ms 100188 KB Output is correct
17 Incorrect 80 ms 100344 KB Output isn't correct
18 Correct 81 ms 100408 KB Output is correct
19 Incorrect 82 ms 100408 KB Output isn't correct
20 Incorrect 87 ms 100472 KB Output isn't correct
21 Correct 80 ms 100336 KB Output is correct
22 Correct 81 ms 100368 KB Output is correct
23 Incorrect 81 ms 100424 KB Output isn't correct
24 Incorrect 79 ms 100344 KB Output isn't correct
25 Incorrect 80 ms 100464 KB Output isn't correct
26 Correct 86 ms 100380 KB Output is correct
27 Correct 88 ms 100856 KB Output is correct
28 Correct 89 ms 100848 KB Output is correct
29 Correct 90 ms 101240 KB Output is correct
30 Incorrect 102 ms 101240 KB Output isn't correct
31 Incorrect 93 ms 101128 KB Output isn't correct
32 Incorrect 87 ms 101212 KB Output isn't correct
33 Incorrect 84 ms 101368 KB Output isn't correct
34 Correct 84 ms 101112 KB Output is correct
35 Incorrect 81 ms 101368 KB Output isn't correct
36 Incorrect 96 ms 101496 KB Output isn't correct
37 Incorrect 74 ms 100216 KB Output isn't correct
38 Correct 908 ms 111352 KB Output is correct
39 Incorrect 84 ms 100216 KB Output isn't correct
40 Incorrect 163 ms 103004 KB Output isn't correct
41 Incorrect 81 ms 100216 KB Output isn't correct
42 Incorrect 132 ms 100472 KB Output isn't correct
43 Correct 626 ms 111208 KB Output is correct
44 Incorrect 84 ms 101368 KB Output isn't correct
45 Incorrect 580 ms 111096 KB Output isn't correct
46 Correct 500 ms 111960 KB Output is correct
47 Incorrect 593 ms 111220 KB Output isn't correct
48 Incorrect 527 ms 111224 KB Output isn't correct
49 Correct 754 ms 111352 KB Output is correct
50 Incorrect 550 ms 111328 KB Output isn't correct
51 Incorrect 560 ms 111240 KB Output isn't correct
52 Incorrect 571 ms 111192 KB Output isn't correct
53 Incorrect 532 ms 111312 KB Output isn't correct
54 Correct 465 ms 110936 KB Output is correct
55 Correct 510 ms 110968 KB Output is correct
56 Correct 956 ms 111132 KB Output is correct
57 Correct 434 ms 110840 KB Output is correct
58 Correct 479 ms 110840 KB Output is correct
59 Correct 475 ms 110764 KB Output is correct
60 Correct 545 ms 110584 KB Output is correct
61 Correct 825 ms 110592 KB Output is correct
62 Correct 829 ms 110712 KB Output is correct
63 Correct 809 ms 110624 KB Output is correct
64 Correct 483 ms 110316 KB Output is correct
65 Incorrect 555 ms 110328 KB Output isn't correct
66 Incorrect 523 ms 110360 KB Output isn't correct
67 Incorrect 575 ms 110364 KB Output isn't correct
68 Incorrect 638 ms 110240 KB Output isn't correct
69 Correct 476 ms 110328 KB Output is correct
70 Incorrect 274 ms 108892 KB Output isn't correct
71 Incorrect 439 ms 110056 KB Output isn't correct
72 Incorrect 442 ms 109816 KB Output isn't correct
73 Incorrect 470 ms 110024 KB Output isn't correct
74 Incorrect 496 ms 109944 KB Output isn't correct
75 Incorrect 502 ms 109804 KB Output isn't correct
76 Incorrect 536 ms 109768 KB Output isn't correct
77 Incorrect 511 ms 109848 KB Output isn't correct
78 Incorrect 471 ms 109668 KB Output isn't correct
79 Incorrect 361 ms 109456 KB Output isn't correct
80 Incorrect 331 ms 109432 KB Output isn't correct
81 Incorrect 340 ms 109304 KB Output isn't correct
82 Incorrect 454 ms 109600 KB Output isn't correct
83 Incorrect 438 ms 109308 KB Output isn't correct
84 Incorrect 331 ms 109176 KB Output isn't correct
85 Incorrect 454 ms 109304 KB Output isn't correct
86 Incorrect 807 ms 109304 KB Output isn't correct
87 Correct 441 ms 109236 KB Output is correct
88 Incorrect 448 ms 109048 KB Output isn't correct
89 Incorrect 617 ms 109024 KB Output isn't correct
90 Incorrect 316 ms 107984 KB Output isn't correct
91 Incorrect 530 ms 109048 KB Output isn't correct
92 Incorrect 586 ms 109136 KB Output isn't correct
93 Incorrect 803 ms 109052 KB Output isn't correct
94 Incorrect 581 ms 109048 KB Output isn't correct
95 Incorrect 450 ms 108888 KB Output isn't correct
96 Incorrect 472 ms 108920 KB Output isn't correct
97 Incorrect 838 ms 108968 KB Output isn't correct
98 Incorrect 485 ms 108792 KB Output isn't correct
99 Incorrect 562 ms 108696 KB Output isn't correct
100 Incorrect 820 ms 108828 KB Output isn't correct