oj.uz

Submission #171584

# Submission time Handle Problem Language Result Execution time Memory
171584 2019-12-29T10:16:32 Z mcdx9524 Bomb (IZhO17_bomb) C++14
7 / 100
 4 ms 636 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2500 + 7;

char a[N][N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    if (n == 1 || m == 1) {
        vector <int> aa;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char x;
                cin >> x;
                aa.push_back(x - '0');
            }
        }
        int cnt = 1;
        int res = 1e9;
        for (int i = 1; i < max(n, m); i++) {
            if (aa[i] != aa[i - 1]) {
                if (aa[i - 1] == 1) {
                    res = min(res, cnt);
                }
                cnt = 0;
            }
            cnt++;
        }
        if (aa[max(n, m) - 1] == 1) {
            res = min(res, cnt);
        }
        cout << res << '\n';
        return 0;
    }
    if (max(n, m) > 20) {
        assert(0);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= m; y++) {
            char b[n + 7][m + 7];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    b[i][j] = a[i][j];
                }
            }
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (i + x - 1 > n || j + y - 1 > m) {
                        continue;
                    }
                    bool bad = false;
                    for (int r = i; r <= i + x - 1; r++) {
                        for (int c = j; c <= j + y - 1; c++) {
                            if (b[r][c] != '1') {
                                bad = true;
                            }
                            if (bad) break;
                        }
                        if (bad) break;
                    }
                    if (bad) continue;
                    for (int r = i; r <= i + x - 1; r++) {
                        for (int c = j; c <= j + y - 1; c++) {
                            b[r][c] = '2';
                        }
                    }
                }
            }
            for (int i = n; i >= 1; i--) {
                for (int j = m; j >= 1; j--) {
                    if (i - x + 1 < 1 || j - y + 1 < 1) {
                        continue;
                    }
                    if (b[i][j] == '1') {
                        for (int r = i; r >= i - x + 1; r--) {
                            for (int c = j; c >= j - y + 1; c--) {
                                b[i][j] = '2';
                            }
                        }
                    }
                }
            }
            bool good = true;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (a[i][j] == '0') {
                        continue;
                    }
                    if (a[i][j] == '1' && b[i][j] == '2') {
                        continue;
                    }
                    good = false;
                    if (!good) break;
                }
                if (!good) break;
            }
            if (good) {
                ans = max(ans, x * y);
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
7.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 372 KB Output is correct
7 Incorrect 2 ms 376 KB Output isn't correct
8 Incorrect 3 ms 376 KB Output isn't correct
9 Incorrect 3 ms 376 KB Output isn't correct
10 Incorrect 2 ms 376 KB Output isn't correct
11 Incorrect 3 ms 376 KB Output isn't correct
12 Incorrect 2 ms 376 KB Output isn't correct
13 Incorrect 2 ms 376 KB Output isn't correct
14 Correct 2 ms 376 KB Output is correct
15 Incorrect 3 ms 376 KB Output isn't correct
16 Incorrect 4 ms 376 KB Output isn't correct
17 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 3 ms 636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Incorrect 3 ms 376 KB Output isn't correct
38 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Incorrect 3 ms 376 KB Output isn't correct
40 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Incorrect 4 ms 376 KB Output isn't correct
42 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
54 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
55 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Runtime error 3 ms 636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
57 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
58 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
59 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
60 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
61 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
62 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
63 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
64 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
65 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
66 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
67 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
68 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
69 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
70 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
71 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
72 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
73 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
74 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
75 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
76 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
77 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
78 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
79 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
80 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
81 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
82 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
83 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
84 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
85 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
86 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
87 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
88 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
89 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
90 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
91 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
92 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
93 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
94 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
95 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
96 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
97 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
98 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
99 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
100 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)