oj.uz

답안 #942744

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
942744 2024-03-11T03:49:28 Z atom Bomb (IZhO17_bomb) C++17
30 / 100
 1000 ms 29032 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);

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

                // if (x == 3 && y == 1) {
                //     cout << "\n";
                //     for (int i = 1; i <= n; ++i) 
                //         for (int j = 1; j <= m; ++j)
                //             cout << dmg[i][j] << " \n"[j == m]; 
                // }   

                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];

                // if (x == 3 && y == 1) {
                //     cout << "\n";
                //     for (int i = 1; i <= n; ++i) 
                //         for (int j = 1; j <= m; ++j)
                //             cout << dmg[i][j] << " \n"[j == m]; 
                // }
                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";
    }

}

Subtask #1
30.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 1 ms 344 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 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 348 KB Output is correct
13 Correct 1 ms 436 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 99 ms 348 KB Output is correct
18 Correct 81 ms 504 KB Output is correct
19 Correct 209 ms 540 KB Output is correct
20 Correct 238 ms 344 KB Output is correct
21 Correct 86 ms 504 KB Output is correct
22 Correct 196 ms 532 KB Output is correct
23 Correct 365 ms 568 KB Output is correct
24 Correct 145 ms 344 KB Output is correct
25 Correct 385 ms 576 KB Output is correct
26 Correct 387 ms 568 KB Output is correct
27 Execution timed out 1051 ms 1436 KB Time limit exceeded
28 Execution timed out 1054 ms 1820 KB Time limit exceeded
29 Execution timed out 1048 ms 1988 KB Time limit exceeded
30 Execution timed out 1061 ms 3112 KB Time limit exceeded
31 Execution timed out 1018 ms 2704 KB Time limit exceeded
32 Execution timed out 1069 ms 2616 KB Time limit exceeded
33 Execution timed out 1018 ms 3224 KB Time limit exceeded
34 Execution timed out 1069 ms 1492 KB Time limit exceeded
35 Execution timed out 1006 ms 3412 KB Time limit exceeded
36 Execution timed out 1047 ms 3048 KB Time limit exceeded
37 Correct 1 ms 344 KB Output is correct
38 Incorrect 64 ms 24920 KB Output isn't correct
39 Correct 1 ms 344 KB Output is correct
40 Incorrect 8 ms 3420 KB Output isn't correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 333 ms 596 KB Output is correct
43 Incorrect 77 ms 25084 KB Output isn't correct
44 Execution timed out 1030 ms 3152 KB Time limit exceeded
45 Incorrect 71 ms 25092 KB Output isn't correct
46 Incorrect 75 ms 25088 KB Output isn't correct
47 Incorrect 74 ms 28896 KB Output isn't correct
48 Incorrect 79 ms 28912 KB Output isn't correct
49 Incorrect 73 ms 28684 KB Output isn't correct
50 Incorrect 70 ms 28688 KB Output isn't correct
51 Incorrect 73 ms 28904 KB Output isn't correct
52 Incorrect 67 ms 28852 KB Output isn't correct
53 Incorrect 71 ms 28672 KB Output isn't correct
54 Incorrect 67 ms 28844 KB Output isn't correct
55 Incorrect 72 ms 28672 KB Output isn't correct
56 Incorrect 86 ms 28812 KB Output isn't correct
57 Incorrect 67 ms 28704 KB Output isn't correct
58 Incorrect 66 ms 28752 KB Output isn't correct
59 Incorrect 66 ms 28756 KB Output isn't correct
60 Incorrect 84 ms 28676 KB Output isn't correct
61 Incorrect 67 ms 28752 KB Output isn't correct
62 Incorrect 85 ms 28744 KB Output isn't correct
63 Incorrect 66 ms 28832 KB Output isn't correct
64 Incorrect 65 ms 28708 KB Output isn't correct
65 Incorrect 66 ms 28736 KB Output isn't correct
66 Incorrect 70 ms 28888 KB Output isn't correct
67 Incorrect 67 ms 28752 KB Output isn't correct
68 Incorrect 72 ms 28880 KB Output isn't correct
69 Incorrect 67 ms 28756 KB Output isn't correct
70 Incorrect 44 ms 19024 KB Output isn't correct
71 Incorrect 68 ms 28752 KB Output isn't correct
72 Incorrect 66 ms 28756 KB Output isn't correct
73 Incorrect 69 ms 29032 KB Output isn't correct
74 Incorrect 66 ms 28752 KB Output isn't correct
75 Incorrect 66 ms 28712 KB Output isn't correct
76 Incorrect 66 ms 28844 KB Output isn't correct
77 Incorrect 68 ms 28756 KB Output isn't correct
78 Incorrect 67 ms 28756 KB Output isn't correct
79 Incorrect 66 ms 28680 KB Output isn't correct
80 Incorrect 65 ms 28756 KB Output isn't correct
81 Incorrect 65 ms 28744 KB Output isn't correct
82 Incorrect 67 ms 28756 KB Output isn't correct
83 Incorrect 82 ms 28856 KB Output isn't correct
84 Incorrect 69 ms 28756 KB Output isn't correct
85 Incorrect 66 ms 28692 KB Output isn't correct
86 Incorrect 65 ms 28792 KB Output isn't correct
87 Incorrect 71 ms 28684 KB Output isn't correct
88 Incorrect 66 ms 28768 KB Output isn't correct
89 Incorrect 67 ms 28756 KB Output isn't correct
90 Incorrect 45 ms 19176 KB Output isn't correct
91 Incorrect 69 ms 28848 KB Output isn't correct
92 Incorrect 66 ms 28756 KB Output isn't correct
93 Incorrect 80 ms 28752 KB Output isn't correct
94 Incorrect 69 ms 28892 KB Output isn't correct
95 Incorrect 75 ms 28756 KB Output isn't correct
96 Incorrect 68 ms 28756 KB Output isn't correct
97 Incorrect 66 ms 28924 KB Output isn't correct
98 Incorrect 68 ms 28928 KB Output isn't correct
99 Incorrect 79 ms 28752 KB Output isn't correct
100 Incorrect 67 ms 28508 KB Output isn't correct