oj.uz

Submission #706339

# Submission time Handle Problem Language Result Execution time Memory
706339 2023-03-06T09:43:29 Z KiriLL1ca Bomb (IZhO17_bomb) C++17
0 / 100
 695 ms 58088 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) umax(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;
    for (int i = 1; i <= m; ++i) {
        umin(mx[i], mx[i - 1]);
        cout << mx[i] << " " << i << endl;
        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;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Incorrect 1 ms 596 KB Output isn't correct
4 Incorrect 1 ms 596 KB Output isn't correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Incorrect 1 ms 256 KB Output isn't correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Incorrect 0 ms 212 KB Output isn't correct
13 Incorrect 0 ms 212 KB Output isn't correct
14 Incorrect 1 ms 212 KB Output isn't correct
15 Incorrect 1 ms 256 KB Output isn't correct
16 Incorrect 0 ms 212 KB Output isn't correct
17 Incorrect 1 ms 340 KB Output isn't correct
18 Incorrect 1 ms 340 KB Output isn't correct
19 Incorrect 1 ms 340 KB Output isn't correct
20 Incorrect 1 ms 340 KB Output isn't correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Incorrect 1 ms 340 KB Output isn't correct
23 Incorrect 1 ms 340 KB Output isn't correct
24 Incorrect 1 ms 340 KB Output isn't correct
25 Incorrect 1 ms 340 KB Output isn't correct
26 Incorrect 1 ms 340 KB Output isn't correct
27 Incorrect 3 ms 980 KB Output isn't correct
28 Incorrect 3 ms 1236 KB Output isn't correct
29 Incorrect 4 ms 1380 KB Output isn't correct
30 Incorrect 5 ms 2004 KB Output isn't correct
31 Incorrect 4 ms 1620 KB Output isn't correct
32 Incorrect 11 ms 1748 KB Output isn't correct
33 Incorrect 5 ms 2132 KB Output isn't correct
34 Incorrect 2 ms 1040 KB Output isn't correct
35 Incorrect 5 ms 2132 KB Output isn't correct
36 Incorrect 7 ms 2132 KB Output isn't correct
37 Incorrect 1 ms 212 KB Output isn't correct
38 Incorrect 628 ms 56168 KB Output isn't correct
39 Incorrect 1 ms 212 KB Output isn't correct
40 Incorrect 40 ms 7252 KB Output isn't correct
41 Incorrect 1 ms 212 KB Output isn't correct
42 Incorrect 1 ms 340 KB Output isn't correct
43 Incorrect 497 ms 56188 KB Output isn't correct
44 Incorrect 6 ms 2132 KB Output isn't correct
45 Incorrect 515 ms 56160 KB Output isn't correct
46 Incorrect 514 ms 56168 KB Output isn't correct
47 Incorrect 523 ms 56236 KB Output isn't correct
48 Incorrect 482 ms 56164 KB Output isn't correct
49 Incorrect 562 ms 56164 KB Output isn't correct
50 Incorrect 491 ms 56164 KB Output isn't correct
51 Incorrect 500 ms 56164 KB Output isn't correct
52 Incorrect 546 ms 56168 KB Output isn't correct
53 Incorrect 572 ms 56164 KB Output isn't correct
54 Incorrect 470 ms 56172 KB Output isn't correct
55 Incorrect 473 ms 56168 KB Output isn't correct
56 Incorrect 622 ms 56188 KB Output isn't correct
57 Incorrect 485 ms 56168 KB Output isn't correct
58 Incorrect 448 ms 56168 KB Output isn't correct
59 Incorrect 500 ms 56160 KB Output isn't correct
60 Incorrect 511 ms 56164 KB Output isn't correct
61 Incorrect 660 ms 56156 KB Output isn't correct
62 Incorrect 654 ms 56164 KB Output isn't correct
63 Incorrect 632 ms 56196 KB Output isn't correct
64 Incorrect 476 ms 56264 KB Output isn't correct
65 Incorrect 594 ms 56160 KB Output isn't correct
66 Incorrect 525 ms 56164 KB Output isn't correct
67 Incorrect 680 ms 56172 KB Output isn't correct
68 Incorrect 695 ms 56160 KB Output isn't correct
69 Incorrect 492 ms 56164 KB Output isn't correct
70 Incorrect 256 ms 36068 KB Output isn't correct
71 Incorrect 463 ms 56252 KB Output isn't correct
72 Incorrect 487 ms 56160 KB Output isn't correct
73 Incorrect 538 ms 56164 KB Output isn't correct
74 Incorrect 486 ms 56168 KB Output isn't correct
75 Incorrect 553 ms 56168 KB Output isn't correct
76 Incorrect 656 ms 57188 KB Output isn't correct
77 Incorrect 657 ms 57192 KB Output isn't correct
78 Incorrect 619 ms 57708 KB Output isn't correct
79 Incorrect 558 ms 57712 KB Output isn't correct
80 Incorrect 427 ms 57696 KB Output isn't correct
81 Incorrect 480 ms 57704 KB Output isn't correct
82 Incorrect 592 ms 57980 KB Output isn't correct
83 Incorrect 543 ms 58080 KB Output isn't correct
84 Incorrect 461 ms 58008 KB Output isn't correct
85 Incorrect 542 ms 58088 KB Output isn't correct
86 Incorrect 682 ms 57956 KB Output isn't correct
87 Incorrect 514 ms 57812 KB Output isn't correct
88 Incorrect 534 ms 57700 KB Output isn't correct
89 Incorrect 577 ms 57760 KB Output isn't correct
90 Incorrect 328 ms 37600 KB Output isn't correct
91 Incorrect 541 ms 57776 KB Output isn't correct
92 Incorrect 596 ms 57676 KB Output isn't correct
93 Incorrect 687 ms 57792 KB Output isn't correct
94 Incorrect 576 ms 57656 KB Output isn't correct
95 Incorrect 528 ms 57656 KB Output isn't correct
96 Incorrect 519 ms 57452 KB Output isn't correct
97 Incorrect 673 ms 57316 KB Output isn't correct
98 Incorrect 548 ms 56548 KB Output isn't correct
99 Incorrect 585 ms 56188 KB Output isn't correct
100 Incorrect 693 ms 56208 KB Output isn't correct