oj.uz

Submission #706326

# Submission time Handle Problem Language Result Execution time Memory
706326 2023-03-06T09:29:33 Z KiriLL1ca Bomb (IZhO17_bomb) C++17
70 / 100
 533 ms 58344 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 < n; ++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) {
            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]);
        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
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Runtime error 2 ms 1060 KB Execution killed with signal 11
4 Runtime error 2 ms 1120 KB Execution killed with signal 11
5 Incorrect 0 ms 340 KB Output isn't correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Runtime error 1 ms 468 KB Execution killed with signal 6
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Incorrect 1 ms 340 KB Output isn't correct
18 Runtime error 1 ms 468 KB Execution killed with signal 6
19 Runtime error 1 ms 596 KB Execution killed with signal 6
20 Runtime error 1 ms 596 KB Execution killed with signal 6
21 Incorrect 1 ms 340 KB Output isn't correct
22 Incorrect 1 ms 340 KB Output isn't correct
23 Correct 1 ms 340 KB Output is correct
24 Runtime error 1 ms 596 KB Execution killed with signal 6
25 Correct 1 ms 340 KB Output is correct
26 Incorrect 1 ms 340 KB Output isn't correct
27 Runtime error 3 ms 1876 KB Execution killed with signal 6
28 Incorrect 2 ms 1240 KB Output isn't correct
29 Runtime error 4 ms 2772 KB Execution killed with signal 6
30 Correct 6 ms 2004 KB Output is correct
31 Incorrect 4 ms 1620 KB Output isn't correct
32 Runtime error 6 ms 3284 KB Execution killed with signal 6
33 Correct 5 ms 2132 KB Output is correct
34 Runtime error 3 ms 2004 KB Execution killed with signal 6
35 Correct 4 ms 2132 KB Output is correct
36 Incorrect 8 ms 2132 KB Output isn't correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 422 ms 56156 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Incorrect 42 ms 7256 KB Output isn't correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 368 ms 56168 KB Output is correct
44 Correct 5 ms 2132 KB Output is correct
45 Correct 335 ms 56164 KB Output is correct
46 Correct 375 ms 56156 KB Output is correct
47 Correct 400 ms 56172 KB Output is correct
48 Correct 367 ms 56216 KB Output is correct
49 Incorrect 496 ms 56420 KB Output isn't correct
50 Correct 373 ms 56676 KB Output is correct
51 Correct 394 ms 56676 KB Output is correct
52 Correct 356 ms 56932 KB Output is correct
53 Correct 382 ms 56928 KB Output is correct
54 Correct 315 ms 57260 KB Output is correct
55 Correct 301 ms 57252 KB Output is correct
56 Correct 504 ms 57256 KB Output is correct
57 Correct 314 ms 57488 KB Output is correct
58 Correct 286 ms 57756 KB Output is correct
59 Correct 246 ms 57764 KB Output is correct
60 Incorrect 371 ms 57956 KB Output isn't correct
61 Incorrect 533 ms 58212 KB Output isn't correct
62 Incorrect 503 ms 58248 KB Output isn't correct
63 Incorrect 509 ms 58344 KB Output isn't correct
64 Incorrect 286 ms 58268 KB Output isn't correct
65 Correct 364 ms 58192 KB Output is correct
66 Correct 382 ms 58088 KB Output is correct
67 Correct 405 ms 58204 KB Output is correct
68 Correct 421 ms 58160 KB Output is correct
69 Correct 285 ms 58084 KB Output is correct
70 Correct 127 ms 37968 KB Output is correct
71 Correct 261 ms 58120 KB Output is correct
72 Correct 295 ms 58092 KB Output is correct
73 Correct 303 ms 58080 KB Output is correct
74 Correct 312 ms 58152 KB Output is correct
75 Correct 320 ms 58080 KB Output is correct
76 Correct 277 ms 58108 KB Output is correct
77 Correct 323 ms 58088 KB Output is correct
78 Correct 282 ms 58112 KB Output is correct
79 Correct 248 ms 58152 KB Output is correct
80 Correct 190 ms 57932 KB Output is correct
81 Correct 216 ms 58044 KB Output is correct
82 Correct 293 ms 58004 KB Output is correct
83 Correct 331 ms 57952 KB Output is correct
84 Correct 194 ms 58128 KB Output is correct
85 Correct 286 ms 57956 KB Output is correct
86 Correct 477 ms 57828 KB Output is correct
87 Correct 329 ms 57940 KB Output is correct
88 Correct 251 ms 57920 KB Output is correct
89 Correct 323 ms 57832 KB Output is correct
90 Correct 155 ms 37944 KB Output is correct
91 Correct 305 ms 58012 KB Output is correct
92 Correct 324 ms 57984 KB Output is correct
93 Correct 439 ms 57956 KB Output is correct
94 Correct 332 ms 57956 KB Output is correct
95 Correct 294 ms 57960 KB Output is correct
96 Correct 290 ms 57856 KB Output is correct
97 Correct 471 ms 57964 KB Output is correct
98 Correct 281 ms 57904 KB Output is correct
99 Correct 330 ms 57880 KB Output is correct
100 Correct 442 ms 57828 KB Output is correct