답안 #96444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96444	2019-02-09T13:22:43 Z	choikiwon	Bomb (IZhO17_bomb)	C++17	37 / 100	956 ms	111960 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;
}

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	70 ms	100216 KB	Output is correct
2	Correct	72 ms	100344 KB	Output is correct
3	Correct	76 ms	106360 KB	Output is correct
4	Correct	80 ms	106360 KB	Output is correct
5	Correct	72 ms	100216 KB	Output is correct
6	Correct	70 ms	100216 KB	Output is correct
7	Correct	72 ms	100188 KB	Output is correct
8	Incorrect	70 ms	100216 KB	Output isn't correct
9	Incorrect	70 ms	100344 KB	Output isn't correct
10	Correct	73 ms	100216 KB	Output is correct
11	Incorrect	72 ms	100216 KB	Output isn't correct
12	Correct	98 ms	100216 KB	Output is correct
13	Correct	86 ms	100216 KB	Output is correct
14	Correct	86 ms	100236 KB	Output is correct
15	Incorrect	83 ms	100188 KB	Output isn't correct
16	Correct	70 ms	100188 KB	Output is correct
17	Incorrect	80 ms	100344 KB	Output isn't correct
18	Correct	81 ms	100408 KB	Output is correct
19	Incorrect	82 ms	100408 KB	Output isn't correct
20	Incorrect	87 ms	100472 KB	Output isn't correct
21	Correct	80 ms	100336 KB	Output is correct
22	Correct	81 ms	100368 KB	Output is correct
23	Incorrect	81 ms	100424 KB	Output isn't correct
24	Incorrect	79 ms	100344 KB	Output isn't correct
25	Incorrect	80 ms	100464 KB	Output isn't correct
26	Correct	86 ms	100380 KB	Output is correct
27	Correct	88 ms	100856 KB	Output is correct
28	Correct	89 ms	100848 KB	Output is correct
29	Correct	90 ms	101240 KB	Output is correct
30	Incorrect	102 ms	101240 KB	Output isn't correct
31	Incorrect	93 ms	101128 KB	Output isn't correct
32	Incorrect	87 ms	101212 KB	Output isn't correct
33	Incorrect	84 ms	101368 KB	Output isn't correct
34	Correct	84 ms	101112 KB	Output is correct
35	Incorrect	81 ms	101368 KB	Output isn't correct
36	Incorrect	96 ms	101496 KB	Output isn't correct
37	Incorrect	74 ms	100216 KB	Output isn't correct
38	Correct	908 ms	111352 KB	Output is correct
39	Incorrect	84 ms	100216 KB	Output isn't correct
40	Incorrect	163 ms	103004 KB	Output isn't correct
41	Incorrect	81 ms	100216 KB	Output isn't correct
42	Incorrect	132 ms	100472 KB	Output isn't correct
43	Correct	626 ms	111208 KB	Output is correct
44	Incorrect	84 ms	101368 KB	Output isn't correct
45	Incorrect	580 ms	111096 KB	Output isn't correct
46	Correct	500 ms	111960 KB	Output is correct
47	Incorrect	593 ms	111220 KB	Output isn't correct
48	Incorrect	527 ms	111224 KB	Output isn't correct
49	Correct	754 ms	111352 KB	Output is correct
50	Incorrect	550 ms	111328 KB	Output isn't correct
51	Incorrect	560 ms	111240 KB	Output isn't correct
52	Incorrect	571 ms	111192 KB	Output isn't correct
53	Incorrect	532 ms	111312 KB	Output isn't correct
54	Correct	465 ms	110936 KB	Output is correct
55	Correct	510 ms	110968 KB	Output is correct
56	Correct	956 ms	111132 KB	Output is correct
57	Correct	434 ms	110840 KB	Output is correct
58	Correct	479 ms	110840 KB	Output is correct
59	Correct	475 ms	110764 KB	Output is correct
60	Correct	545 ms	110584 KB	Output is correct
61	Correct	825 ms	110592 KB	Output is correct
62	Correct	829 ms	110712 KB	Output is correct
63	Correct	809 ms	110624 KB	Output is correct
64	Correct	483 ms	110316 KB	Output is correct
65	Incorrect	555 ms	110328 KB	Output isn't correct
66	Incorrect	523 ms	110360 KB	Output isn't correct
67	Incorrect	575 ms	110364 KB	Output isn't correct
68	Incorrect	638 ms	110240 KB	Output isn't correct
69	Correct	476 ms	110328 KB	Output is correct
70	Incorrect	274 ms	108892 KB	Output isn't correct
71	Incorrect	439 ms	110056 KB	Output isn't correct
72	Incorrect	442 ms	109816 KB	Output isn't correct
73	Incorrect	470 ms	110024 KB	Output isn't correct
74	Incorrect	496 ms	109944 KB	Output isn't correct
75	Incorrect	502 ms	109804 KB	Output isn't correct
76	Incorrect	536 ms	109768 KB	Output isn't correct
77	Incorrect	511 ms	109848 KB	Output isn't correct
78	Incorrect	471 ms	109668 KB	Output isn't correct
79	Incorrect	361 ms	109456 KB	Output isn't correct
80	Incorrect	331 ms	109432 KB	Output isn't correct
81	Incorrect	340 ms	109304 KB	Output isn't correct
82	Incorrect	454 ms	109600 KB	Output isn't correct
83	Incorrect	438 ms	109308 KB	Output isn't correct
84	Incorrect	331 ms	109176 KB	Output isn't correct
85	Incorrect	454 ms	109304 KB	Output isn't correct
86	Incorrect	807 ms	109304 KB	Output isn't correct
87	Correct	441 ms	109236 KB	Output is correct
88	Incorrect	448 ms	109048 KB	Output isn't correct
89	Incorrect	617 ms	109024 KB	Output isn't correct
90	Incorrect	316 ms	107984 KB	Output isn't correct
91	Incorrect	530 ms	109048 KB	Output isn't correct
92	Incorrect	586 ms	109136 KB	Output isn't correct
93	Incorrect	803 ms	109052 KB	Output isn't correct
94	Incorrect	581 ms	109048 KB	Output isn't correct
95	Incorrect	450 ms	108888 KB	Output isn't correct
96	Incorrect	472 ms	108920 KB	Output isn't correct
97	Incorrect	838 ms	108968 KB	Output isn't correct
98	Incorrect	485 ms	108792 KB	Output isn't correct
99	Incorrect	562 ms	108696 KB	Output isn't correct
100	Incorrect	820 ms	108828 KB	Output isn't correct