oj.uz

Submission #706361

# Submission time Handle Problem Language Result Execution time Memory
706361 2023-03-06T10:30:32 Z nifeshe Bomb (IZhO17_bomb) C++17
24 / 100
 830 ms 56384 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define endl '\n'
#define sz(x) (int)((x).size())
#define vec vector
#define pw(x) (1ll << x)

using namespace std;
using namespace __gnu_pbds;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int inf = 1e9 + 17;

inline void solve () {
    int n, m; cin >> n >> m;
    vec <string> a (n);
    for (auto &i : a) cin >> i;

    vec <int> mx (m + 2, inf);

    for (int iter = 0; iter < 2; ++iter) {
        vec <vec <int>> p (n, vec <int> (m)), s (n, vec <int> (m));
        for (int j = 0; j < m; ++j) {
            p[0][j] = (a[0][j] == '1');
            for (int i = 1; i < n; ++i) {
                if (a[i][j] == '1') p[i][j] = p[i - 1][j] + 1;
            }

            s[n - 1][j] = (a[n - 1][j] == '1');
            for (int i = n - 2; ~i; --i) {
                if (a[i][j] == '1') s[i][j] = s[i + 1][j] + 1;
            }

            for (int i = 0; i < n; ++i) if (a[i][j] == '1') umin(mx[1], p[i][j] + s[i][j] - 1);
        }

        for (int i = 0; i < n; ++i) {
            for (int l = 0, r = 0; r < m; ) {
                while (r < m && a[i][r] == '1') ++r;
                if (l == r) {
                    ++l, ++r;
                    continue;
                }

                int mn_down = inf, mn_up = inf;
                for (int q = l; q < r; ++q) {
                    umin(mn_up, p[i][q]);
                    umin(mn_down, s[i][q]);
                    umin(mx[q - l + 1], mn_down + mn_up - 1);
                }
                umin(mx[r - l + 1], 0);

                l = r;
            }
        }

        for (auto &i : a) reverse(all(i));
    }

    int ans = 0;
    bool ok = 0;
    for (int i = 1; i <= m; ++i) {
        umin(mx[i], mx[i - 1]);
        assert(mx[i] == mx[1] || mx[i] == 0);
        umax(ans, mx[i] * i);
    }
    cout << ans << endl;
}

signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif// LOCAL
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message

bomb.cpp: In function 'void solve()':
bomb.cpp:74:10: warning: unused variable 'ok' [-Wunused-variable]
   74 |     bool ok = 0;
      |          ^~

Subtask #1
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Runtime error 1 ms 468 KB Execution killed with signal 6
9 Runtime error 1 ms 468 KB Execution killed with signal 6
10 Runtime error 1 ms 468 KB Execution killed with signal 6
11 Runtime error 1 ms 468 KB Execution killed with signal 6
12 Runtime error 1 ms 468 KB Execution killed with signal 6
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Runtime error 1 ms 468 KB Execution killed with signal 6
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Runtime error 1 ms 596 KB Execution killed with signal 6
19 Runtime error 1 ms 596 KB Execution killed with signal 6
20 Runtime error 2 ms 596 KB Execution killed with signal 6
21 Runtime error 2 ms 596 KB Execution killed with signal 6
22 Runtime error 1 ms 596 KB Execution killed with signal 6
23 Runtime error 1 ms 596 KB Execution killed with signal 6
24 Runtime error 1 ms 596 KB Execution killed with signal 6
25 Runtime error 1 ms 596 KB Execution killed with signal 6
26 Correct 1 ms 340 KB Output is correct
27 Correct 4 ms 980 KB Output is correct
28 Runtime error 3 ms 1240 KB Execution killed with signal 6
29 Runtime error 6 ms 1380 KB Execution killed with signal 6
30 Runtime error 7 ms 2004 KB Execution killed with signal 6
31 Runtime error 6 ms 1676 KB Execution killed with signal 6
32 Runtime error 5 ms 1748 KB Execution killed with signal 6
33 Runtime error 6 ms 2132 KB Execution killed with signal 6
34 Runtime error 3 ms 1612 KB Execution killed with signal 6
35 Runtime error 5 ms 2132 KB Execution killed with signal 6
36 Correct 8 ms 2132 KB Output is correct
37 Runtime error 1 ms 468 KB Execution killed with signal 6
38 Correct 830 ms 56164 KB Output is correct
39 Runtime error 2 ms 468 KB Execution killed with signal 6
40 Runtime error 69 ms 7264 KB Execution killed with signal 6
41 Runtime error 1 ms 480 KB Execution killed with signal 6
42 Runtime error 1 ms 596 KB Execution killed with signal 6
43 Correct 548 ms 56140 KB Output is correct
44 Runtime error 7 ms 2132 KB Execution killed with signal 6
45 Runtime error 527 ms 56224 KB Execution killed with signal 6
46 Correct 519 ms 56160 KB Output is correct
47 Runtime error 536 ms 56160 KB Execution killed with signal 6
48 Runtime error 477 ms 56176 KB Execution killed with signal 6
49 Correct 670 ms 56244 KB Output is correct
50 Runtime error 499 ms 56164 KB Execution killed with signal 6
51 Runtime error 480 ms 56160 KB Execution killed with signal 6
52 Runtime error 537 ms 56160 KB Execution killed with signal 6
53 Runtime error 479 ms 56196 KB Execution killed with signal 6
54 Runtime error 446 ms 56168 KB Execution killed with signal 6
55 Runtime error 337 ms 56168 KB Execution killed with signal 6
56 Correct 671 ms 56144 KB Output is correct
57 Runtime error 376 ms 56164 KB Execution killed with signal 6
58 Runtime error 326 ms 56168 KB Execution killed with signal 6
59 Runtime error 410 ms 56140 KB Execution killed with signal 6
60 Correct 456 ms 56160 KB Output is correct
61 Correct 756 ms 56184 KB Output is correct
62 Correct 712 ms 56160 KB Output is correct
63 Correct 729 ms 56168 KB Output is correct
64 Correct 336 ms 56168 KB Output is correct
65 Runtime error 495 ms 56240 KB Execution killed with signal 6
66 Runtime error 465 ms 56240 KB Execution killed with signal 6
67 Runtime error 507 ms 56164 KB Execution killed with signal 6
68 Runtime error 580 ms 56160 KB Execution killed with signal 6
69 Runtime error 333 ms 56140 KB Execution killed with signal 6
70 Runtime error 129 ms 36068 KB Execution killed with signal 6
71 Runtime error 291 ms 56212 KB Execution killed with signal 6
72 Runtime error 405 ms 56164 KB Execution killed with signal 6
73 Runtime error 362 ms 56204 KB Execution killed with signal 6
74 Runtime error 346 ms 56168 KB Execution killed with signal 6
75 Runtime error 381 ms 56384 KB Execution killed with signal 6
76 Runtime error 395 ms 56272 KB Execution killed with signal 6
77 Runtime error 401 ms 56212 KB Execution killed with signal 6
78 Runtime error 366 ms 56272 KB Execution killed with signal 6
79 Runtime error 214 ms 56164 KB Execution killed with signal 6
80 Runtime error 199 ms 56144 KB Execution killed with signal 6
81 Runtime error 241 ms 56244 KB Execution killed with signal 6
82 Runtime error 369 ms 56164 KB Execution killed with signal 6
83 Runtime error 366 ms 56156 KB Execution killed with signal 6
84 Runtime error 193 ms 56184 KB Execution killed with signal 6
85 Runtime error 328 ms 56112 KB Execution killed with signal 6
86 Runtime error 645 ms 56160 KB Execution killed with signal 6
87 Runtime error 363 ms 56192 KB Execution killed with signal 6
88 Runtime error 370 ms 56192 KB Execution killed with signal 6
89 Runtime error 453 ms 56304 KB Execution killed with signal 6
90 Runtime error 175 ms 36072 KB Execution killed with signal 6
91 Runtime error 380 ms 56184 KB Execution killed with signal 6
92 Runtime error 431 ms 56168 KB Execution killed with signal 6
93 Runtime error 664 ms 56212 KB Execution killed with signal 6
94 Runtime error 439 ms 56196 KB Execution killed with signal 6
95 Runtime error 382 ms 56208 KB Execution killed with signal 6
96 Runtime error 375 ms 56252 KB Execution killed with signal 6
97 Runtime error 627 ms 56188 KB Execution killed with signal 6
98 Runtime error 377 ms 56164 KB Execution killed with signal 6
99 Runtime error 459 ms 56188 KB Execution killed with signal 6
100 Runtime error 630 ms 56160 KB Execution killed with signal 6