oj.uz

Submission #171585

# Submission time Handle Problem Language Result Execution time Memory
171585 2019-12-29T10:17:15 Z mcdx9524 Bomb (IZhO17_bomb) C++14
8 / 100
 1000 ms 760 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) > 100) {
        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
8.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 376 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 Incorrect 132 ms 552 KB Output isn't correct
18 Incorrect 75 ms 592 KB Output isn't correct
19 Incorrect 252 ms 632 KB Output isn't correct
20 Incorrect 281 ms 632 KB Output isn't correct
21 Incorrect 81 ms 504 KB Output isn't correct
22 Correct 184 ms 504 KB Output is correct
23 Incorrect 755 ms 732 KB Output isn't correct
24 Incorrect 192 ms 508 KB Output isn't correct
25 Incorrect 985 ms 632 KB Output isn't correct
26 Execution timed out 1049 ms 632 KB Time limit exceeded
27 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 3 ms 632 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 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 3 ms 632 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 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 3 ms 504 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 504 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 3 ms 376 KB Output isn't correct
42 Execution timed out 1061 ms 632 KB Time limit exceeded
43 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 3 ms 632 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 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 3 ms 632 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 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 3 ms 632 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 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
55 Runtime error 3 ms 632 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 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
59 Runtime error 3 ms 504 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 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
62 Runtime error 3 ms 504 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 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
65 Runtime error 3 ms 632 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 504 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 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
72 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
73 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
74 Runtime error 3 ms 632 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 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
77 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
78 Runtime error 3 ms 504 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 632 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 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
84 Runtime error 3 ms 632 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 632 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 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
89 Runtime error 3 ms 632 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 632 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 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
95 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
96 Runtime error 3 ms 632 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 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
99 Runtime error 3 ms 632 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)