답안 #945057

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945057 2024-03-13T11:03:21 Z atom Bomb (IZhO17_bomb) C++17
62 / 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;
        }
    }

    // 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";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 344 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 Incorrect 0 ms 348 KB Output isn't correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 388 KB Output is correct
19 Incorrect 1 ms 348 KB Output isn't correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Incorrect 1 ms 348 KB Output isn't correct
24 Incorrect 0 ms 348 KB Output isn't correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 2 ms 1372 KB Output is correct
28 Correct 2 ms 1628 KB Output is correct
29 Correct 3 ms 2000 KB Output is correct
30 Incorrect 4 ms 2652 KB Output isn't correct
31 Incorrect 3 ms 2140 KB Output isn't correct
32 Incorrect 4 ms 2136 KB Output isn't correct
33 Correct 4 ms 2904 KB Output is correct
34 Correct 2 ms 1372 KB Output is correct
35 Incorrect 4 ms 2908 KB Output isn't correct
36 Correct 5 ms 3160 KB Output is correct
37 Incorrect 0 ms 348 KB Output isn't correct
38 Execution timed out 2465 ms 131072 KB Time limit exceeded
39 Incorrect 1 ms 344 KB Output isn't correct
40 Correct 24 ms 9564 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 244 ms 74324 KB Output is correct
44 Correct 6 ms 2904 KB Output is correct
45 Incorrect 231 ms 74248 KB Output isn't correct
46 Correct 208 ms 74320 KB Output is correct
47 Incorrect 227 ms 74320 KB Output isn't correct
48 Correct 225 ms 74404 KB Output is correct
49 Correct 278 ms 74324 KB Output is correct
50 Correct 227 ms 74492 KB Output is correct
51 Correct 222 ms 74568 KB Output is correct
52 Correct 213 ms 74320 KB Output is correct
53 Correct 225 ms 74384 KB Output is correct
54 Correct 180 ms 74320 KB Output is correct
55 Correct 179 ms 74252 KB Output is correct
56 Execution timed out 2543 ms 131072 KB Time limit exceeded
57 Correct 176 ms 74324 KB Output is correct
58 Correct 174 ms 74320 KB Output is correct
59 Correct 180 ms 74324 KB Output is correct
60 Correct 212 ms 74252 KB Output is correct
61 Incorrect 275 ms 74384 KB Output isn't correct
62 Correct 284 ms 74380 KB Output is correct
63 Correct 277 ms 74384 KB Output is correct
64 Correct 174 ms 74324 KB Output is correct
65 Correct 209 ms 74320 KB Output is correct
66 Correct 215 ms 74388 KB Output is correct
67 Correct 224 ms 74324 KB Output is correct
68 Correct 235 ms 74384 KB Output is correct
69 Correct 176 ms 74320 KB Output is correct
70 Incorrect 87 ms 47732 KB Output isn't correct
71 Incorrect 163 ms 74384 KB Output isn't correct
72 Correct 176 ms 74384 KB Output is correct
73 Incorrect 179 ms 74384 KB Output isn't correct
74 Incorrect 174 ms 74324 KB Output isn't correct
75 Incorrect 172 ms 74320 KB Output isn't correct
76 Correct 181 ms 74384 KB Output is correct
77 Correct 178 ms 74244 KB Output is correct
78 Correct 181 ms 74240 KB Output is correct
79 Incorrect 130 ms 74320 KB Output isn't correct
80 Incorrect 130 ms 74260 KB Output isn't correct
81 Incorrect 134 ms 74320 KB Output isn't correct
82 Correct 189 ms 74464 KB Output is correct
83 Incorrect 182 ms 74320 KB Output isn't correct
84 Incorrect 131 ms 74320 KB Output isn't correct
85 Incorrect 178 ms 74324 KB Output isn't correct
86 Incorrect 270 ms 74324 KB Output isn't correct
87 Correct 176 ms 74384 KB Output is correct
88 Incorrect 188 ms 74496 KB Output isn't correct
89 Incorrect 200 ms 74320 KB Output isn't correct
90 Incorrect 109 ms 47748 KB Output isn't correct
91 Correct 186 ms 74324 KB Output is correct
92 Correct 206 ms 74240 KB Output is correct
93 Correct 258 ms 74324 KB Output is correct
94 Incorrect 206 ms 74256 KB Output isn't correct
95 Incorrect 186 ms 74244 KB Output isn't correct
96 Incorrect 188 ms 74380 KB Output isn't correct
97 Correct 262 ms 74320 KB Output is correct
98 Correct 182 ms 74324 KB Output is correct
99 Incorrect 202 ms 74376 KB Output isn't correct
100 Incorrect 258 ms 74256 KB Output isn't correct