oj.uz

Submission #96803

# Submission time Handle Problem Language Result Execution time Memory
96803 2019-02-12T04:18:56 Z choikiwon Bomb (IZhO17_bomb) C++17
0 / 100
 450 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 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;
        int x = 1e9, y = 1e9;
        for(int j = 0; j < M; j++) {
            if(G[i][j] == '1') {
                if(dp(i, j, 3) == 1) {
                    len = 1;
                }
                if(len) {
                    x = min(x, dp(i, j, 0));
                    y = min(y, dp(i, j, 1));
                    mn[len] = min(mn[len], x + y - 1);
                }
                len++;
            }
            else len = 0, x = y = 1e9;
        }
        len = 0;
        x = y = 1e9;
        for(int j = M - 1; j >= 0; j--) {
            if(G[i][j] == '1') {
                if(dp(i, j, 2) == 1) {
                    len = 1;
                }
                if(len) {
                    x = min(x, dp(i, j, 0));
                    y = min(y, dp(i, j, 1));
                    mn[len] = min(mn[len], x + y - 1);
                }
                len++;
            }
            else len = 0, x = y = 1e9;
        }
    }
    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:28: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:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
bomb.cpp:33: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 307 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 257 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 235 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 244 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 233 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 235 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 262 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 242 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 235 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 263 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 226 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 229 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 229 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 252 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 248 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 232 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 252 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 230 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 261 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 263 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 241 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 247 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 252 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 265 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 272 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 269 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 266 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 274 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 252 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 260 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 264 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 251 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 239 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 236 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 226 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 237 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 262 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 246 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 252 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 242 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 252 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Runtime error 264 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 236 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Runtime error 246 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 258 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 307 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 235 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 241 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 230 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 239 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 264 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 237 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
54 Runtime error 255 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
55 Runtime error 260 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Runtime error 243 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
57 Runtime error 236 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
58 Runtime error 240 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
59 Runtime error 263 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
60 Runtime error 257 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
61 Runtime error 252 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
62 Runtime error 329 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
63 Runtime error 249 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
64 Runtime error 256 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
65 Runtime error 269 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
66 Runtime error 251 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
67 Runtime error 262 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
68 Runtime error 268 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
69 Runtime error 234 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
70 Runtime error 260 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
71 Runtime error 230 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
72 Runtime error 247 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
73 Runtime error 244 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
74 Runtime error 242 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
75 Runtime error 245 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
76 Runtime error 235 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
77 Runtime error 232 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
78 Runtime error 244 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
79 Runtime error 246 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
80 Runtime error 263 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
81 Runtime error 293 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
82 Runtime error 274 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
83 Runtime error 299 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
84 Runtime error 369 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
85 Runtime error 450 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
86 Runtime error 283 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
87 Runtime error 419 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
88 Runtime error 270 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
89 Runtime error 268 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
90 Runtime error 266 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
91 Runtime error 299 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
92 Runtime error 291 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
93 Runtime error 264 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
94 Runtime error 269 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
95 Runtime error 270 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
96 Runtime error 267 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
97 Runtime error 273 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
98 Runtime error 261 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
99 Runtime error 264 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
100 Runtime error 254 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)