oj.uz

Submission #99837

# Submission time Handle Problem Language Result Execution time Memory
99837 2019-03-07T17:59:25 Z naoai Bomb (IZhO17_bomb) C++14
24 / 100
 242 ms 122532 KB 
#include <bits/stdc++.h>

using namespace std;

#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");

const int nmax = 2500 + 5;

int n, m;
int v[nmax + 1][nmax + 1];
int u[nmax + 1][nmax + 1];
string s[nmax + 1];

void check (int h, int w) {
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            v[i][j] = v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1] + (s[i][j - 1] - '0');
        }
    }

    bool ok = 1;
    for (int i = 1; i <= n - h + 1; ++ i) {
        for (int j = 1; j <= m - w + 1; ++ j) {
            int sum = v[i + h - 1][j + w - 1] - v[i - 1][j + w - 1] - v[i + h - 1][j - 1] + v[i - 1][j - 1];
            if (sum == h * w) {
                ++ u[i][j];
                ++ u[i + h][j + w];
                -- u[i + h][j];
                -- u[i][j + w];
            }
        }
    }

    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            u[i][j] += u[i - 1][j] + u[i][j - 1] - u[i - 1][j - 1];
            if ((u[i][j] == 0) != ((s[i][j - 1] - '0') == 0)) {
                assert(0);
            }
        }
    }
}

int main() {
    fin.sync_with_stdio(false); fin.tie(); fout.tie();
    fin >> n >> m;

    int hmax = n + 1;
    int wmax = m + 1;

    for (int i = 1; i <= n; ++ i)
        fin >> s[i];

    for (int i = 1; i <= n; ++ i) {
        int a = 0;

        s[i] += '0';
        for (int j = 0; j <= m; ++ j) {
            if (j > 0)
                if (s[i][j] == '0' && s[i][j - 1] == '1')
                    wmax = min(wmax, a);

            if (s[i][j] == '1')
                ++ a;
            else
                a = 0;
        }
    }

    s[n + 1].resize(m + 1, '0');

    for (int j = 0; j < m; ++ j) {
        int a = 0;
        for (int i = 1; i <= n + 1; ++ i) {
            if (i > 1)
                if (s[i][j] == '0' && s[i - 1][j] == '1')
                    hmax = min(hmax, a);

            if (s[i][j] == '1')
                ++ a;
            else
                a = 0;
        }
    }

    cout << wmax * hmax << "\n";
    check(hmax, wmax);

    return 0;
}

Compilation message

bomb.cpp: In function 'void check(int, int)':
bomb.cpp:23:10: warning: unused variable 'ok' [-Wunused-variable]
     bool ok = 1;
          ^~

Subtask #1
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 20 ms 20608 KB Output is correct
4 Correct 20 ms 20600 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Runtime error 4 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 5 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 4 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 4 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 4 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Runtime error 5 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Correct 3 ms 640 KB Output is correct
17 Correct 4 ms 1024 KB Output is correct
18 Runtime error 7 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 8 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 8 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 6 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 6 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 5 ms 1752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 8 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 7 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Correct 3 ms 1280 KB Output is correct
27 Correct 7 ms 3712 KB Output is correct
28 Runtime error 13 ms 4608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 24 ms 9336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 19 ms 7680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 14 ms 5504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 16 ms 7168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 21 ms 8448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 13 ms 4864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 19 ms 7168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Correct 12 ms 6272 KB Output is correct
37 Runtime error 5 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Correct 155 ms 62584 KB Output is correct
39 Runtime error 5 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 48 ms 25980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 6 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 7 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Correct 156 ms 62432 KB Output is correct
44 Runtime error 18 ms 6980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Runtime error 174 ms 75128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Correct 190 ms 62456 KB Output is correct
47 Runtime error 165 ms 75784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 235 ms 119928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Correct 164 ms 62584 KB Output is correct
50 Runtime error 220 ms 119928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Runtime error 229 ms 119780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
52 Runtime error 235 ms 119928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Runtime error 208 ms 119928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
54 Runtime error 195 ms 98012 KB Execution killed with signal 11 (could be triggered by violating memory limits)
55 Runtime error 206 ms 98040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
56 Correct 162 ms 62556 KB Output is correct
57 Runtime error 211 ms 100216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
58 Runtime error 214 ms 100048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
59 Runtime error 242 ms 100088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
60 Correct 192 ms 62584 KB Output is correct
61 Correct 171 ms 62456 KB Output is correct
62 Correct 183 ms 62328 KB Output is correct
63 Correct 175 ms 62352 KB Output is correct
64 Correct 178 ms 62328 KB Output is correct
65 Runtime error 218 ms 119800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
66 Runtime error 216 ms 119544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
67 Runtime error 218 ms 119928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
68 Runtime error 219 ms 119672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
69 Runtime error 220 ms 99832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
70 Runtime error 113 ms 56956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
71 Runtime error 189 ms 83064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
72 Runtime error 181 ms 81148 KB Execution killed with signal 11 (could be triggered by violating memory limits)
73 Runtime error 200 ms 77464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
74 Runtime error 199 ms 87672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
75 Runtime error 189 ms 82524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
76 Runtime error 182 ms 86364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
77 Runtime error 196 ms 86372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
78 Runtime error 184 ms 87800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
79 Runtime error 176 ms 77816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
80 Runtime error 182 ms 78412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
81 Runtime error 180 ms 78840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
82 Runtime error 172 ms 84028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
83 Runtime error 187 ms 86908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
84 Runtime error 219 ms 75076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
85 Runtime error 207 ms 98360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
86 Runtime error 205 ms 122532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
87 Runtime error 200 ms 100796 KB Execution killed with signal 11 (could be triggered by violating memory limits)
88 Runtime error 170 ms 76176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
89 Runtime error 223 ms 111324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
90 Runtime error 140 ms 70264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
91 Runtime error 231 ms 105544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
92 Runtime error 222 ms 107896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
93 Runtime error 223 ms 121180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
94 Runtime error 220 ms 109560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
95 Runtime error 194 ms 87672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
96 Runtime error 194 ms 77556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
97 Runtime error 213 ms 122068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
98 Runtime error 186 ms 88696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
99 Runtime error 207 ms 111636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
100 Runtime error 238 ms 120824 KB Execution killed with signal 11 (could be triggered by violating memory limits)