oj.uz

Submission #96709

# Submission time Handle Problem Language Result Execution time Memory
96709 2019-02-11T10:28:16 Z choikiwon Bomb (IZhO17_bomb) C++17
37 / 100
 860 ms 112456 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;
}

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));

    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++) {
        int len = 0;
        for(int j = 0; j < M; j++) {
            if(G[i][j] == '1') {
                if(dp(i, j, 3) == 1 && dp(i, j, 0) == 1) {
                    len = 1;
                }
                if(len) {
                    mn[len] = min(mn[len], dp(i, j, 1));
                    len++;
                }
            }
            else len = 0;
        }
        len = 0;
        for(int j = M - 1; j >= 0; j--) {
            if(G[i][j] == '1') {
                if(dp(i, j, 2) == 1 && dp(i, j, 0) == 1) {
                    len = 1;
                }
                if(len) {
                    mn[len] = min(mn[len], dp(i, j, 1));
                    len++;
                }
            }
            else len = 0;
        }
    }
    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: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 68 ms 100216 KB Output is correct
2 Correct 72 ms 100200 KB Output is correct
3 Correct 73 ms 106360 KB Output is correct
4 Correct 73 ms 106364 KB Output is correct
5 Correct 74 ms 100088 KB Output is correct
6 Correct 69 ms 100216 KB Output is correct
7 Incorrect 70 ms 100216 KB Output isn't correct
8 Incorrect 68 ms 100140 KB Output isn't correct
9 Incorrect 68 ms 100216 KB Output isn't correct
10 Incorrect 68 ms 100308 KB Output isn't correct
11 Correct 69 ms 100196 KB Output is correct
12 Incorrect 71 ms 100216 KB Output isn't correct
13 Correct 68 ms 100096 KB Output is correct
14 Correct 70 ms 100132 KB Output is correct
15 Incorrect 74 ms 100196 KB Output isn't correct
16 Correct 68 ms 100216 KB Output is correct
17 Correct 71 ms 100344 KB Output is correct
18 Incorrect 85 ms 100268 KB Output isn't correct
19 Incorrect 69 ms 100344 KB Output isn't correct
20 Incorrect 68 ms 100348 KB Output isn't correct
21 Incorrect 70 ms 100216 KB Output isn't correct
22 Incorrect 77 ms 100444 KB Output isn't correct
23 Incorrect 69 ms 100344 KB Output isn't correct
24 Incorrect 80 ms 100392 KB Output isn't correct
25 Incorrect 70 ms 100344 KB Output isn't correct
26 Incorrect 69 ms 100344 KB Output isn't correct
27 Incorrect 74 ms 100860 KB Output isn't correct
28 Incorrect 74 ms 100852 KB Output isn't correct
29 Incorrect 91 ms 101112 KB Output isn't correct
30 Incorrect 95 ms 101240 KB Output isn't correct
31 Correct 76 ms 100984 KB Output is correct
32 Incorrect 77 ms 101116 KB Output isn't correct
33 Incorrect 80 ms 101372 KB Output isn't correct
34 Incorrect 73 ms 101024 KB Output isn't correct
35 Incorrect 89 ms 101240 KB Output isn't correct
36 Incorrect 93 ms 101352 KB Output isn't correct
37 Correct 77 ms 100216 KB Output is correct
38 Correct 706 ms 112320 KB Output is correct
39 Correct 84 ms 100216 KB Output is correct
40 Incorrect 137 ms 102904 KB Output isn't correct
41 Correct 68 ms 100216 KB Output is correct
42 Correct 71 ms 100344 KB Output is correct
43 Correct 571 ms 112220 KB Output is correct
44 Correct 90 ms 101324 KB Output is correct
45 Correct 518 ms 112344 KB Output is correct
46 Correct 455 ms 112136 KB Output is correct
47 Correct 524 ms 112276 KB Output is correct
48 Correct 470 ms 112248 KB Output is correct
49 Incorrect 680 ms 112220 KB Output isn't correct
50 Correct 469 ms 112252 KB Output is correct
51 Correct 511 ms 112320 KB Output is correct
52 Correct 539 ms 112220 KB Output is correct
53 Correct 504 ms 112248 KB Output is correct
54 Incorrect 423 ms 112120 KB Output isn't correct
55 Incorrect 424 ms 112248 KB Output isn't correct
56 Correct 702 ms 112160 KB Output is correct
57 Incorrect 416 ms 112120 KB Output isn't correct
58 Incorrect 405 ms 112248 KB Output isn't correct
59 Incorrect 423 ms 112340 KB Output isn't correct
60 Incorrect 409 ms 112248 KB Output isn't correct
61 Incorrect 736 ms 112352 KB Output isn't correct
62 Incorrect 669 ms 112376 KB Output isn't correct
63 Incorrect 656 ms 112248 KB Output isn't correct
64 Incorrect 411 ms 112248 KB Output isn't correct
65 Correct 555 ms 112380 KB Output is correct
66 Correct 460 ms 112248 KB Output is correct
67 Correct 505 ms 112336 KB Output is correct
68 Correct 521 ms 112248 KB Output is correct
69 Incorrect 422 ms 112304 KB Output isn't correct
70 Incorrect 240 ms 108792 KB Output isn't correct
71 Incorrect 362 ms 112220 KB Output isn't correct
72 Incorrect 398 ms 112348 KB Output isn't correct
73 Correct 405 ms 112368 KB Output is correct
74 Incorrect 410 ms 112248 KB Output isn't correct
75 Incorrect 458 ms 112340 KB Output isn't correct
76 Incorrect 418 ms 112232 KB Output isn't correct
77 Incorrect 420 ms 112244 KB Output isn't correct
78 Incorrect 399 ms 112204 KB Output isn't correct
79 Incorrect 322 ms 112256 KB Output isn't correct
80 Incorrect 324 ms 112228 KB Output isn't correct
81 Incorrect 325 ms 112228 KB Output isn't correct
82 Incorrect 451 ms 112348 KB Output isn't correct
83 Incorrect 392 ms 112220 KB Output isn't correct
84 Incorrect 326 ms 112120 KB Output isn't correct
85 Incorrect 423 ms 112272 KB Output isn't correct
86 Incorrect 860 ms 112404 KB Output isn't correct
87 Incorrect 408 ms 112240 KB Output isn't correct
88 Correct 478 ms 112456 KB Output is correct
89 Correct 500 ms 112232 KB Output is correct
90 Incorrect 285 ms 108828 KB Output isn't correct
91 Incorrect 422 ms 112116 KB Output isn't correct
92 Incorrect 473 ms 112232 KB Output isn't correct
93 Incorrect 671 ms 112248 KB Output isn't correct
94 Correct 477 ms 112208 KB Output is correct
95 Incorrect 438 ms 112344 KB Output isn't correct
96 Correct 390 ms 112272 KB Output is correct
97 Incorrect 622 ms 112256 KB Output isn't correct
98 Incorrect 393 ms 112248 KB Output isn't correct
99 Incorrect 458 ms 112296 KB Output isn't correct
100 Incorrect 640 ms 112376 KB Output isn't correct