oj.uz

Submission #87293

# Submission time Handle Problem Language Result Execution time Memory
87293 2018-11-30T07:46:13 Z Yaroslaff Bomb (IZhO17_bomb) C++14
50 / 100
 457 ms 132096 KB 
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define ll long long
#define int short int
#define ld long double
#define null nullptr
#define endl '\n'

using namespace std;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

//const int M = 1e9 + 7;
const int N = 2502;

int n, m, x[N][N], l[N][N], r[N][N], res[N], ans;
string s[N];

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
//#else
//    freopen("bomb.in","r",stdin);
//    freopen("bomb.out","w",stdout);
#endif
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> s[i];res[i + 1] = N;
        for (int j = 0; j < m; j++)
            x[i][j] = s[i][j] - '0';
    }
    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++){
        if (!x[i][j]) l[i][j] = 0;
        else l[i][j] = (j ? l[i][j - 1] : 0) + 1;
    }
    for (int i = n - 1; i >= 0; i--)
    for (int j = m - 1; j >= 0; j--){
        if (!x[i][j]) r[i][j] = 0;
        else r[i][j] = r[i][j + 1] + 1;
    }
    for (int j = 0; j < m; j++){
        int tl = N;
        int tr = N;
        int p = -1;
        for (int i = 0; i <= n; i++){
            if (i != n && x[i][j] == 1){
                res[1] = min(res[1], (int)(l[i][j] + r[i][j] - 1));
                int len = i - p;
                tl = min(tl, l[i][j]);
                tr = min(tr, r[i][j]);
                res[len] = min(res[len], (int)(tl + tr - 1));
            }
            if (i == n || x[i][j] == 0){
                int l = i - p;
//                cerr << l << endl;
                if (l != 1) res[l] = 0;
                tl = tr = N;
                p = i;
            }
        }
        tl = N;
        tr = N;
        p = n;
        for (int i = n - 1; i >= -1; i--){
            if (i != -1 && x[i][j] == 1){
                res[1] = min(res[1], (int)(l[i][j] + r[i][j] - 1));
                int len = p - i;
                tl = min(tl, l[i][j]);
                tr = min(tr, r[i][j]);
                res[len] = min(res[len], (int)(tl + tr - 1));
            }
            if (i == -1 || x[i][j] == 0){
                int l = p - i;
//                cerr << l << endl;
                if (l != 1) res[l] = 0;
                tl = tr = N;
                p = i;
            }
        }
    }
    for (int i = 2; i <= n; i++)
        res[i] = min(res[i], res[i - 1]);
    for (int i = 1; i <= n; i++)
        ans = max(ans, (int)(i*res[i]));
    cout << ans;
    return 0;
}

Compilation message

bomb.cpp:22:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 27 ms 30536 KB Output is correct
4 Correct 29 ms 30576 KB Output is correct
5 Correct 2 ms 30576 KB Output is correct
6 Correct 2 ms 30576 KB Output is correct
7 Correct 2 ms 30576 KB Output is correct
8 Correct 2 ms 30576 KB Output is correct
9 Correct 2 ms 30576 KB Output is correct
10 Correct 3 ms 30576 KB Output is correct
11 Correct 3 ms 30576 KB Output is correct
12 Correct 2 ms 30576 KB Output is correct
13 Correct 2 ms 30576 KB Output is correct
14 Correct 2 ms 30576 KB Output is correct
15 Correct 2 ms 30576 KB Output is correct
16 Correct 2 ms 30576 KB Output is correct
17 Correct 3 ms 30576 KB Output is correct
18 Correct 3 ms 30576 KB Output is correct
19 Correct 3 ms 30576 KB Output is correct
20 Correct 3 ms 30576 KB Output is correct
21 Correct 2 ms 30576 KB Output is correct
22 Correct 3 ms 30576 KB Output is correct
23 Correct 3 ms 30576 KB Output is correct
24 Correct 3 ms 30576 KB Output is correct
25 Correct 3 ms 30576 KB Output is correct
26 Correct 3 ms 30576 KB Output is correct
27 Correct 7 ms 30576 KB Output is correct
28 Correct 6 ms 30576 KB Output is correct
29 Correct 9 ms 30576 KB Output is correct
30 Correct 9 ms 30576 KB Output is correct
31 Correct 7 ms 30576 KB Output is correct
32 Correct 8 ms 30576 KB Output is correct
33 Correct 9 ms 30576 KB Output is correct
34 Correct 6 ms 30576 KB Output is correct
35 Correct 9 ms 30576 KB Output is correct
36 Correct 12 ms 30576 KB Output is correct
37 Correct 2 ms 30576 KB Output is correct
38 Incorrect 430 ms 51820 KB Output isn't correct
39 Correct 2 ms 51820 KB Output is correct
40 Incorrect 47 ms 51820 KB Output isn't correct
41 Correct 2 ms 51820 KB Output is correct
42 Correct 3 ms 51820 KB Output is correct
43 Incorrect 359 ms 58704 KB Output isn't correct
44 Correct 11 ms 58704 KB Output is correct
45 Incorrect 326 ms 64956 KB Output isn't correct
46 Correct 290 ms 71140 KB Output is correct
47 Incorrect 327 ms 77252 KB Output isn't correct
48 Correct 308 ms 83364 KB Output is correct
49 Correct 439 ms 89432 KB Output is correct
50 Correct 318 ms 95564 KB Output is correct
51 Correct 322 ms 101696 KB Output is correct
52 Correct 353 ms 107800 KB Output is correct
53 Correct 312 ms 113924 KB Output is correct
54 Correct 232 ms 120036 KB Output is correct
55 Correct 252 ms 126148 KB Output is correct
56 Runtime error 432 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
57 Runtime error 226 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
58 Runtime error 238 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
59 Runtime error 225 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
60 Runtime error 294 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
61 Runtime error 430 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
62 Runtime error 441 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
63 Runtime error 457 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
64 Runtime error 236 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
65 Runtime error 303 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
66 Runtime error 307 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
67 Runtime error 337 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
68 Runtime error 364 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
69 Runtime error 233 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
70 Runtime error 111 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
71 Runtime error 201 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
72 Runtime error 229 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
73 Runtime error 231 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
74 Runtime error 246 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
75 Runtime error 250 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
76 Runtime error 244 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
77 Runtime error 249 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
78 Runtime error 238 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
79 Runtime error 149 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
80 Runtime error 148 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
81 Runtime error 161 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
82 Runtime error 250 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
83 Runtime error 242 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
84 Runtime error 145 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
85 Runtime error 234 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
86 Runtime error 433 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
87 Runtime error 230 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
88 Runtime error 246 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
89 Runtime error 288 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
90 Runtime error 139 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
91 Runtime error 268 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
92 Runtime error 286 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
93 Runtime error 398 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
94 Runtime error 292 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
95 Runtime error 241 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
96 Runtime error 238 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
97 Runtime error 412 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
98 Runtime error 244 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
99 Runtime error 281 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
100 Runtime error 392 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.