oj.uz

Submission #96708

# Submission time Handle Problem Language Result Execution time Memory
96708 2019-02-11T10:27:04 Z choikiwon Bomb (IZhO17_bomb) C++17
0 / 100
 472 ms 132096 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 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:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input.txt", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bomb.cpp:29: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:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
bomb.cpp:34: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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 246 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 256 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 227 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 231 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 231 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 226 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 279 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 251 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 247 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 261 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 272 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 249 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 248 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 265 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 256 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 301 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 260 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 275 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 292 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 274 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 293 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 247 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 264 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 253 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 472 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 259 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 261 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 265 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 255 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 325 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 251 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 265 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 261 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 245 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 260 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 259 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 259 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 231 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 280 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 256 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 252 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 230 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Runtime error 240 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 234 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Runtime error 240 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 255 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 265 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 281 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 272 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 324 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 251 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 254 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 287 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
54 Runtime error 269 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
55 Runtime error 258 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Runtime error 273 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
57 Runtime error 262 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
58 Runtime error 326 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
59 Runtime error 257 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
60 Runtime error 259 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
61 Runtime error 260 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
62 Runtime error 244 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
63 Runtime error 252 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
64 Runtime error 235 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
65 Runtime error 256 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
66 Runtime error 235 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
67 Runtime error 232 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
68 Runtime error 241 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
69 Runtime error 244 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
70 Runtime error 234 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
71 Runtime error 235 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
72 Runtime error 245 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
73 Runtime error 262 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
74 Runtime error 274 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
75 Runtime error 254 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
76 Runtime error 277 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
77 Runtime error 237 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
78 Runtime error 231 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
79 Runtime error 244 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
80 Runtime error 254 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
81 Runtime error 259 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
82 Runtime error 254 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
83 Runtime error 264 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
84 Runtime error 256 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
85 Runtime error 255 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
86 Runtime error 271 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
87 Runtime error 263 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
88 Runtime error 248 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
89 Runtime error 258 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
90 Runtime error 228 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
91 Runtime error 236 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
92 Runtime error 239 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
93 Runtime error 233 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
94 Runtime error 235 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
95 Runtime error 230 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
96 Runtime error 245 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
97 Runtime error 244 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
98 Runtime error 265 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
99 Runtime error 252 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
100 Runtime error 266 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)