oj.uz

Submission #883711

# Submission time Handle Problem Language Result Execution time Memory
883711 2023-12-05T19:04:49 Z Sokol080808 Bomb (IZhO17_bomb) C++17
23 / 100
 1000 ms 55848 KB 
#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <malloc.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2>& p) {in >> p.first >> p.second; return in;}
template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2>& p) {out << p.first << ' ' << p.second; return out;}
template<typename T> istream& operator>>(istream& in, vector<T>& v) {for (auto& x : v) in >> x; return in;}
template<typename T> ostream& operator<<(ostream& out, vector<T>& v) {for (auto& x : v) out << x << ' '; return out;}
template<typename T> ostream& operator<<(ostream& out, set<T>& v) {for (auto& x : v) out << x << ' '; return out;}
template<typename T> ostream& operator<<(ostream& out, multiset<T>& v) {for (auto& x : v) out << x << ' '; return out;}

const int MAX_INT = 2147483647;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<char>> f(n, vector<char>(m));
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> f[i][j];


    vector<vector<int>> up(n, vector<int>(m)), down(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (f[i][j] == '0') {
                up[i][j] = i;
                continue;
            }
            up[i][j] = (i - 1 >= 0 ? up[i - 1][j] : i - 1);
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < m; j++) {
            if (f[i][j] == '0') {
                down[i][j] = i;
                continue;
            }
            down[i][j] = (i + 1 < n ? down[i + 1][j] : i + 1);
        }
    }

    vector<ll> best(m + 1, n);
    int mx_x = 1e9;
    for (int i = 0; i < n; i++) {
        int mn = 1e9;
        for (int j = 0; j < m; j++) {
            if (f[i][j] == '0') continue;

            int r = j;
            while (r + 1 < m && f[i][r + 1] == '1') r++;

            int mx_l = r - j + 1;
            mn = min(mn, mx_l);

            for (int l = j; l <= r; l++) {
                int u = -1;
                int d = n;
                for (int lst = l, len = 1; lst <= r; lst++, len++) {
                    u = max(u, up[i][lst]);
                    d = min(d, down[i][lst]);
                    best[len] = min<ll>(best[len], d - u - 1);
                }
            }

            j = r;
        }
        mx_x = min(mx_x, mn);
    }

    ll ans = 0;
    for (int i = 1; i <= mx_x; i++) ans = max(ans, i * best[i]);
    cout << ans << '\n';

    return 0;
}

Subtask #1
23.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Correct 0 ms 344 KB Output is correct
17 Incorrect 0 ms 348 KB Output isn't correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Incorrect 0 ms 348 KB Output isn't correct
24 Incorrect 1 ms 348 KB Output isn't correct
25 Incorrect 1 ms 348 KB Output isn't correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 12 ms 1116 KB Output is correct
28 Correct 2 ms 1372 KB Output is correct
29 Correct 19 ms 1612 KB Output is correct
30 Incorrect 7 ms 2140 KB Output isn't correct
31 Incorrect 5 ms 1628 KB Output isn't correct
32 Incorrect 3 ms 1892 KB Output isn't correct
33 Incorrect 12 ms 2268 KB Output isn't correct
34 Correct 2 ms 1116 KB Output is correct
35 Incorrect 4 ms 2204 KB Output isn't correct
36 Incorrect 61 ms 2292 KB Output isn't correct
37 Incorrect 0 ms 344 KB Output isn't correct
38 Execution timed out 1045 ms 55632 KB Time limit exceeded
39 Incorrect 0 ms 348 KB Output isn't correct
40 Incorrect 296 ms 7332 KB Output isn't correct
41 Incorrect 1 ms 344 KB Output isn't correct
42 Incorrect 1 ms 348 KB Output isn't correct
43 Execution timed out 1038 ms 55536 KB Time limit exceeded
44 Incorrect 27 ms 2136 KB Output isn't correct
45 Execution timed out 1043 ms 55648 KB Time limit exceeded
46 Correct 147 ms 55796 KB Output is correct
47 Execution timed out 1078 ms 55532 KB Time limit exceeded
48 Execution timed out 1040 ms 55632 KB Time limit exceeded
49 Execution timed out 1041 ms 55532 KB Time limit exceeded
50 Execution timed out 1048 ms 55648 KB Time limit exceeded
51 Execution timed out 1066 ms 55540 KB Time limit exceeded
52 Execution timed out 1040 ms 55556 KB Time limit exceeded
53 Execution timed out 1065 ms 55636 KB Time limit exceeded
54 Execution timed out 1060 ms 55768 KB Time limit exceeded
55 Execution timed out 1010 ms 55632 KB Time limit exceeded
56 Correct 313 ms 55796 KB Output is correct
57 Execution timed out 1016 ms 55548 KB Time limit exceeded
58 Execution timed out 1069 ms 55556 KB Time limit exceeded
59 Execution timed out 1010 ms 55636 KB Time limit exceeded
60 Execution timed out 1047 ms 55536 KB Time limit exceeded
61 Execution timed out 1032 ms 55532 KB Time limit exceeded
62 Execution timed out 1045 ms 55548 KB Time limit exceeded
63 Execution timed out 1050 ms 55772 KB Time limit exceeded
64 Execution timed out 1030 ms 55548 KB Time limit exceeded
65 Execution timed out 1018 ms 55588 KB Time limit exceeded
66 Execution timed out 1024 ms 55632 KB Time limit exceeded
67 Execution timed out 1066 ms 55636 KB Time limit exceeded
68 Execution timed out 1056 ms 55536 KB Time limit exceeded
69 Execution timed out 1064 ms 55636 KB Time limit exceeded
70 Incorrect 207 ms 35924 KB Output isn't correct
71 Incorrect 470 ms 55636 KB Output isn't correct
72 Execution timed out 1004 ms 55792 KB Time limit exceeded
73 Execution timed out 1031 ms 55728 KB Time limit exceeded
74 Incorrect 948 ms 55548 KB Output isn't correct
75 Execution timed out 1014 ms 55792 KB Time limit exceeded
76 Execution timed out 1070 ms 55632 KB Time limit exceeded
77 Execution timed out 1034 ms 55536 KB Time limit exceeded
78 Execution timed out 1054 ms 55552 KB Time limit exceeded
79 Incorrect 87 ms 55636 KB Output isn't correct
80 Incorrect 88 ms 55636 KB Output isn't correct
81 Incorrect 123 ms 55636 KB Output isn't correct
82 Execution timed out 1070 ms 55548 KB Time limit exceeded
83 Execution timed out 1031 ms 55544 KB Time limit exceeded
84 Incorrect 91 ms 55792 KB Output isn't correct
85 Execution timed out 1042 ms 55792 KB Time limit exceeded
86 Execution timed out 1038 ms 55536 KB Time limit exceeded
87 Correct 841 ms 55800 KB Output is correct
88 Execution timed out 1073 ms 55532 KB Time limit exceeded
89 Execution timed out 1048 ms 55544 KB Time limit exceeded
90 Incorrect 426 ms 35920 KB Output isn't correct
91 Execution timed out 1072 ms 55628 KB Time limit exceeded
92 Execution timed out 1071 ms 55636 KB Time limit exceeded
93 Execution timed out 1074 ms 55640 KB Time limit exceeded
94 Execution timed out 1055 ms 55540 KB Time limit exceeded
95 Execution timed out 1038 ms 55632 KB Time limit exceeded
96 Execution timed out 1061 ms 55636 KB Time limit exceeded
97 Execution timed out 1052 ms 55756 KB Time limit exceeded
98 Execution timed out 1018 ms 55636 KB Time limit exceeded
99 Execution timed out 1042 ms 55848 KB Time limit exceeded
100 Execution timed out 1044 ms 55688 KB Time limit exceeded