답안 #945057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
945057	2024-03-13T11:03:21 Z	atom	Bomb (IZhO17_bomb)	C++17	62 / 100	1000 ms	131072 KB

bomb

#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";
}

Subtask #1

62.0 / 100.0

#	결과	실행 시간	메모리	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