oj.uz

Submission #173185

# Submission time Handle Problem Language Result Execution time Memory
173185 2020-01-03T14:41:25 Z VEGAnn Bomb (IZhO17_bomb) C++14
0 / 100
 4 ms 488 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, pref[N][N], an1;
short pr[N][N], best[N], nt[N][N], down[N][2], up[N][2];
short 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, N);

    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], short(nt[i][j] - pr[i][j] + 1));
        }
    }

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

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

    if (!full) return -1;

    if (full)
        cout << an1;
    else cout << max(ans, an1);

    return 0;
}

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:72:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("in.txt","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 376 KB Output isn't correct
2 Incorrect 4 ms 376 KB Output isn't correct
3 Incorrect 4 ms 376 KB Output isn't correct
4 Incorrect 4 ms 376 KB Output isn't correct
5 Incorrect 4 ms 460 KB Output isn't correct
6 Incorrect 4 ms 440 KB Output isn't correct
7 Incorrect 4 ms 488 KB Output isn't correct
8 Incorrect 4 ms 376 KB Output isn't correct
9 Incorrect 4 ms 376 KB Output isn't correct
10 Incorrect 4 ms 376 KB Output isn't correct
11 Incorrect 4 ms 380 KB Output isn't correct
12 Incorrect 4 ms 424 KB Output isn't correct
13 Incorrect 4 ms 348 KB Output isn't correct
14 Incorrect 4 ms 376 KB Output isn't correct
15 Incorrect 4 ms 376 KB Output isn't correct
16 Incorrect 4 ms 376 KB Output isn't correct
17 Incorrect 4 ms 444 KB Output isn't correct
18 Incorrect 4 ms 420 KB Output isn't correct
19 Incorrect 4 ms 376 KB Output isn't correct
20 Incorrect 4 ms 348 KB Output isn't correct
21 Incorrect 4 ms 348 KB Output isn't correct
22 Incorrect 4 ms 376 KB Output isn't correct
23 Incorrect 4 ms 376 KB Output isn't correct
24 Incorrect 4 ms 376 KB Output isn't correct
25 Incorrect 4 ms 424 KB Output isn't correct
26 Incorrect 4 ms 376 KB Output isn't correct
27 Incorrect 4 ms 348 KB Output isn't correct
28 Incorrect 4 ms 376 KB Output isn't correct
29 Incorrect 4 ms 376 KB Output isn't correct
30 Incorrect 4 ms 376 KB Output isn't correct
31 Incorrect 4 ms 448 KB Output isn't correct
32 Incorrect 4 ms 376 KB Output isn't correct
33 Incorrect 4 ms 376 KB Output isn't correct
34 Incorrect 4 ms 348 KB Output isn't correct
35 Incorrect 4 ms 376 KB Output isn't correct
36 Incorrect 4 ms 420 KB Output isn't correct
37 Incorrect 4 ms 376 KB Output isn't correct
38 Incorrect 4 ms 352 KB Output isn't correct
39 Incorrect 4 ms 376 KB Output isn't correct
40 Incorrect 4 ms 376 KB Output isn't correct
41 Incorrect 4 ms 376 KB Output isn't correct
42 Incorrect 4 ms 376 KB Output isn't correct
43 Incorrect 4 ms 376 KB Output isn't correct
44 Incorrect 4 ms 348 KB Output isn't correct
45 Incorrect 4 ms 376 KB Output isn't correct
46 Incorrect 4 ms 420 KB Output isn't correct
47 Incorrect 4 ms 376 KB Output isn't correct
48 Incorrect 4 ms 376 KB Output isn't correct
49 Incorrect 4 ms 452 KB Output isn't correct
50 Incorrect 4 ms 376 KB Output isn't correct
51 Incorrect 4 ms 368 KB Output isn't correct
52 Incorrect 4 ms 376 KB Output isn't correct
53 Incorrect 4 ms 376 KB Output isn't correct
54 Incorrect 4 ms 376 KB Output isn't correct
55 Incorrect 4 ms 376 KB Output isn't correct
56 Incorrect 4 ms 376 KB Output isn't correct
57 Incorrect 4 ms 376 KB Output isn't correct
58 Incorrect 4 ms 376 KB Output isn't correct
59 Incorrect 4 ms 376 KB Output isn't correct
60 Incorrect 4 ms 376 KB Output isn't correct
61 Incorrect 4 ms 376 KB Output isn't correct
62 Incorrect 4 ms 376 KB Output isn't correct
63 Incorrect 4 ms 376 KB Output isn't correct
64 Incorrect 4 ms 348 KB Output isn't correct
65 Incorrect 4 ms 376 KB Output isn't correct
66 Incorrect 4 ms 376 KB Output isn't correct
67 Incorrect 4 ms 376 KB Output isn't correct
68 Incorrect 4 ms 376 KB Output isn't correct
69 Incorrect 4 ms 376 KB Output isn't correct
70 Incorrect 4 ms 376 KB Output isn't correct
71 Incorrect 4 ms 376 KB Output isn't correct
72 Incorrect 4 ms 376 KB Output isn't correct
73 Incorrect 4 ms 376 KB Output isn't correct
74 Incorrect 4 ms 376 KB Output isn't correct
75 Incorrect 4 ms 376 KB Output isn't correct
76 Incorrect 4 ms 376 KB Output isn't correct
77 Incorrect 4 ms 376 KB Output isn't correct
78 Incorrect 4 ms 376 KB Output isn't correct
79 Incorrect 4 ms 376 KB Output isn't correct
80 Incorrect 4 ms 376 KB Output isn't correct
81 Incorrect 4 ms 376 KB Output isn't correct
82 Incorrect 4 ms 376 KB Output isn't correct
83 Incorrect 4 ms 376 KB Output isn't correct
84 Incorrect 4 ms 448 KB Output isn't correct
85 Incorrect 4 ms 376 KB Output isn't correct
86 Incorrect 4 ms 424 KB Output isn't correct
87 Incorrect 4 ms 376 KB Output isn't correct
88 Incorrect 4 ms 376 KB Output isn't correct
89 Incorrect 4 ms 376 KB Output isn't correct
90 Incorrect 4 ms 376 KB Output isn't correct
91 Incorrect 4 ms 376 KB Output isn't correct
92 Incorrect 4 ms 376 KB Output isn't correct
93 Incorrect 4 ms 376 KB Output isn't correct
94 Incorrect 4 ms 376 KB Output isn't correct
95 Incorrect 4 ms 376 KB Output isn't correct
96 Incorrect 4 ms 348 KB Output isn't correct
97 Incorrect 4 ms 376 KB Output isn't correct
98 Incorrect 4 ms 376 KB Output isn't correct
99 Incorrect 4 ms 444 KB Output isn't correct
100 Incorrect 3 ms 376 KB Output isn't correct