oj.uz

Submission #945056

# Submission time Handle Problem Language Result Execution time Memory
945056 2024-03-13T11:02:06 Z atom Bomb (IZhO17_bomb) C++17
64 / 100
 1000 ms 131072 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
 
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
 
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    #ifdef JASPER
        freopen("in1", "r", stdin);
    #endif
 
    int n, m;
    cin >> n >> m;
    vector <vector <int>> a(n + 5, vector <int> (m + 5, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char x; cin >> x;
            a[i][j] = x - '0';
        }
    }
 
    // for (int i = 1; i <= n; ++i) 
    //     for (int j = 1; j <= m; ++j)
    //         cout << a[i][j] << " \n"[j == m]; 
 
    //sub1: shortest consecutive 1ss
    if (n == 1 || m == 1) {
        if (n == 1) {
            int ans = 1e9;
            for (int i = 1; i <= m; ++i) {
                if (a[1][i] == 0) continue;
                int cur = 0;
                while (i <= m && a[1][i]) { 
                    ++cur;
                    ++i;
                }
                ans = min(ans, cur);
            }
            cout << ans << "\n";
            return 0;
        }
        if (m == 1) {
            int ans = 1e9;
            for (int i = 1; i <= n; ++i) {
                if (a[i][1] == 0) continue;
                int cur = 0;
                while (i <= n && a[i][1]) { 
                    ++cur;
                    ++i;
                }
                ans = min(ans, cur);
            }
            cout << ans << "\n";
            return 0;
        }
    }
 
    // sub3
    if (n <= 450 && m <= 450) {
        vector <vector <int>> prf(n + 5, vector <int> (m + 5, 0));
        int earth = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                earth += (a[i][j] == 0);
                prf[i][j] = prf[i][j - 1] + prf[i - 1][j] - prf[i - 1][j - 1] + a[i][j];
            }
        }
 
        int ans = 0;
        for (int x = 1; x <= n; ++x) {
            for (int y = 1; y <= m; ++y) {
                if (x * y <= ans) continue;
 
                // prf(l)++, prf(r + 1)--;
                vector <vector <int>> dmg(n + 2, vector <int> (m + 2, 0));
 
                for (int i = 1; i + x - 1 <= n; ++i) {
                    for (int j = 1; j + y - 1 <= m; ++j) {
                        int I = i + x - 1, J = j + y - 1;
                        if (prf[I][J] + prf[i - 1][j - 1] - prf[I][j - 1] - prf[i - 1][J] == x * y) {
                            dmg[i][j] += 1;
                            dmg[I + 1][j] -= 1;
                            dmg[i][J + 1] -= 1;
                            dmg[I + 1][J + 1] += 1;
                        }
                    }
                }
 
                for (int i = 1; i <= n; ++i)
                    for (int j = 1; j <= m; ++j)
                        dmg[i][j] += dmg[i - 1][j] + dmg[i][j - 1] - dmg[i - 1][j - 1];

                bool valid = 1;
                for (int i = 1; i <= n; ++i) {
                    for (int j = 1; j <= m; ++j) {
                        if (a[i][j] && !dmg[i][j])
                            valid = 0;
                    }
                }
                if (valid) ans = max(ans, x * y);
            }
        }
 
        cout << ans << "\n";
        return 0;
    }
    


    // two pointer to optimize
    vector <vector <int>> lt(n + 5, vector <int> (m + 5, 0)), rt(n + 5, vector <int> (m + 5, 0));
    vector <int> w(n + 5, 1e9); // ans(i) : W when H = i
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            a[i][j]? lt[i][j] = (lt[i][j - 1] + 1) : 0;

        for (int j = m; j >= 1; --j)
            a[i][j]? rt[i][j] = (rt[i][j + 1] + 1) : 0;

        for (int j = 1; j <= m; ++j)
            if (a[i][j]) w[1] = min(w[1], rt[i][j] + lt[i][j] - 1);
    }
    // find feasible height

    int min_h = 1e9; // minimum vertical strip of 1s;
    for (int j = 1; j <= m; ++j) {
        int k = 0; // length of consecutive 1s of current column
        int l = 1e9, r = 1e9;
        for (int i = 1; i <= n; ++i) {
            if (a[i][j]) {
                ++k;
                l = min(l, lt[i][j]);
                r = min(r, rt[i][j]);
                w[k] = min(w[k], r + l - 1);
            }
            else {
                if (k) min_h = min(min_h, k);
                l = r = 1e9;
                k = 0;
            }
        }
    }

    int ans = 0;
    for (int h = 1; h <= min_h; ++h) {
        w[h + 1] = min(w[h + 1], w[h]); // width is bounded by the minimum horizontal strip
        ans = max(ans, w[h] * h);
    }
    cout << ans << "\n";
}

Subtask #1
64.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 456 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 86 ms 344 KB Output is correct
18 Correct 79 ms 348 KB Output is correct
19 Correct 211 ms 544 KB Output is correct
20 Correct 233 ms 348 KB Output is correct
21 Correct 87 ms 504 KB Output is correct
22 Correct 201 ms 756 KB Output is correct
23 Correct 377 ms 580 KB Output is correct
24 Correct 142 ms 532 KB Output is correct
25 Correct 406 ms 348 KB Output is correct
26 Correct 384 ms 604 KB Output is correct
27 Execution timed out 1070 ms 1908 KB Time limit exceeded
28 Execution timed out 1050 ms 2044 KB Time limit exceeded
29 Execution timed out 1054 ms 2364 KB Time limit exceeded
30 Execution timed out 1039 ms 3076 KB Time limit exceeded
31 Execution timed out 1049 ms 2644 KB Time limit exceeded
32 Execution timed out 1033 ms 2576 KB Time limit exceeded
33 Execution timed out 1067 ms 3560 KB Time limit exceeded
34 Execution timed out 1055 ms 1796 KB Time limit exceeded
35 Execution timed out 1054 ms 3344 KB Time limit exceeded
36 Execution timed out 1053 ms 3252 KB Time limit exceeded
37 Correct 1 ms 348 KB Output is correct
38 Execution timed out 2669 ms 131072 KB Time limit exceeded
39 Correct 1 ms 348 KB Output is correct
40 Correct 22 ms 10492 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 333 ms 348 KB Output is correct
43 Correct 236 ms 80468 KB Output is correct
44 Execution timed out 1063 ms 3316 KB Time limit exceeded
45 Incorrect 227 ms 80464 KB Output isn't correct
46 Correct 217 ms 80464 KB Output is correct
47 Incorrect 248 ms 80496 KB Output isn't correct
48 Correct 223 ms 80492 KB Output is correct
49 Correct 286 ms 80500 KB Output is correct
50 Correct 227 ms 80492 KB Output is correct
51 Correct 226 ms 80496 KB Output is correct
52 Correct 219 ms 80500 KB Output is correct
53 Correct 219 ms 80492 KB Output is correct
54 Correct 209 ms 80496 KB Output is correct
55 Correct 178 ms 80496 KB Output is correct
56 Execution timed out 2527 ms 131072 KB Time limit exceeded
57 Correct 180 ms 80472 KB Output is correct
58 Correct 182 ms 80464 KB Output is correct
59 Correct 172 ms 80468 KB Output is correct
60 Correct 219 ms 80380 KB Output is correct
61 Incorrect 275 ms 80364 KB Output isn't correct
62 Correct 279 ms 80496 KB Output is correct
63 Correct 281 ms 80724 KB Output is correct
64 Correct 195 ms 80472 KB Output is correct
65 Correct 210 ms 80496 KB Output is correct
66 Correct 214 ms 80472 KB Output is correct
67 Correct 233 ms 80468 KB Output is correct
68 Correct 243 ms 80724 KB Output is correct
69 Correct 175 ms 80496 KB Output is correct
70 Incorrect 94 ms 51680 KB Output isn't correct
71 Incorrect 158 ms 80464 KB Output isn't correct
72 Correct 172 ms 80376 KB Output is correct
73 Incorrect 181 ms 80464 KB Output isn't correct
74 Incorrect 176 ms 80492 KB Output isn't correct
75 Incorrect 178 ms 80468 KB Output isn't correct
76 Correct 185 ms 80720 KB Output is correct
77 Correct 182 ms 80468 KB Output is correct
78 Correct 193 ms 80368 KB Output is correct
79 Incorrect 131 ms 80468 KB Output isn't correct
80 Incorrect 133 ms 80472 KB Output isn't correct
81 Incorrect 141 ms 80500 KB Output isn't correct
82 Correct 186 ms 80496 KB Output is correct
83 Incorrect 185 ms 80464 KB Output isn't correct
84 Incorrect 131 ms 80468 KB Output isn't correct
85 Incorrect 185 ms 80492 KB Output isn't correct
86 Incorrect 263 ms 80496 KB Output isn't correct
87 Correct 176 ms 80464 KB Output is correct
88 Incorrect 185 ms 80468 KB Output isn't correct
89 Incorrect 207 ms 80496 KB Output isn't correct
90 Incorrect 106 ms 51536 KB Output isn't correct
91 Correct 196 ms 80572 KB Output is correct
92 Correct 212 ms 80364 KB Output is correct
93 Correct 260 ms 80468 KB Output is correct
94 Incorrect 203 ms 80496 KB Output isn't correct
95 Incorrect 189 ms 80496 KB Output isn't correct
96 Incorrect 184 ms 80256 KB Output isn't correct
97 Correct 265 ms 80492 KB Output is correct
98 Correct 186 ms 80500 KB Output is correct
99 Incorrect 206 ms 80512 KB Output isn't correct
100 Incorrect 286 ms 80496 KB Output isn't correct