oj.uz

Submission #1030364

# Submission time Handle Problem Language Result Execution time Memory
1030364 2024-07-22T03:41:02 Z caterpillow Bomb (IZhO17_bomb) C++17
29 / 100
 1000 ms 33288 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define vt vector
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b)  for (int i = (a); i < (b); i++)
#define F0R(i, b) FOR(i, 0, b)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define pb push_back
#define endl '\n'

/*

N^3: find max width for each given height

*/

int rs, cs;
vt<vt<bool>> grid;
vt<vt<int>> sfx;

int sum(int r1, int c1, int r2, int c2) {
    return sfx[r1][c1] - sfx[r1][c2 + 1] - sfx[r2 + 1][c1] + sfx[r2 + 1][c2 + 1];
}

int mx(int h) {
    // cerr << "\nchecking " << h << endl;
    // check if possible
    // F0R (r, rs - h + 1) {
    //     F0R (c, cs) {
    //         int s = sum(r, c, r + h - 1, c);
    //         if (0 < s && s < h) return 0;
    //     }
    // }

    // find longest run
    vt<vt<bool>> mod(rs - h + 1, vt<bool>(cs));
    F0R (r, rs - h + 1) {
        F0R (c, cs) {
            mod[r][c] = sum(r, c, r + h - 1, c) == h;
        }
    }

    // F0R (r, rs - h + 1) {
    //     F0R (c, cs) {
    //         cerr << mod[r][c] << " \n"[c == cs - 1];
    //     }
    // }

    int mn = cs;
    F0R (r, rs - h + 1) {
        int streak = 0;
        F0R (c, cs) {
            if (mod[r][c]) streak++;
            else {
                if (streak) mn = min(mn, streak), streak = 0;
            }
        }
        if (streak) mn = min(mn, streak);
    }
    return mn;
}

main() {
    cin.tie(0)->sync_with_stdio();

    cin >> rs >> cs;
    rs += 2, cs += 2;
    grid.resize(rs, vt<bool>(cs));
    sfx.resize(rs + 1, vt<int>(cs + 1));
    FOR (r, 1, rs - 1) {
        FOR (c, 1, cs - 1) {
            char ch; cin >> ch;
            grid[r][c] = sfx[r][c] = ch - '0';
        }
    }
    ROF (r, 0, rs) ROF (c, 0, cs) sfx[r][c] += sfx[r][c + 1];
    ROF (r, 0, rs) ROF (c, 0, cs) sfx[r][c] += sfx[r + 1][c];

    // calculate maximum height
    int mxh = rs;
    vt<int> run(cs);
    F0R (r, rs) {
        F0R (c, cs) {
            if (grid[r][c] == 0) {
                if (run[c] != 0) {
                    mxh = min(mxh, run[c]);
                    run[c] = 0;
                }
            } else {
                run[c]++;
            }
        }
    }

    // cerr << "maximum height " << mxh << endl;

    // F0R (r, rs) {
    //     F0R (c, cs) {
    //         cerr << grid[r][c] << " \n"[c == cs - 1];
    //     }
    // }

    int ans = 0;
    FOR (h, 1, mxh + 1) {
        ans = max(ans, h * mx(h));
    }
    cout << ans << endl;
}

Compilation message

bomb.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main() {
      | ^~~~
bomb.cpp: In function 'int main()':
bomb.cpp:78:36: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   78 |             grid[r][c] = sfx[r][c] = ch - '0';

Subtask #1
29.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 5 ms 928 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Incorrect 1 ms 348 KB Output isn't correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Incorrect 1 ms 348 KB Output isn't correct
24 Incorrect 1 ms 348 KB Output isn't correct
25 Incorrect 2 ms 348 KB Output isn't correct
26 Incorrect 1 ms 348 KB Output isn't correct
27 Correct 2 ms 836 KB Output is correct
28 Correct 5 ms 860 KB Output is correct
29 Incorrect 33 ms 1116 KB Output isn't correct
30 Incorrect 65 ms 1372 KB Output isn't correct
31 Incorrect 36 ms 1116 KB Output isn't correct
32 Incorrect 52 ms 1116 KB Output isn't correct
33 Incorrect 84 ms 1628 KB Output isn't correct
34 Correct 5 ms 860 KB Output is correct
35 Incorrect 17 ms 1508 KB Output isn't correct
36 Incorrect 38 ms 1376 KB Output isn't correct
37 Incorrect 1 ms 348 KB Output isn't correct
38 Execution timed out 1038 ms 33164 KB Time limit exceeded
39 Incorrect 1 ms 348 KB Output isn't correct
40 Incorrect 730 ms 4528 KB Output isn't correct
41 Incorrect 0 ms 348 KB Output isn't correct
42 Incorrect 2 ms 504 KB Output isn't correct
43 Execution timed out 1071 ms 33060 KB Time limit exceeded
44 Incorrect 115 ms 1372 KB Output isn't correct
45 Execution timed out 1049 ms 33004 KB Time limit exceeded
46 Correct 595 ms 33008 KB Output is correct
47 Execution timed out 1020 ms 33144 KB Time limit exceeded
48 Incorrect 989 ms 33016 KB Output isn't correct
49 Correct 267 ms 33004 KB Output is correct
50 Incorrect 909 ms 33004 KB Output isn't correct
51 Incorrect 966 ms 33268 KB Output isn't correct
52 Execution timed out 1039 ms 33028 KB Time limit exceeded
53 Incorrect 996 ms 33112 KB Output isn't correct
54 Execution timed out 1022 ms 33012 KB Time limit exceeded
55 Execution timed out 1043 ms 33004 KB Time limit exceeded
56 Execution timed out 1061 ms 33256 KB Time limit exceeded
57 Correct 857 ms 33004 KB Output is correct
58 Execution timed out 1038 ms 33192 KB Time limit exceeded
59 Execution timed out 1035 ms 33288 KB Time limit exceeded
60 Correct 713 ms 33004 KB Output is correct
61 Correct 548 ms 33136 KB Output is correct
62 Execution timed out 1038 ms 33016 KB Time limit exceeded
63 Execution timed out 1040 ms 33148 KB Time limit exceeded
64 Execution timed out 1036 ms 33256 KB Time limit exceeded
65 Execution timed out 1066 ms 33008 KB Time limit exceeded
66 Incorrect 332 ms 33076 KB Output isn't correct
67 Incorrect 884 ms 33172 KB Output isn't correct
68 Incorrect 926 ms 33008 KB Output isn't correct
69 Correct 813 ms 33008 KB Output is correct
70 Execution timed out 1054 ms 21436 KB Time limit exceeded
71 Execution timed out 1070 ms 33012 KB Time limit exceeded
72 Execution timed out 1058 ms 33000 KB Time limit exceeded
73 Execution timed out 1031 ms 33008 KB Time limit exceeded
74 Execution timed out 1047 ms 33020 KB Time limit exceeded
75 Execution timed out 1025 ms 33064 KB Time limit exceeded
76 Execution timed out 1043 ms 33016 KB Time limit exceeded
77 Execution timed out 1006 ms 33036 KB Time limit exceeded
78 Execution timed out 1070 ms 33008 KB Time limit exceeded
79 Execution timed out 1059 ms 33004 KB Time limit exceeded
80 Execution timed out 1060 ms 33004 KB Time limit exceeded
81 Execution timed out 1068 ms 33004 KB Time limit exceeded
82 Execution timed out 1054 ms 33064 KB Time limit exceeded
83 Execution timed out 1047 ms 33008 KB Time limit exceeded
84 Incorrect 505 ms 33008 KB Output isn't correct
85 Execution timed out 1044 ms 33116 KB Time limit exceeded
86 Correct 777 ms 33016 KB Output is correct
87 Execution timed out 1051 ms 33188 KB Time limit exceeded
88 Execution timed out 1016 ms 33016 KB Time limit exceeded
89 Execution timed out 1039 ms 33012 KB Time limit exceeded
90 Execution timed out 1061 ms 21416 KB Time limit exceeded
91 Execution timed out 1033 ms 33224 KB Time limit exceeded
92 Execution timed out 1033 ms 33004 KB Time limit exceeded
93 Execution timed out 1065 ms 33032 KB Time limit exceeded
94 Execution timed out 1055 ms 33256 KB Time limit exceeded
95 Execution timed out 1031 ms 33004 KB Time limit exceeded
96 Execution timed out 1067 ms 33004 KB Time limit exceeded
97 Incorrect 842 ms 33008 KB Output isn't correct
98 Execution timed out 1066 ms 33004 KB Time limit exceeded
99 Execution timed out 1076 ms 33244 KB Time limit exceeded
100 Execution timed out 1045 ms 33264 KB Time limit exceeded