oj.uz

답안 #1030389

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1030389 2024-07-22T04:27:14 Z caterpillow Bomb (IZhO17_bomb) C++17
35 / 100
 1000 ms 57152 KB 
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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];
}

    
bool check(int w, int h) {
    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);
    };

    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) {
                if (!is_covered(r, c)) return false;
            }
        }
    }
    return true;
}

int ans = 0;

void solve(int mnh, int mxh, int mnw, int mxw) {
    if (mxh < mnh || mxw < mnw) return;
    int h = (mnh + mxh) / 2;
    int lo = mnw - 1, hi = mxw + 1;
    while (hi - lo > 1) {
        if (h * (hi - 1) <= ans) return;
        int w = (lo + hi) / 2;
        if (check(w, h)) lo = w;
        else hi = w;
    }
    ans = max(ans, h * lo);
    solve(mnh, h - 1, lo, mxw);
    solve(h + 1, mxh, mnw, lo);
}

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];

    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;
        }
    }

    solve(1, mxh, 1, mxw);
    cout << ans << endl;
}

Compilation message

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

Subtask #1
35.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 352 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 1 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 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 Incorrect 1 ms 352 KB Output isn't correct
20 Incorrect 1 ms 348 KB Output isn't correct
21 Correct 0 ms 352 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 2 ms 456 KB Output is correct
24 Incorrect 1 ms 348 KB Output isn't correct
25 Incorrect 1 ms 452 KB Output isn't correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 3 ms 1176 KB Output is correct
28 Correct 5 ms 1436 KB Output is correct
29 Correct 15 ms 1620 KB Output is correct
30 Incorrect 14 ms 2168 KB Output isn't correct
31 Incorrect 10 ms 1828 KB Output isn't correct
32 Incorrect 11 ms 1892 KB Output isn't correct
33 Incorrect 16 ms 2312 KB Output isn't correct
34 Correct 5 ms 1220 KB Output is correct
35 Incorrect 18 ms 2320 KB Output isn't correct
36 Correct 41 ms 2360 KB Output is correct
37 Incorrect 0 ms 348 KB Output isn't correct
38 Execution timed out 1101 ms 56704 KB Time limit exceeded
39 Correct 0 ms 348 KB Output is correct
40 Incorrect 62 ms 7440 KB Output isn't correct
41 Correct 1 ms 344 KB Output is correct
42 Incorrect 1 ms 348 KB Output isn't correct
43 Execution timed out 1099 ms 56972 KB Time limit exceeded
44 Incorrect 14 ms 2300 KB Output isn't correct
45 Incorrect 308 ms 56748 KB Output isn't correct
46 Correct 979 ms 56700 KB Output is correct
47 Incorrect 340 ms 56740 KB Output isn't correct
48 Execution timed out 1062 ms 56744 KB Time limit exceeded
49 Correct 435 ms 56700 KB Output is correct
50 Execution timed out 1020 ms 56912 KB Time limit exceeded
51 Execution timed out 1078 ms 56652 KB Time limit exceeded
52 Execution timed out 1102 ms 56700 KB Time limit exceeded
53 Execution timed out 1026 ms 56716 KB Time limit exceeded
54 Execution timed out 1081 ms 56700 KB Time limit exceeded
55 Execution timed out 1025 ms 56700 KB Time limit exceeded
56 Execution timed out 1008 ms 56828 KB Time limit exceeded
57 Execution timed out 1053 ms 56700 KB Time limit exceeded
58 Execution timed out 1026 ms 56720 KB Time limit exceeded
59 Execution timed out 1074 ms 56700 KB Time limit exceeded
60 Correct 837 ms 56700 KB Output is correct
61 Execution timed out 1012 ms 56700 KB Time limit exceeded
62 Execution timed out 1074 ms 56724 KB Time limit exceeded
63 Execution timed out 1041 ms 56852 KB Time limit exceeded
64 Execution timed out 1040 ms 57152 KB Time limit exceeded
65 Execution timed out 1014 ms 56696 KB Time limit exceeded
66 Execution timed out 1072 ms 56724 KB Time limit exceeded
67 Execution timed out 1044 ms 56732 KB Time limit exceeded
68 Execution timed out 1025 ms 56700 KB Time limit exceeded
69 Execution timed out 1071 ms 56796 KB Time limit exceeded
70 Incorrect 487 ms 36480 KB Output isn't correct
71 Incorrect 457 ms 56740 KB Output isn't correct
72 Incorrect 343 ms 56700 KB Output isn't correct
73 Incorrect 452 ms 56940 KB Output isn't correct
74 Incorrect 629 ms 56780 KB Output isn't correct
75 Execution timed out 1045 ms 56724 KB Time limit exceeded
76 Incorrect 620 ms 56740 KB Output isn't correct
77 Incorrect 559 ms 56788 KB Output isn't correct
78 Incorrect 608 ms 56740 KB Output isn't correct
79 Incorrect 315 ms 56700 KB Output isn't correct
80 Incorrect 299 ms 56744 KB Output isn't correct
81 Incorrect 473 ms 56748 KB Output isn't correct
82 Execution timed out 1042 ms 57004 KB Time limit exceeded
83 Incorrect 573 ms 56788 KB Output isn't correct
84 Incorrect 360 ms 56820 KB Output isn't correct
85 Incorrect 512 ms 56748 KB Output isn't correct
86 Incorrect 400 ms 56948 KB Output isn't correct
87 Incorrect 567 ms 56792 KB Output isn't correct
88 Incorrect 586 ms 56944 KB Output isn't correct
89 Incorrect 420 ms 56760 KB Output isn't correct
90 Incorrect 351 ms 36568 KB Output isn't correct
91 Incorrect 576 ms 57056 KB Output isn't correct
92 Incorrect 695 ms 56832 KB Output isn't correct
93 Correct 289 ms 56744 KB Output is correct
94 Correct 683 ms 56800 KB Output is correct
95 Incorrect 608 ms 56788 KB Output isn't correct
96 Incorrect 588 ms 56656 KB Output isn't correct
97 Correct 332 ms 56788 KB Output is correct
98 Incorrect 653 ms 56760 KB Output isn't correct
99 Incorrect 520 ms 56836 KB Output isn't correct
100 Incorrect 452 ms 56784 KB Output isn't correct