oj.uz

Submission #337892

# Submission time Handle Problem Language Result Execution time Memory
337892 2020-12-22T05:11:25 Z BY_KUTBILIM Bomb (IZhO17_bomb) C++14
0 / 100
 563 ms 113516 KB 
/** @BY_KUTBILIM **/
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define ll long long
#define all(x) ((x).begin(), (x).end())
#define rall(x) ((x).rbegin(), (x).end())

const int inf = (int)1e9+7;

int up[2510][2510], down[2510][2510];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie();

    int n, m;
    cin >> n >> m;
    bool a[n][m];
    char ch;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> ch;
            a[i][j] = bool(ch - '0');
        }
    }
    int W = m, H = n, len;
    for(int i = 0; i < n; i++){
        len = 0;
        for(int j = 0; j < m; j++){
            if(a[i][j])len++;
            else{
                if(len)W = min(W, len);
                len = 0;
            }
        }
        if(len)W = min(W, len);
    }
    for(int j = 0; j < m; j++){
        len = 0;
        for(int i = 0; i < n; i++){
            if(a[i][j])len++;
            else{
                if(len)H = min(H, len);
                len = 0;
            }
        }
        if(len)H = min(H, len);
    }
    
    for(int j = 0; j < m; j++){
        for(int i = 0; i < n; i++){
            if(a[i][j]){
                up[i][j] = (i ? up[i-1][j] : 0) + 1;
            }
        }
        for(int i = n - 1; i >= 0; i--){
            if(a[i][j]){
                down[i][j] = (i < n - 2 ? down[i+1][j] : 0) + 1;
            }
        }
    }
    
    vector<int> ans(W, H);
    int l, r;
    for(int i = 0; i < n; i++){
        l = inf, r = inf, len = 0;
        for(int j = 0; j < m; j++){
            if(a[i][j]){
                r = min(r, up[i][j]);
                l = min(l, down[i][j]);
                ans[len++] = min(ans[len-1], r + l - 1);
            } else len = 0, l = inf, r = inf;
        }
        for(int j = m - 1; j >= 0; j--){
            if(a[i][j]){
                r = min(r, up[i][j]);
                l = min(l, down[i][j]);
                ans[len++] = min(ans[len-1], r + l - 1);
            } else len = 0, l = inf, r = inf;
        }
    }
    int res = ans[0];
    for(int i = 1; i < W; i++){
        ans[i] = min(ans[i], ans[i-1]);
        res = max(res, ans[i] * i);
    }
    cout << res;

    return 0;
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:75:24: warning: operation on 'len' may be undefined [-Wsequence-point]
   75 |                 ans[len++] = min(ans[len-1], r + l - 1);
      |                     ~~~^~
bomb.cpp:82:24: warning: operation on 'len' may be undefined [-Wsequence-point]
   82 |                 ans[len++] = min(ans[len-1], r + l - 1);
      |                     ~~~^~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 492 KB Output isn't correct
3 Incorrect 10 ms 20460 KB Output isn't correct
4 Incorrect 11 ms 20460 KB Output isn't correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Incorrect 1 ms 492 KB Output isn't correct
9 Incorrect 1 ms 492 KB Output isn't correct
10 Incorrect 1 ms 492 KB Output isn't correct
11 Incorrect 1 ms 512 KB Output isn't correct
12 Incorrect 1 ms 492 KB Output isn't correct
13 Incorrect 1 ms 492 KB Output isn't correct
14 Incorrect 1 ms 492 KB Output isn't correct
15 Incorrect 1 ms 512 KB Output isn't correct
16 Incorrect 1 ms 492 KB Output isn't correct
17 Incorrect 1 ms 876 KB Output isn't correct
18 Incorrect 1 ms 620 KB Output isn't correct
19 Incorrect 1 ms 876 KB Output isn't correct
20 Incorrect 1 ms 876 KB Output isn't correct
21 Incorrect 1 ms 492 KB Output isn't correct
22 Incorrect 1 ms 620 KB Output isn't correct
23 Incorrect 1 ms 876 KB Output isn't correct
24 Incorrect 1 ms 876 KB Output isn't correct
25 Incorrect 1 ms 1132 KB Output isn't correct
26 Incorrect 1 ms 1260 KB Output isn't correct
27 Incorrect 5 ms 3436 KB Output isn't correct
28 Incorrect 5 ms 1004 KB Output isn't correct
29 Incorrect 8 ms 4332 KB Output isn't correct
30 Incorrect 8 ms 3564 KB Output isn't correct
31 Incorrect 6 ms 2540 KB Output isn't correct
32 Incorrect 8 ms 3436 KB Output isn't correct
33 Incorrect 10 ms 4588 KB Output isn't correct
34 Incorrect 3 ms 1004 KB Output isn't correct
35 Incorrect 7 ms 1260 KB Output isn't correct
36 Incorrect 11 ms 5996 KB Output isn't correct
37 Incorrect 1 ms 492 KB Output isn't correct
38 Runtime error 563 ms 113516 KB Execution killed with signal 6 (could be triggered by violating memory limits)
39 Incorrect 1 ms 492 KB Output isn't correct
40 Runtime error 84 ms 29036 KB Execution killed with signal 6 (could be triggered by violating memory limits)
41 Incorrect 1 ms 492 KB Output isn't correct
42 Incorrect 1 ms 1260 KB Output isn't correct
43 Runtime error 490 ms 105572 KB Execution killed with signal 6 (could be triggered by violating memory limits)
44 Incorrect 12 ms 5280 KB Output isn't correct
45 Runtime error 500 ms 108012 KB Execution killed with signal 6 (could be triggered by violating memory limits)
46 Incorrect 408 ms 56432 KB Output isn't correct
47 Runtime error 486 ms 108200 KB Execution killed with signal 6 (could be triggered by violating memory limits)
48 Incorrect 412 ms 56684 KB Output isn't correct
49 Incorrect 486 ms 56464 KB Output isn't correct
50 Incorrect 395 ms 56556 KB Output isn't correct
51 Incorrect 398 ms 56408 KB Output isn't correct
52 Incorrect 390 ms 56504 KB Output isn't correct
53 Incorrect 412 ms 55876 KB Output isn't correct
54 Incorrect 320 ms 43116 KB Output isn't correct
55 Incorrect 318 ms 41452 KB Output isn't correct
56 Incorrect 470 ms 56504 KB Output isn't correct
57 Incorrect 319 ms 36436 KB Output isn't correct
58 Incorrect 323 ms 41580 KB Output isn't correct
59 Incorrect 319 ms 38380 KB Output isn't correct
60 Incorrect 378 ms 48296 KB Output isn't correct
61 Incorrect 471 ms 56428 KB Output isn't correct
62 Incorrect 480 ms 56684 KB Output isn't correct
63 Runtime error 547 ms 113516 KB Execution killed with signal 6 (could be triggered by violating memory limits)
64 Incorrect 321 ms 39404 KB Output isn't correct
65 Incorrect 378 ms 55404 KB Output isn't correct
66 Runtime error 464 ms 104940 KB Execution killed with signal 6 (could be triggered by violating memory limits)
67 Runtime error 475 ms 113388 KB Execution killed with signal 6 (could be triggered by violating memory limits)
68 Runtime error 486 ms 113388 KB Execution killed with signal 6 (could be triggered by violating memory limits)
69 Incorrect 319 ms 36204 KB Output isn't correct
70 Runtime error 180 ms 29548 KB Execution killed with signal 6 (could be triggered by violating memory limits)
71 Runtime error 348 ms 57836 KB Execution killed with signal 6 (could be triggered by violating memory limits)
72 Runtime error 379 ms 68844 KB Execution killed with signal 6 (could be triggered by violating memory limits)
73 Runtime error 381 ms 69740 KB Execution killed with signal 6 (could be triggered by violating memory limits)
74 Runtime error 382 ms 72812 KB Execution killed with signal 6 (could be triggered by violating memory limits)
75 Runtime error 397 ms 76396 KB Execution killed with signal 6 (could be triggered by violating memory limits)
76 Runtime error 399 ms 78956 KB Execution killed with signal 6 (could be triggered by violating memory limits)
77 Runtime error 402 ms 79980 KB Execution killed with signal 6 (could be triggered by violating memory limits)
78 Runtime error 413 ms 80356 KB Execution killed with signal 6 (could be triggered by violating memory limits)
79 Incorrect 263 ms 12620 KB Output isn't correct
80 Incorrect 238 ms 14012 KB Output isn't correct
81 Runtime error 281 ms 28140 KB Execution killed with signal 6 (could be triggered by violating memory limits)
82 Runtime error 411 ms 85356 KB Execution killed with signal 6 (could be triggered by violating memory limits)
83 Runtime error 428 ms 85740 KB Execution killed with signal 6 (could be triggered by violating memory limits)
84 Incorrect 238 ms 7916 KB Output isn't correct
85 Runtime error 418 ms 83436 KB Execution killed with signal 6 (could be triggered by violating memory limits)
86 Incorrect 457 ms 55404 KB Output isn't correct
87 Runtime error 413 ms 81312 KB Execution killed with signal 6 (could be triggered by violating memory limits)
88 Runtime error 411 ms 83284 KB Execution killed with signal 6 (could be triggered by violating memory limits)
89 Runtime error 450 ms 101100 KB Execution killed with signal 6 (could be triggered by violating memory limits)
90 Runtime error 250 ms 58476 KB Execution killed with signal 6 (could be triggered by violating memory limits)
91 Runtime error 423 ms 91244 KB Execution killed with signal 6 (could be triggered by violating memory limits)
92 Runtime error 446 ms 94828 KB Execution killed with signal 6 (could be triggered by violating memory limits)
93 Incorrect 449 ms 54636 KB Output isn't correct
94 Runtime error 442 ms 98284 KB Execution killed with signal 6 (could be triggered by violating memory limits)
95 Runtime error 418 ms 85740 KB Execution killed with signal 6 (could be triggered by violating memory limits)
96 Runtime error 423 ms 85356 KB Execution killed with signal 6 (could be triggered by violating memory limits)
97 Incorrect 447 ms 55532 KB Output isn't correct
98 Runtime error 411 ms 84844 KB Execution killed with signal 6 (could be triggered by violating memory limits)
99 Runtime error 443 ms 97584 KB Execution killed with signal 6 (could be triggered by violating memory limits)
100 Incorrect 447 ms 53868 KB Output isn't correct