답안 #945056

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

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