oj.uz

Submission #96710

# Submission time Handle Problem Language Result Execution time Memory
96710 2019-02-11T10:36:47 Z choikiwon Bomb (IZhO17_bomb) C++17
47 / 100
 836 ms 106616 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;
        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;
        }
        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++;
                }
            }
        }
    }
    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:30: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:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
bomb.cpp:35: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
47.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 100220 KB Output is correct
2 Correct 81 ms 100216 KB Output is correct
3 Correct 82 ms 106360 KB Output is correct
4 Correct 85 ms 106360 KB Output is correct
5 Correct 77 ms 100180 KB Output is correct
6 Correct 67 ms 100144 KB Output is correct
7 Correct 77 ms 100216 KB Output is correct
8 Incorrect 66 ms 100216 KB Output isn't correct
9 Incorrect 74 ms 100244 KB Output isn't correct
10 Incorrect 75 ms 100136 KB Output isn't correct
11 Correct 68 ms 100220 KB Output is correct
12 Incorrect 76 ms 100132 KB Output isn't correct
13 Correct 68 ms 100216 KB Output is correct
14 Correct 76 ms 100216 KB Output is correct
15 Incorrect 77 ms 100216 KB Output isn't correct
16 Correct 76 ms 100216 KB Output is correct
17 Correct 77 ms 100344 KB Output is correct
18 Incorrect 80 ms 100368 KB Output isn't correct
19 Incorrect 77 ms 100344 KB Output isn't correct
20 Incorrect 85 ms 100412 KB Output isn't correct
21 Incorrect 78 ms 100196 KB Output isn't correct
22 Incorrect 74 ms 100316 KB Output isn't correct
23 Incorrect 73 ms 100472 KB Output isn't correct
24 Incorrect 75 ms 100344 KB Output isn't correct
25 Incorrect 68 ms 100444 KB Output isn't correct
26 Correct 68 ms 100348 KB Output is correct
27 Correct 74 ms 100856 KB Output is correct
28 Incorrect 80 ms 100856 KB Output isn't correct
29 Incorrect 83 ms 101116 KB Output isn't correct
30 Incorrect 76 ms 101240 KB Output isn't correct
31 Correct 75 ms 100984 KB Output is correct
32 Incorrect 76 ms 101240 KB Output isn't correct
33 Incorrect 80 ms 101208 KB Output isn't correct
34 Incorrect 70 ms 100984 KB Output isn't correct
35 Incorrect 75 ms 101216 KB Output isn't correct
36 Correct 90 ms 101412 KB Output is correct
37 Correct 65 ms 100216 KB Output is correct
38 Correct 723 ms 106468 KB Output is correct
39 Correct 67 ms 100216 KB Output is correct
40 Incorrect 151 ms 102428 KB Output isn't correct
41 Correct 75 ms 100188 KB Output is correct
42 Correct 71 ms 100472 KB Output is correct
43 Correct 669 ms 106440 KB Output is correct
44 Correct 92 ms 101236 KB Output is correct
45 Correct 583 ms 106616 KB Output is correct
46 Correct 497 ms 106356 KB Output is correct
47 Correct 570 ms 106360 KB Output is correct
48 Correct 542 ms 106480 KB Output is correct
49 Correct 819 ms 106488 KB Output is correct
50 Correct 547 ms 106488 KB Output is correct
51 Correct 537 ms 106332 KB Output is correct
52 Correct 516 ms 106504 KB Output is correct
53 Correct 570 ms 106468 KB Output is correct
54 Incorrect 445 ms 106332 KB Output isn't correct
55 Incorrect 438 ms 106416 KB Output isn't correct
56 Correct 796 ms 106432 KB Output is correct
57 Incorrect 424 ms 106388 KB Output isn't correct
58 Incorrect 440 ms 106488 KB Output isn't correct
59 Incorrect 458 ms 106468 KB Output isn't correct
60 Correct 614 ms 106480 KB Output is correct
61 Correct 836 ms 106432 KB Output is correct
62 Correct 800 ms 106512 KB Output is correct
63 Correct 804 ms 106488 KB Output is correct
64 Correct 456 ms 106360 KB Output is correct
65 Correct 534 ms 106432 KB Output is correct
66 Correct 498 ms 106516 KB Output is correct
67 Correct 533 ms 106360 KB Output is correct
68 Correct 565 ms 106456 KB Output is correct
69 Incorrect 411 ms 106360 KB Output isn't correct
70 Incorrect 265 ms 105276 KB Output isn't correct
71 Incorrect 382 ms 106344 KB Output isn't correct
72 Incorrect 417 ms 106364 KB Output isn't correct
73 Correct 421 ms 106360 KB Output is correct
74 Incorrect 415 ms 106320 KB Output isn't correct
75 Incorrect 416 ms 106488 KB Output isn't correct
76 Incorrect 429 ms 106488 KB Output isn't correct
77 Incorrect 411 ms 106360 KB Output isn't correct
78 Incorrect 449 ms 106488 KB Output isn't correct
79 Incorrect 323 ms 106332 KB Output isn't correct
80 Incorrect 322 ms 106328 KB Output isn't correct
81 Incorrect 343 ms 106332 KB Output isn't correct
82 Incorrect 416 ms 106380 KB Output isn't correct
83 Incorrect 411 ms 106360 KB Output isn't correct
84 Incorrect 322 ms 106456 KB Output isn't correct
85 Incorrect 433 ms 106384 KB Output isn't correct
86 Incorrect 719 ms 106488 KB Output isn't correct
87 Incorrect 403 ms 106360 KB Output isn't correct
88 Correct 451 ms 106516 KB Output is correct
89 Correct 561 ms 106488 KB Output is correct
90 Incorrect 291 ms 105052 KB Output isn't correct
91 Incorrect 464 ms 106360 KB Output isn't correct
92 Incorrect 483 ms 106452 KB Output isn't correct
93 Incorrect 710 ms 106380 KB Output isn't correct
94 Correct 538 ms 106608 KB Output is correct
95 Incorrect 423 ms 106360 KB Output isn't correct
96 Correct 418 ms 106444 KB Output is correct
97 Incorrect 671 ms 106332 KB Output isn't correct
98 Incorrect 424 ms 106360 KB Output isn't correct
99 Incorrect 481 ms 106488 KB Output isn't correct
100 Incorrect 727 ms 106380 KB Output isn't correct