oj.uz

Submission #180297

# Submission time Handle Problem Language Result Execution time Memory
180297 2020-01-08T17:19:03 Z srvlt Bomb (IZhO17_bomb) C++14
100 / 100
 748 ms 123740 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree <pair <int, int>, null_type, less <pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;

#define ll long long
#define db double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define size(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

#define endl "\n"
//#define int long long

using namespace std;

void dout() {
    cerr << endl;
}
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;

const int N = 2503, inf = 1e4;
int n, m, a[N][N], top[N][N], bot[N][N];
int h[N], W = inf, H = inf, row[N][N], col[N][N];

void solve(int tc) {
    // check for (int i = 0; i < n; j++)
    cin >> n >> m;
    char c;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c;
            if (c == '1') {
                a[i][j] = 1;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        bot[n + 1][i] = n + 1;
    }
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            top[i][j] = top[i - 1][j];
            if (!a[i][j]) {
                top[i][j] = i;
            }
        }
        for (int i = n; i >= 1; i--) {
            bot[i][j] = bot[i + 1][j];
            if (!a[i][j]) {
                bot[i][j] = i;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j]) {
                row[i][j] = row[i][j - 1] + 1;
            }   else {
                if (row[i][j - 1] > 0) {
                    W = min(W, row[i][j - 1]);
                }
            }
        }
        if (row[i][m] > 0) {
            W = min(W, row[i][m]);
        }
    }
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            if (a[i][j]) {
                col[i][j] = col[i - 1][j] + 1;
            }   else {
                if (col[i - 1][j] > 0) {
                    H = min(H, col[i - 1][j]);
                }
            }
        }
        if (col[n][j] > 0) {
            H = min(H, col[n][j]);
        }
    }

    for (int i = 1; i <= m; i++) {
        h[i] = H;
    }

    for (int i = 1; i <= n; i++) {
        int last = -1, mn = inf, mx = -inf;
        for (int j = 1; j <= m; j++) {
            if (!a[i][j]) {
                last = -1;
                mn = inf, mx = -inf;
            }   else {
                if (last == -1) {
                    last = j;
                }
                mn = min(mn, bot[i][j]);
                mx = max(mx, top[i][j]);
                h[j - last + 1] = min(h[j - last + 1], mn - mx - 1);
            }
        }
        last = -1, mn = inf, mx = -inf;
        for (int j = m; j >= 1; j--) {
            if (!a[i][j]) {
                last = -1;
                mn = inf, mx = -inf;
            }   else {
                if (last == -1) {
                    last = j;
                }
                mn = min(mn, bot[i][j]);
                mx = max(mx, top[i][j]);
                h[last - j + 1] = min(h[last - j + 1], mn - mx - 1);
            }
        }
    }
    int mn = inf, mx = 0;
    for (int i = 1; i <= W; i++) {
        mn = h[i];
        mx = max(mx, mn * i);
    }
    cout << mx;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
//    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
//        cleanup();
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 44 ms 50552 KB Output is correct
4 Correct 44 ms 50552 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 3 ms 632 KB Output is correct
14 Correct 2 ms 632 KB Output is correct
15 Correct 3 ms 760 KB Output is correct
16 Correct 0 ms 760 KB Output is correct
17 Correct 3 ms 1788 KB Output is correct
18 Correct 4 ms 1400 KB Output is correct
19 Correct 4 ms 1912 KB Output is correct
20 Correct 4 ms 1856 KB Output is correct
21 Correct 2 ms 1060 KB Output is correct
22 Correct 4 ms 1532 KB Output is correct
23 Correct 4 ms 2040 KB Output is correct
24 Correct 4 ms 1912 KB Output is correct
25 Correct 4 ms 2424 KB Output is correct
26 Correct 4 ms 2680 KB Output is correct
27 Correct 11 ms 7928 KB Output is correct
28 Correct 9 ms 4220 KB Output is correct
29 Correct 11 ms 10460 KB Output is correct
30 Correct 15 ms 9976 KB Output is correct
31 Correct 13 ms 7160 KB Output is correct
32 Correct 15 ms 9080 KB Output is correct
33 Correct 19 ms 11512 KB Output is correct
34 Correct 9 ms 4728 KB Output is correct
35 Correct 15 ms 6652 KB Output is correct
36 Correct 21 ms 13560 KB Output is correct
37 Correct 3 ms 760 KB Output is correct
38 Correct 743 ms 123740 KB Output is correct
39 Correct 3 ms 760 KB Output is correct
40 Correct 75 ms 33784 KB Output is correct
41 Correct 2 ms 760 KB Output is correct
42 Correct 4 ms 2552 KB Output is correct
43 Correct 746 ms 117880 KB Output is correct
44 Correct 24 ms 12664 KB Output is correct
45 Correct 725 ms 119884 KB Output is correct
46 Correct 737 ms 123656 KB Output is correct
47 Correct 719 ms 120056 KB Output is correct
48 Correct 738 ms 123640 KB Output is correct
49 Correct 748 ms 123640 KB Output is correct
50 Correct 744 ms 123640 KB Output is correct
51 Correct 730 ms 123512 KB Output is correct
52 Correct 724 ms 123640 KB Output is correct
53 Correct 720 ms 122616 KB Output is correct
54 Correct 694 ms 103740 KB Output is correct
55 Correct 691 ms 101152 KB Output is correct
56 Correct 740 ms 123652 KB Output is correct
57 Correct 680 ms 93816 KB Output is correct
58 Correct 684 ms 101232 KB Output is correct
59 Correct 686 ms 96524 KB Output is correct
60 Correct 710 ms 111224 KB Output is correct
61 Correct 743 ms 123552 KB Output is correct
62 Correct 733 ms 123540 KB Output is correct
63 Correct 748 ms 123384 KB Output is correct
64 Correct 679 ms 97680 KB Output is correct
65 Correct 723 ms 121832 KB Output is correct
66 Correct 719 ms 117356 KB Output is correct
67 Correct 723 ms 123360 KB Output is correct
68 Correct 727 ms 123436 KB Output is correct
69 Correct 685 ms 92920 KB Output is correct
70 Correct 421 ms 55180 KB Output is correct
71 Correct 656 ms 82440 KB Output is correct
72 Correct 676 ms 90616 KB Output is correct
73 Correct 682 ms 91464 KB Output is correct
74 Correct 678 ms 93632 KB Output is correct
75 Correct 682 ms 96088 KB Output is correct
76 Correct 707 ms 98108 KB Output is correct
77 Correct 713 ms 98680 KB Output is correct
78 Correct 691 ms 99268 KB Output is correct
79 Correct 625 ms 58104 KB Output is correct
80 Correct 641 ms 59832 KB Output is correct
81 Correct 635 ms 60408 KB Output is correct
82 Correct 692 ms 102940 KB Output is correct
83 Correct 716 ms 103060 KB Output is correct
84 Correct 617 ms 50936 KB Output is correct
85 Correct 686 ms 101516 KB Output is correct
86 Correct 737 ms 121720 KB Output is correct
87 Correct 683 ms 99572 KB Output is correct
88 Correct 692 ms 101168 KB Output is correct
89 Correct 707 ms 114168 KB Output is correct
90 Correct 447 ms 76176 KB Output is correct
91 Correct 699 ms 107000 KB Output is correct
92 Correct 708 ms 109488 KB Output is correct
93 Correct 728 ms 120184 KB Output is correct
94 Correct 708 ms 112120 KB Output is correct
95 Correct 697 ms 102880 KB Output is correct
96 Correct 698 ms 102572 KB Output is correct
97 Correct 738 ms 121480 KB Output is correct
98 Correct 687 ms 102248 KB Output is correct
99 Correct 706 ms 111436 KB Output is correct
100 Correct 731 ms 119416 KB Output is correct