oj.uz

Submission #96764

# Submission time Handle Problem Language Result Execution time Memory
96764 2019-02-11T19:24:43 Z choikiwon Bomb (IZhO17_bomb) C++17
99 / 100
 968 ms 109444 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() {
    //freopen("input.txt", "r", stdin);

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

    for(int i = 0; i <= mnw; i++) mn[i] = 1e9;
    mn[0] = mnh;
    for(int i = 0; i < N; i++) {
        int len = 0;
        int chk1 = 0, chk2 = 0;
        for(int j = 0; j < M; j++) {
            if(G[i][j] == '1') {
                if(dp(i, j, 3) == 1) {
                    len = 1;
                }
                if(len) {
                    if(dp(i, j, 0) == 1) chk1 = 1;
                    if(chk1) mn[len] = min(mn[len], dp(i, j, 1));
                    if(dp(i, j, 1) == 1) chk2 = 1;
                    if(chk2) mn[len] = min(mn[len], dp(i, j, 0));
                }
                len++;
            }
            else len = 0, chk1 = 0, chk2 = 0;
        }
        len = 0;
        chk1 = 0, chk2 = 0;
        for(int j = M - 1; j >= 0; j--) {
            if(G[i][j] == '1') {
                if(dp(i, j, 2) == 1) {
                    len = 1;
                }
                if(len) {
                    if(dp(i, j, 0) == 1) chk1 = 1;
                    if(chk1) mn[len] = min(mn[len], dp(i, j, 1));
                    if(dp(i, j, 1) == 1) chk2 = 1;
                    if(chk2) mn[len] = min(mn[len], dp(i, j, 0));
                }
                len++;
            }
            else len = 0, chk1 = 0, chk2 = 0;
        }
    }
    //*
    for(int i = 0; i < N; i++) {
        int tmn = 1e9;
        int len = 0;
        for(int j = 0; j < M; j++) {
            if(G[i][j] == '1') {
                if(len) tmn = min(tmn, dp(i, j, 1));
                if(dp(i, j, 0) == 1) {
                    if(len) mn[len - 1] = min(mn[len - 1], tmn);
                    tmn = dp(i, j, 1);
                    len = 1;
                }
                if(len) len++;
            }
            else tmn = 1e9, len = 0;
        }
        tmn = 1e9;
        len = 0;
        for(int j = 0; j < M; j++) {
            if(G[i][j] == '1') {
                if(len) tmn = min(tmn, dp(i, j, 0));
                if(dp(i, j, 1) == 1) {
                    if(len) mn[len - 1] = min(mn[len - 1], tmn);
                    tmn = dp(i, j, 0);
                    len = 1;
                }
                if(len) len++;
            }
            else tmn = 1e9, 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:28: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:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
bomb.cpp:33: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
99.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 100088 KB Output is correct
2 Correct 67 ms 100216 KB Output is correct
3 Correct 75 ms 106360 KB Output is correct
4 Correct 73 ms 106240 KB Output is correct
5 Correct 67 ms 100216 KB Output is correct
6 Correct 70 ms 100204 KB Output is correct
7 Correct 68 ms 100180 KB Output is correct
8 Correct 68 ms 100220 KB Output is correct
9 Correct 73 ms 100216 KB Output is correct
10 Correct 67 ms 100200 KB Output is correct
11 Correct 71 ms 100244 KB Output is correct
12 Correct 68 ms 100144 KB Output is correct
13 Correct 67 ms 100216 KB Output is correct
14 Correct 68 ms 100216 KB Output is correct
15 Correct 68 ms 100140 KB Output is correct
16 Correct 69 ms 100188 KB Output is correct
17 Correct 68 ms 100444 KB Output is correct
18 Correct 72 ms 100280 KB Output is correct
19 Correct 71 ms 100344 KB Output is correct
20 Correct 69 ms 100344 KB Output is correct
21 Correct 70 ms 100216 KB Output is correct
22 Correct 69 ms 100344 KB Output is correct
23 Correct 68 ms 100344 KB Output is correct
24 Correct 69 ms 100344 KB Output is correct
25 Correct 72 ms 100476 KB Output is correct
26 Correct 70 ms 100344 KB Output is correct
27 Correct 77 ms 100856 KB Output is correct
28 Correct 82 ms 100856 KB Output is correct
29 Correct 104 ms 101112 KB Output is correct
30 Correct 78 ms 101244 KB Output is correct
31 Correct 75 ms 100996 KB Output is correct
32 Correct 79 ms 101112 KB Output is correct
33 Correct 80 ms 101240 KB Output is correct
34 Correct 79 ms 101112 KB Output is correct
35 Correct 79 ms 101264 KB Output is correct
36 Correct 90 ms 101288 KB Output is correct
37 Correct 72 ms 100220 KB Output is correct
38 Correct 824 ms 108920 KB Output is correct
39 Correct 70 ms 100188 KB Output is correct
40 Incorrect 149 ms 102904 KB Output isn't correct
41 Correct 69 ms 100216 KB Output is correct
42 Correct 69 ms 100420 KB Output is correct
43 Correct 660 ms 108932 KB Output is correct
44 Correct 86 ms 101240 KB Output is correct
45 Correct 649 ms 108964 KB Output is correct
46 Correct 531 ms 108792 KB Output is correct
47 Correct 766 ms 108924 KB Output is correct
48 Correct 572 ms 108924 KB Output is correct
49 Correct 866 ms 109048 KB Output is correct
50 Correct 589 ms 109108 KB Output is correct
51 Correct 563 ms 108924 KB Output is correct
52 Correct 560 ms 108924 KB Output is correct
53 Correct 597 ms 108864 KB Output is correct
54 Correct 475 ms 108948 KB Output is correct
55 Correct 484 ms 108792 KB Output is correct
56 Correct 968 ms 108920 KB Output is correct
57 Correct 488 ms 108980 KB Output is correct
58 Correct 458 ms 108920 KB Output is correct
59 Correct 463 ms 108936 KB Output is correct
60 Correct 603 ms 108896 KB Output is correct
61 Correct 854 ms 109048 KB Output is correct
62 Correct 815 ms 109080 KB Output is correct
63 Correct 857 ms 109040 KB Output is correct
64 Correct 486 ms 108760 KB Output is correct
65 Correct 587 ms 108920 KB Output is correct
66 Correct 542 ms 108920 KB Output is correct
67 Correct 630 ms 109048 KB Output is correct
68 Correct 657 ms 109028 KB Output is correct
69 Correct 490 ms 108836 KB Output is correct
70 Correct 264 ms 107636 KB Output is correct
71 Correct 395 ms 108956 KB Output is correct
72 Correct 443 ms 108840 KB Output is correct
73 Correct 446 ms 108980 KB Output is correct
74 Correct 454 ms 109184 KB Output is correct
75 Correct 452 ms 108992 KB Output is correct
76 Correct 452 ms 109048 KB Output is correct
77 Correct 469 ms 109136 KB Output is correct
78 Correct 449 ms 108888 KB Output is correct
79 Correct 320 ms 109112 KB Output is correct
80 Correct 325 ms 109088 KB Output is correct
81 Correct 328 ms 108944 KB Output is correct
82 Correct 470 ms 109088 KB Output is correct
83 Correct 486 ms 109304 KB Output is correct
84 Correct 335 ms 108948 KB Output is correct
85 Correct 454 ms 109252 KB Output is correct
86 Correct 844 ms 109304 KB Output is correct
87 Correct 462 ms 109052 KB Output is correct
88 Correct 494 ms 109072 KB Output is correct
89 Correct 590 ms 109080 KB Output is correct
90 Correct 326 ms 107872 KB Output is correct
91 Correct 563 ms 109176 KB Output is correct
92 Correct 555 ms 109076 KB Output is correct
93 Correct 742 ms 109176 KB Output is correct
94 Correct 559 ms 109224 KB Output is correct
95 Correct 463 ms 109380 KB Output is correct
96 Correct 473 ms 109276 KB Output is correct
97 Correct 759 ms 109440 KB Output is correct
98 Correct 452 ms 109176 KB Output is correct
99 Correct 521 ms 109444 KB Output is correct
100 Correct 729 ms 109252 KB Output is correct