oj.uz

Submission #96445

# Submission time Handle Problem Language Result Execution time Memory
96445 2019-02-09T13:27:41 Z choikiwon Bomb (IZhO17_bomb) C++17
37 / 100
 983 ms 107696 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;
        int l = j - dp(i, j, 3) + 1;
        int r = j + dp(i, j, 2) + 1;

        if(a != V[i].size() && V[i][a] <= r) {
            mn[ V[i][a] - j + 1 ] = min(mn[ V[i][a] - j + 1 ], dp(i, j, 1));
        }
        if(b != -1 && l <= V[i][b]) {
            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:58:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(a != V[i].size() && V[i][a] <= r) {
            ~~^~~~~~~~~~~~~~
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 73 ms 100216 KB Output is correct
2 Correct 68 ms 100216 KB Output is correct
3 Correct 75 ms 106360 KB Output is correct
4 Correct 73 ms 106364 KB Output is correct
5 Correct 69 ms 100216 KB Output is correct
6 Correct 82 ms 100216 KB Output is correct
7 Correct 78 ms 100216 KB Output is correct
8 Incorrect 69 ms 100216 KB Output isn't correct
9 Incorrect 68 ms 100216 KB Output isn't correct
10 Correct 94 ms 100216 KB Output is correct
11 Incorrect 67 ms 100216 KB Output isn't correct
12 Correct 67 ms 100216 KB Output is correct
13 Correct 79 ms 100216 KB Output is correct
14 Correct 73 ms 100344 KB Output is correct
15 Incorrect 77 ms 100216 KB Output isn't correct
16 Correct 77 ms 100216 KB Output is correct
17 Incorrect 79 ms 100344 KB Output isn't correct
18 Correct 77 ms 100344 KB Output is correct
19 Incorrect 78 ms 100472 KB Output isn't correct
20 Incorrect 79 ms 100472 KB Output isn't correct
21 Correct 78 ms 100288 KB Output is correct
22 Correct 82 ms 100368 KB Output is correct
23 Incorrect 77 ms 100492 KB Output isn't correct
24 Incorrect 69 ms 100412 KB Output isn't correct
25 Incorrect 73 ms 100472 KB Output isn't correct
26 Correct 79 ms 100472 KB Output is correct
27 Correct 85 ms 100984 KB Output is correct
28 Correct 83 ms 100856 KB Output is correct
29 Correct 76 ms 101212 KB Output is correct
30 Incorrect 83 ms 101216 KB Output isn't correct
31 Incorrect 75 ms 100960 KB Output isn't correct
32 Incorrect 74 ms 101240 KB Output isn't correct
33 Incorrect 86 ms 101368 KB Output isn't correct
34 Correct 78 ms 101112 KB Output is correct
35 Incorrect 87 ms 101240 KB Output isn't correct
36 Incorrect 100 ms 101496 KB Output isn't correct
37 Incorrect 80 ms 100216 KB Output isn't correct
38 Correct 960 ms 106688 KB Output is correct
39 Incorrect 79 ms 100216 KB Output isn't correct
40 Incorrect 152 ms 102392 KB Output isn't correct
41 Incorrect 77 ms 100216 KB Output isn't correct
42 Incorrect 81 ms 100520 KB Output isn't correct
43 Correct 682 ms 106584 KB Output is correct
44 Incorrect 95 ms 101476 KB Output isn't correct
45 Incorrect 634 ms 106460 KB Output isn't correct
46 Correct 494 ms 107256 KB Output is correct
47 Incorrect 641 ms 106616 KB Output isn't correct
48 Incorrect 577 ms 106512 KB Output isn't correct
49 Correct 726 ms 106560 KB Output is correct
50 Incorrect 554 ms 106488 KB Output isn't correct
51 Incorrect 589 ms 106616 KB Output isn't correct
52 Incorrect 545 ms 106492 KB Output isn't correct
53 Incorrect 532 ms 106552 KB Output isn't correct
54 Correct 426 ms 106360 KB Output is correct
55 Correct 534 ms 106640 KB Output is correct
56 Correct 983 ms 106616 KB Output is correct
57 Correct 492 ms 106616 KB Output is correct
58 Correct 485 ms 106532 KB Output is correct
59 Correct 471 ms 106488 KB Output is correct
60 Correct 547 ms 106524 KB Output is correct
61 Correct 761 ms 106668 KB Output is correct
62 Correct 893 ms 106516 KB Output is correct
63 Correct 948 ms 106484 KB Output is correct
64 Correct 491 ms 106540 KB Output is correct
65 Incorrect 576 ms 106652 KB Output isn't correct
66 Incorrect 540 ms 106524 KB Output isn't correct
67 Incorrect 617 ms 106560 KB Output isn't correct
68 Incorrect 678 ms 106576 KB Output isn't correct
69 Correct 470 ms 106484 KB Output is correct
70 Incorrect 257 ms 105208 KB Output isn't correct
71 Incorrect 389 ms 106440 KB Output isn't correct
72 Incorrect 441 ms 106404 KB Output isn't correct
73 Incorrect 440 ms 106612 KB Output isn't correct
74 Incorrect 425 ms 106588 KB Output isn't correct
75 Incorrect 452 ms 106460 KB Output isn't correct
76 Incorrect 509 ms 106488 KB Output isn't correct
77 Incorrect 503 ms 106612 KB Output isn't correct
78 Incorrect 455 ms 106344 KB Output isn't correct
79 Incorrect 319 ms 106360 KB Output isn't correct
80 Incorrect 308 ms 106488 KB Output isn't correct
81 Incorrect 323 ms 106544 KB Output isn't correct
82 Incorrect 443 ms 106488 KB Output isn't correct
83 Incorrect 467 ms 106568 KB Output isn't correct
84 Incorrect 324 ms 106488 KB Output isn't correct
85 Incorrect 431 ms 106520 KB Output isn't correct
86 Incorrect 830 ms 106604 KB Output isn't correct
87 Correct 432 ms 106488 KB Output is correct
88 Incorrect 459 ms 106460 KB Output isn't correct
89 Incorrect 579 ms 106744 KB Output isn't correct
90 Incorrect 300 ms 105320 KB Output isn't correct
91 Incorrect 470 ms 106488 KB Output isn't correct
92 Incorrect 556 ms 106672 KB Output isn't correct
93 Incorrect 806 ms 106488 KB Output isn't correct
94 Incorrect 555 ms 106488 KB Output isn't correct
95 Incorrect 447 ms 106536 KB Output isn't correct
96 Incorrect 431 ms 106488 KB Output isn't correct
97 Incorrect 846 ms 106496 KB Output isn't correct
98 Incorrect 471 ms 106744 KB Output isn't correct
99 Incorrect 547 ms 107680 KB Output isn't correct
100 Incorrect 833 ms 107696 KB Output isn't correct