oj.uz

Submission #1030382

# Submission time Handle Problem Language Result Execution time Memory
1030382 2024-07-22T04:14:48 Z caterpillow Bomb (IZhO17_bomb) C++17
29 / 100
 1000 ms 2412 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'

#ifndef LOCAL
#define cerr if (0) std::cerr
#endif

/*

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) {
    r2 = min(r2, rs - 1);
    c2 = min(c2, cs - 1);
    return sfx[r1][c1] - sfx[r1][c2 + 1] - sfx[r2 + 1][c1] + sfx[r2 + 1][c2 + 1];
}

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

    cin >> rs >> cs;
    if (rs > 450 || cs > 450) return 0;
    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];

    int mxw = cs, mxh = rs;
    F0R (r, rs) {
        int streak = 0;
        F0R (c, cs) {
            if (grid[r][c]) streak++;
            else if (streak) mxw = min(mxw, streak), streak = 0;
        }
    }
    F0R (c, cs) {
        int streak = 0;
        F0R (r, rs) {
            if (grid[r][c]) streak++;
            else if (streak) mxh = min(mxh, streak), streak = 0;
        }
    }

    cerr << mxw << " " << mxh << endl;

    int best = 0;
    FOR (h, 1, mxh + 1) {
        FOR (w, 1, mxw + 1) {
            vt<vt<int>> pfx(rs, vt<int>(cs));
            auto is_covered = [&] (int r, int c) {
                return (pfx[r][c] - (r - h >= 0 ? pfx[r - h][c] : 0) - (c - w >= 0 ? pfx[r][c - w] : 0) + (r - h >= 0 && c - w >= 0 ? pfx[r - h][c - w] : 0)) > 0;
            };
            auto add = [&] (int r, int c) {
                pfx[r][c] += (r ? pfx[r - 1][c] : 0) + (c ? pfx[r][c - 1] : 0) - (r && c ? pfx[r - 1][c - 1] : 0);
            };

            cerr << w << " " << h << endl;

            bool good = true;
            F0R (r, rs - 1) {
                F0R (c, cs - 1) {
                    if (sum(r, c, r + h - 1, c + w - 1) == w * h) {
                        pfx[r][c]++;
                    }
                    add(r, c);
                    if (grid[r][c] == 1) {
                        cerr << is_covered(r, c) << endl;
                        good &= is_covered(r, c);
                    }
                }
            }
            if (good) best = max(best, w * h);
        }
    }
    cout << best << endl;
}

Compilation message

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

Subtask #1
29.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 432 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 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 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 12 ms 516 KB Output is correct
20 Correct 12 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 33 ms 348 KB Output is correct
24 Correct 15 ms 696 KB Output is correct
25 Correct 53 ms 348 KB Output is correct
26 Correct 8 ms 348 KB Output is correct
27 Correct 4 ms 1180 KB Output is correct
28 Correct 45 ms 1448 KB Output is correct
29 Execution timed out 1055 ms 1592 KB Time limit exceeded
30 Execution timed out 1060 ms 2168 KB Time limit exceeded
31 Execution timed out 1039 ms 1844 KB Time limit exceeded
32 Execution timed out 1037 ms 2020 KB Time limit exceeded
33 Execution timed out 1057 ms 2316 KB Time limit exceeded
34 Correct 40 ms 1220 KB Output is correct
35 Execution timed out 1031 ms 2296 KB Time limit exceeded
36 Execution timed out 1027 ms 2412 KB Time limit exceeded
37 Correct 1 ms 344 KB Output is correct
38 Incorrect 1 ms 348 KB Output isn't correct
39 Correct 1 ms 432 KB Output is correct
40 Incorrect 0 ms 348 KB Output isn't correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 146 ms 520 KB Output is correct
43 Incorrect 0 ms 344 KB Output isn't correct
44 Execution timed out 1090 ms 2320 KB Time limit exceeded
45 Incorrect 0 ms 344 KB Output isn't correct
46 Incorrect 0 ms 348 KB Output isn't correct
47 Incorrect 0 ms 348 KB Output isn't correct
48 Incorrect 0 ms 348 KB Output isn't correct
49 Incorrect 0 ms 348 KB Output isn't correct
50 Incorrect 0 ms 348 KB Output isn't correct
51 Incorrect 0 ms 348 KB Output isn't correct
52 Incorrect 0 ms 348 KB Output isn't correct
53 Incorrect 0 ms 348 KB Output isn't correct
54 Incorrect 1 ms 348 KB Output isn't correct
55 Incorrect 0 ms 344 KB Output isn't correct
56 Incorrect 0 ms 348 KB Output isn't correct
57 Incorrect 0 ms 348 KB Output isn't correct
58 Incorrect 0 ms 348 KB Output isn't correct
59 Incorrect 0 ms 348 KB Output isn't correct
60 Incorrect 0 ms 348 KB Output isn't correct
61 Incorrect 0 ms 348 KB Output isn't correct
62 Incorrect 0 ms 344 KB Output isn't correct
63 Incorrect 0 ms 348 KB Output isn't correct
64 Incorrect 0 ms 348 KB Output isn't correct
65 Incorrect 0 ms 348 KB Output isn't correct
66 Incorrect 0 ms 344 KB Output isn't correct
67 Incorrect 0 ms 348 KB Output isn't correct
68 Incorrect 0 ms 348 KB Output isn't correct
69 Incorrect 0 ms 348 KB Output isn't correct
70 Incorrect 0 ms 348 KB Output isn't correct
71 Incorrect 0 ms 348 KB Output isn't correct
72 Incorrect 0 ms 348 KB Output isn't correct
73 Incorrect 0 ms 348 KB Output isn't correct
74 Incorrect 0 ms 348 KB Output isn't correct
75 Incorrect 0 ms 348 KB Output isn't correct
76 Incorrect 0 ms 348 KB Output isn't correct
77 Incorrect 0 ms 348 KB Output isn't correct
78 Incorrect 0 ms 348 KB Output isn't correct
79 Incorrect 0 ms 348 KB Output isn't correct
80 Incorrect 1 ms 344 KB Output isn't correct
81 Incorrect 0 ms 348 KB Output isn't correct
82 Incorrect 0 ms 348 KB Output isn't correct
83 Incorrect 1 ms 348 KB Output isn't correct
84 Incorrect 1 ms 348 KB Output isn't correct
85 Incorrect 0 ms 348 KB Output isn't correct
86 Incorrect 0 ms 348 KB Output isn't correct
87 Incorrect 0 ms 348 KB Output isn't correct
88 Incorrect 0 ms 348 KB Output isn't correct
89 Incorrect 0 ms 348 KB Output isn't correct
90 Incorrect 0 ms 344 KB Output isn't correct
91 Incorrect 0 ms 348 KB Output isn't correct
92 Incorrect 0 ms 348 KB Output isn't correct
93 Incorrect 1 ms 348 KB Output isn't correct
94 Incorrect 0 ms 348 KB Output isn't correct
95 Incorrect 0 ms 348 KB Output isn't correct
96 Incorrect 0 ms 348 KB Output isn't correct
97 Incorrect 0 ms 348 KB Output isn't correct
98 Incorrect 0 ms 344 KB Output isn't correct
99 Incorrect 1 ms 344 KB Output isn't correct
100 Incorrect 0 ms 600 KB Output isn't correct