oj.uz

Submission #706317

# Submission time Handle Problem Language Result Execution time Memory
706317 2023-03-06T09:25:07 Z KiriLL1ca Bomb (IZhO17_bomb) C++17
0 / 100
 1000 ms 119624 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 + 1, inf);

    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 j = 0; j < m; ++j) {
            cout << p[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << s[i][j] << " ";
        }
        cout << endl;
    }

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

    int ans = 0;
    for (int i = 1; i <= m; ++i) {
        umin(mx[i], mx[i - 1]);
        cerr << 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 Runtime error 1 ms 488 KB Execution killed with signal 6
3 Runtime error 2 ms 1108 KB Execution killed with signal 11
4 Runtime error 2 ms 1096 KB Execution killed with signal 11
5 Incorrect 16 ms 320 KB Output isn't correct
6 Incorrect 6 ms 340 KB Output isn't correct
7 Runtime error 1 ms 444 KB Execution killed with signal 6
8 Incorrect 1 ms 212 KB Output isn't correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Incorrect 1 ms 320 KB Output isn't correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Runtime error 1 ms 468 KB Execution killed with signal 6
14 Incorrect 1 ms 212 KB Output isn't correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Incorrect 1 ms 212 KB Output isn't correct
17 Incorrect 2 ms 340 KB Output isn't correct
18 Runtime error 3 ms 576 KB Execution killed with signal 6
19 Runtime error 2 ms 596 KB Execution killed with signal 6
20 Runtime error 3 ms 576 KB Execution killed with signal 6
21 Incorrect 2 ms 340 KB Output isn't correct
22 Incorrect 3 ms 340 KB Output isn't correct
23 Incorrect 3 ms 468 KB Output isn't correct
24 Runtime error 3 ms 596 KB Execution killed with signal 6
25 Incorrect 4 ms 456 KB Output isn't correct
26 Incorrect 3 ms 468 KB Output isn't correct
27 Runtime error 17 ms 2552 KB Execution killed with signal 6
28 Incorrect 17 ms 1876 KB Output isn't correct
29 Runtime error 27 ms 3700 KB Execution killed with signal 6
30 Incorrect 32 ms 3036 KB Output isn't correct
31 Incorrect 25 ms 2388 KB Output isn't correct
32 Runtime error 25 ms 4196 KB Execution killed with signal 6
33 Incorrect 28 ms 3224 KB Output isn't correct
34 Runtime error 14 ms 2396 KB Execution killed with signal 6
35 Incorrect 29 ms 3084 KB Output isn't correct
36 Incorrect 32 ms 3800 KB Output isn't correct
37 Incorrect 1 ms 316 KB Output isn't correct
38 Execution timed out 1047 ms 119624 KB Time limit exceeded
39 Incorrect 1 ms 324 KB Output isn't correct
40 Incorrect 184 ms 13768 KB Output isn't correct
41 Incorrect 1 ms 320 KB Output isn't correct
42 Incorrect 3 ms 452 KB Output isn't correct
43 Execution timed out 1022 ms 107572 KB Time limit exceeded
44 Incorrect 35 ms 3568 KB Output isn't correct
45 Execution timed out 1025 ms 105392 KB Time limit exceeded
46 Execution timed out 1018 ms 91412 KB Time limit exceeded
47 Execution timed out 1006 ms 105444 KB Time limit exceeded
48 Incorrect 980 ms 101852 KB Output isn't correct
49 Execution timed out 1027 ms 114760 KB Time limit exceeded
50 Incorrect 945 ms 103024 KB Output isn't correct
51 Execution timed out 1041 ms 98584 KB Time limit exceeded
52 Incorrect 967 ms 102344 KB Output isn't correct
53 Incorrect 919 ms 102076 KB Output isn't correct
54 Incorrect 874 ms 95076 KB Output isn't correct
55 Incorrect 867 ms 94928 KB Output isn't correct
56 Execution timed out 1008 ms 118936 KB Time limit exceeded
57 Incorrect 921 ms 94672 KB Output isn't correct
58 Incorrect 879 ms 95100 KB Output isn't correct
59 Incorrect 860 ms 94492 KB Output isn't correct
60 Incorrect 890 ms 102020 KB Output isn't correct
61 Execution timed out 1030 ms 118740 KB Time limit exceeded
62 Execution timed out 1004 ms 116964 KB Time limit exceeded
63 Execution timed out 1026 ms 119464 KB Time limit exceeded
64 Incorrect 936 ms 95360 KB Output isn't correct
65 Incorrect 987 ms 101140 KB Output isn't correct
66 Execution timed out 1039 ms 100452 KB Time limit exceeded
67 Execution timed out 1095 ms 103112 KB Time limit exceeded
68 Execution timed out 1035 ms 102028 KB Time limit exceeded
69 Incorrect 991 ms 94660 KB Output isn't correct
70 Incorrect 542 ms 57548 KB Output isn't correct
71 Incorrect 875 ms 91068 KB Output isn't correct
72 Incorrect 907 ms 93320 KB Output isn't correct
73 Incorrect 892 ms 93932 KB Output isn't correct
74 Incorrect 927 ms 93520 KB Output isn't correct
75 Incorrect 890 ms 94172 KB Output isn't correct
76 Incorrect 899 ms 94332 KB Output isn't correct
77 Incorrect 967 ms 95044 KB Output isn't correct
78 Incorrect 942 ms 88460 KB Output isn't correct
79 Incorrect 834 ms 81308 KB Output isn't correct
80 Incorrect 873 ms 81324 KB Output isn't correct
81 Incorrect 812 ms 82064 KB Output isn't correct
82 Incorrect 994 ms 89356 KB Output isn't correct
83 Incorrect 924 ms 89192 KB Output isn't correct
84 Incorrect 867 ms 81656 KB Output isn't correct
85 Incorrect 871 ms 88592 KB Output isn't correct
86 Incorrect 992 ms 109896 KB Output isn't correct
87 Incorrect 925 ms 88296 KB Output isn't correct
88 Incorrect 890 ms 89404 KB Output isn't correct
89 Incorrect 894 ms 95484 KB Output isn't correct
90 Incorrect 531 ms 56116 KB Output isn't correct
91 Incorrect 893 ms 90988 KB Output isn't correct
92 Incorrect 909 ms 94660 KB Output isn't correct
93 Execution timed out 1002 ms 109060 KB Time limit exceeded
94 Incorrect 899 ms 95332 KB Output isn't correct
95 Incorrect 895 ms 89476 KB Output isn't correct
96 Incorrect 877 ms 89084 KB Output isn't correct
97 Execution timed out 1006 ms 109828 KB Time limit exceeded
98 Incorrect 871 ms 89968 KB Output isn't correct
99 Incorrect 915 ms 94620 KB Output isn't correct
100 Incorrect 985 ms 108368 KB Output isn't correct