답안 #96709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96709	2019-02-11T10:28:16 Z	choikiwon	Bomb (IZhO17_bomb)	C++17	37 / 100	860 ms	112456 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 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

#	결과	실행 시간	메모리	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