oj.uz

Submission #173167

# Submission time Handle Problem Language Result Execution time Memory
173167 2020-01-03T14:16:12 Z VEGAnn Bomb (IZhO17_bomb) C++14
14 / 100
 1000 ms 131076 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define MP make_pair
#define ft first
#define sd second
#define pii pair<int, int>
#define PB push_back
using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2510;
const int oo = 2e9;
int n, m, ans, a[N][N], mx = oo, pr[N][N], best[N], nt[N][N], down[N][2], up[N][2], pref[N][N];
int pl[N][N], vl[N][N];
stack<int> st;

bool ok(int ht, int wd){
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            pl[i][j] = 0;

    bool was = 1;
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++){
        if (i + ht - 1 > n || j + wd - 1 > m)
            break;
        int i1 = i + ht - 1, i2 = i - 1;
        int j1 = j + wd - 1, j2 = j - 1;
        int kol = pref[i1][j1] - pref[i2][j1] - pref[i1][j2] + pref[i2][j2];

        if (kol > 0) continue;

        was = 1;
        pl[i][j]++; pl[i][j + wd]--;
        pl[i + ht][j]--; pl[i + ht][j + wd]++;

    }

    if (!was) return 0;

    for (int i = 1; i <= n; i++){
        int cr = 0;
        for (int j = 1; j <= m; j++){
            cr += pl[i][j];
            vl[i][j] = cr;
        }
    }

    for (int j = 1; j <= m; j++){
        int cr = 0;
        for (int i = 1; i <= n; i++){
            cr += vl[i][j];
            if (a[i][j] == 1 && cr == 0)
                return 0;
        }
    }

    return 1;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("in.txt","r",stdin);

    ll sta = chrono::system_clock().now().time_since_epoch().count();

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++){
        char c; cin >> c;
        a[i][j] = (c == '1' ? 1 : 0);

        pref[i][j] = (a[i][j] ^ 1) + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];

    }

    for (int j = 1; j <= m; j++){
        for (int i = 1; i <= n; ){
            if (a[i][j] == 0)
                i++;
            else {
                int i1 = i;
                while (i1 <= n && a[i1][j] == 1)
                    i1++;
                mx = min(mx, i1 - i);
                i = i1;
            }
        }
    }

    if (mx == oo){
        cout << n * m;
        return 0;
    }

    fill(best, best + n + 1, oo);

    for (int i = 1; i <= n; i++){
        int pre = 0;
        for (int j = 1; j <= m; j++){
            if (a[i][j] == 0)
                pre = j;
            pr[i][j] = pre + 1;
        }

        pre = m + 1;
        for (int j = m; j > 0; j--){
            if (a[i][j] == 0)
                pre = j;
            nt[i][j] = pre - 1;
        }
    }

    for (int j = 1; j <= m; j++){
        for (int i = 1; i <= n; ){
            if (a[i][j] == 0)
                i++;
            else {
                int i1 = i;
                while (i1 <= n && a[i1][j] == 1)
                    i1++;

                while (sz(st)) st.pop();
                for (int ii = i; ii < i1; ii++){
                    while (sz(st) && pr[st.top()][j] <= pr[ii][j])
                        st.pop();
                    down[ii][0] = (sz(st) == 0 ? i : st.top() + 1);
                    st.push(ii);
                }

                while (sz(st)) st.pop();
                for (int ii = i; ii < i1; ii++){
                    while (sz(st) && nt[st.top()][j] >= nt[ii][j])
                        st.pop();
                    down[ii][1] = (sz(st) == 0 ? i : st.top() + 1);
                    st.push(ii);
                }

                while (sz(st)) st.pop();
                for (int ii = i1 - 1; ii >= i; ii--){
                    while (sz(st) && pr[st.top()][j] <= pr[ii][j])
                        st.pop();
                    up[ii][0] = (sz(st) == 0 ? i1 - 1 : st.top() - 1);
                    st.push(ii);
                }

                while (sz(st)) st.pop();
                for (int ii = i1 - 1; ii >= i; ii--){
                    while (sz(st) && nt[st.top()][j] >= nt[ii][j])
                        st.pop();
                    up[ii][1] = (sz(st) == 0 ? i1 - 1 : st.top() - 1);
                    st.push(ii);
                }

                i = i1;
            }
        }

        for (int i = 1; i <= n; i++){
            if (a[i][j] == 0) continue;
            int l = max(down[i][0], down[i][1]);
            int r = min(up[i][0], up[i][1]);
            int cur = r - l + 1;
            best[cur] = min(best[cur], nt[i][j] - pr[i][j] + 1);
        }
    }

    best[n + 1] = oo;
    for (int i = n; i > 0; i--) {
        best[i] = min(best[i + 1], best[i]);
        if (best[i] < oo && i <= mx)
            ans = max(ans, best[i] * i);
    }

    int wd = m;
    for (int ht = 1; ht <= n; ht++){
        ll tim = chrono::system_clock().now().time_since_epoch().count();;
        if (tim - sta < 10000000) break;
        while (wd > 0 && !ok(ht, wd))
            wd--;
        if (wd == 0) break;
        if (n * wd <= ans) break;
        ans = max(ans, ht * wd);
    }

    cout << ans << '\n';

    return 0;
}

Subtask #1
14.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 62 ms 60792 KB Output is correct
4 Correct 67 ms 60664 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Incorrect 3 ms 760 KB Output isn't correct
9 Incorrect 3 ms 632 KB Output isn't correct
10 Incorrect 3 ms 760 KB Output isn't correct
11 Incorrect 2 ms 760 KB Output isn't correct
12 Incorrect 2 ms 632 KB Output isn't correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 2 ms 632 KB Output is correct
15 Incorrect 2 ms 632 KB Output isn't correct
16 Correct 2 ms 632 KB Output is correct
17 Correct 4 ms 2040 KB Output is correct
18 Incorrect 3 ms 1528 KB Output isn't correct
19 Incorrect 4 ms 2040 KB Output isn't correct
20 Incorrect 3 ms 1912 KB Output isn't correct
21 Incorrect 3 ms 1272 KB Output isn't correct
22 Incorrect 3 ms 1656 KB Output isn't correct
23 Incorrect 4 ms 2168 KB Output isn't correct
24 Incorrect 3 ms 1784 KB Output isn't correct
25 Incorrect 4 ms 2168 KB Output isn't correct
26 Correct 4 ms 2168 KB Output is correct
27 Correct 75 ms 9504 KB Output is correct
28 Incorrect 10 ms 6904 KB Output isn't correct
29 Incorrect 235 ms 12888 KB Output isn't correct
30 Incorrect 239 ms 15352 KB Output isn't correct
31 Incorrect 172 ms 12280 KB Output isn't correct
32 Incorrect 151 ms 13944 KB Output isn't correct
33 Incorrect 282 ms 16120 KB Output isn't correct
34 Incorrect 63 ms 11128 KB Output isn't correct
35 Incorrect 268 ms 16248 KB Output isn't correct
36 Correct 377 ms 16248 KB Output is correct
37 Incorrect 2 ms 632 KB Output isn't correct
38 Execution timed out 1032 ms 131076 KB Time limit exceeded
39 Incorrect 2 ms 632 KB Output isn't correct
40 Execution timed out 1053 ms 40400 KB Time limit exceeded
41 Incorrect 2 ms 760 KB Output isn't correct
42 Incorrect 4 ms 2168 KB Output isn't correct
43 Runtime error 994 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Incorrect 328 ms 16152 KB Output isn't correct
45 Runtime error 800 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
46 Runtime error 689 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 797 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Runtime error 730 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
49 Execution timed out 1080 ms 103928 KB Time limit exceeded
50 Runtime error 753 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Runtime error 750 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
52 Runtime error 752 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
53 Runtime error 734 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
54 Runtime error 565 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
55 Runtime error 558 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
56 Runtime error 1006 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
57 Runtime error 526 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
58 Runtime error 547 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
59 Runtime error 530 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
60 Runtime error 712 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
61 Execution timed out 1083 ms 101752 KB Time limit exceeded
62 Runtime error 1012 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
63 Runtime error 1031 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
64 Runtime error 533 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
65 Runtime error 707 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
66 Runtime error 715 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
67 Runtime error 779 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
68 Runtime error 831 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
69 Runtime error 535 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
70 Execution timed out 1090 ms 122256 KB Time limit exceeded
71 Runtime error 467 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
72 Runtime error 520 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Runtime error 548 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
74 Runtime error 518 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
75 Runtime error 536 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Runtime error 550 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
77 Runtime error 564 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
78 Runtime error 546 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
79 Runtime error 339 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
80 Runtime error 342 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
81 Runtime error 358 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
82 Runtime error 575 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
83 Runtime error 574 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
84 Runtime error 345 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
85 Runtime error 545 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
86 Runtime error 980 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
87 Runtime error 534 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
88 Runtime error 579 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
89 Runtime error 680 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
90 Execution timed out 1082 ms 122232 KB Time limit exceeded
91 Runtime error 599 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
92 Runtime error 686 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
93 Runtime error 941 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
94 Runtime error 675 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
95 Runtime error 572 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
96 Runtime error 578 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
97 Runtime error 964 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
98 Runtime error 566 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
99 Runtime error 661 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
100 Runtime error 942 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)