답안 #96436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96436	2019-02-09T13:06:09 Z	choikiwon	Bomb (IZhO17_bomb)	C++17	37 / 100	988 ms	113076 KB

bomb

#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 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

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	100216 KB	Output is correct
2	Correct	76 ms	100344 KB	Output is correct
3	Correct	85 ms	106364 KB	Output is correct
4	Correct	84 ms	106360 KB	Output is correct
5	Correct	83 ms	100228 KB	Output is correct
6	Correct	81 ms	100248 KB	Output is correct
7	Correct	80 ms	100156 KB	Output is correct
8	Incorrect	82 ms	100344 KB	Output isn't correct
9	Incorrect	78 ms	100216 KB	Output isn't correct
10	Correct	79 ms	100216 KB	Output is correct
11	Incorrect	87 ms	100344 KB	Output isn't correct
12	Correct	80 ms	100216 KB	Output is correct
13	Correct	83 ms	100168 KB	Output is correct
14	Correct	85 ms	100216 KB	Output is correct
15	Incorrect	181 ms	100216 KB	Output isn't correct
16	Correct	81 ms	100344 KB	Output is correct
17	Incorrect	79 ms	100472 KB	Output isn't correct
18	Correct	80 ms	100472 KB	Output is correct
19	Incorrect	79 ms	100444 KB	Output isn't correct
20	Incorrect	70 ms	100472 KB	Output isn't correct
21	Correct	79 ms	100244 KB	Output is correct
22	Correct	82 ms	100344 KB	Output is correct
23	Incorrect	80 ms	100460 KB	Output isn't correct
24	Incorrect	69 ms	100344 KB	Output isn't correct
25	Incorrect	84 ms	100472 KB	Output isn't correct
26	Correct	79 ms	100456 KB	Output is correct
27	Correct	86 ms	100856 KB	Output is correct
28	Correct	85 ms	100984 KB	Output is correct
29	Correct	81 ms	101240 KB	Output is correct
30	Incorrect	89 ms	101368 KB	Output isn't correct
31	Incorrect	93 ms	101112 KB	Output isn't correct
32	Incorrect	88 ms	101276 KB	Output isn't correct
33	Incorrect	93 ms	101376 KB	Output isn't correct
34	Correct	85 ms	101068 KB	Output is correct
35	Incorrect	90 ms	101368 KB	Output isn't correct
36	Incorrect	99 ms	101368 KB	Output isn't correct
37	Incorrect	87 ms	100188 KB	Output isn't correct
38	Correct	988 ms	112504 KB	Output is correct
39	Incorrect	72 ms	100216 KB	Output isn't correct
40	Incorrect	150 ms	102904 KB	Output isn't correct
41	Incorrect	70 ms	100216 KB	Output isn't correct
42	Incorrect	98 ms	100472 KB	Output isn't correct
43	Correct	635 ms	112476 KB	Output is correct
44	Incorrect	84 ms	101368 KB	Output isn't correct
45	Incorrect	574 ms	112352 KB	Output isn't correct
46	Correct	494 ms	113076 KB	Output is correct
47	Incorrect	610 ms	112376 KB	Output isn't correct
48	Incorrect	546 ms	112448 KB	Output isn't correct
49	Correct	780 ms	112504 KB	Output is correct
50	Incorrect	568 ms	112476 KB	Output isn't correct
51	Incorrect	564 ms	112376 KB	Output isn't correct
52	Incorrect	578 ms	112332 KB	Output isn't correct
53	Incorrect	534 ms	112424 KB	Output isn't correct
54	Correct	427 ms	112376 KB	Output is correct
55	Correct	489 ms	112368 KB	Output is correct
56	Correct	891 ms	112500 KB	Output is correct
57	Correct	424 ms	112344 KB	Output is correct
58	Correct	445 ms	112476 KB	Output is correct
59	Correct	421 ms	112376 KB	Output is correct
60	Correct	495 ms	112376 KB	Output is correct
61	Correct	740 ms	112384 KB	Output is correct
62	Correct	886 ms	112520 KB	Output is correct
63	Correct	838 ms	112504 KB	Output is correct
64	Correct	481 ms	112224 KB	Output is correct
65	Incorrect	584 ms	112340 KB	Output isn't correct
66	Incorrect	558 ms	112380 KB	Output isn't correct
67	Incorrect	602 ms	112372 KB	Output isn't correct
68	Incorrect	619 ms	112520 KB	Output isn't correct
69	Correct	465 ms	112404 KB	Output is correct
70	Incorrect	259 ms	108920 KB	Output isn't correct
71	Incorrect	365 ms	112248 KB	Output isn't correct
72	Incorrect	411 ms	112468 KB	Output isn't correct
73	Incorrect	414 ms	112376 KB	Output isn't correct
74	Incorrect	418 ms	112308 KB	Output isn't correct
75	Incorrect	457 ms	112368 KB	Output isn't correct
76	Incorrect	430 ms	112564 KB	Output isn't correct
77	Incorrect	462 ms	112376 KB	Output isn't correct
78	Incorrect	446 ms	112376 KB	Output isn't correct
79	Incorrect	333 ms	112316 KB	Output isn't correct
80	Incorrect	324 ms	112356 KB	Output isn't correct
81	Incorrect	338 ms	112248 KB	Output isn't correct
82	Incorrect	435 ms	112512 KB	Output isn't correct
83	Incorrect	438 ms	112508 KB	Output isn't correct
84	Incorrect	334 ms	112260 KB	Output isn't correct
85	Incorrect	414 ms	112504 KB	Output isn't correct
86	Incorrect	851 ms	112492 KB	Output isn't correct
87	Correct	449 ms	112504 KB	Output is correct
88	Incorrect	471 ms	112488 KB	Output isn't correct
89	Incorrect	578 ms	112412 KB	Output isn't correct
90	Incorrect	311 ms	108920 KB	Output isn't correct
91	Incorrect	492 ms	112484 KB	Output isn't correct
92	Incorrect	575 ms	112344 KB	Output isn't correct
93	Incorrect	850 ms	112276 KB	Output isn't correct
94	Incorrect	570 ms	112504 KB	Output isn't correct
95	Incorrect	464 ms	112316 KB	Output isn't correct
96	Incorrect	460 ms	112604 KB	Output isn't correct
97	Incorrect	885 ms	112488 KB	Output isn't correct
98	Incorrect	501 ms	112304 KB	Output isn't correct
99	Incorrect	577 ms	112372 KB	Output isn't correct
100	Incorrect	866 ms	112628 KB	Output isn't correct