답안 #87289 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87289	2018-11-30T07:39:27 Z	Yaroslaff	Bomb (IZhO17_bomb)	C++14	49 / 100	514 ms	132096 KB

bomb

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define ll long long
//#define int ll
#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 = 2507;

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);
#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], 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], 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], 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], 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, 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
49.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	768 KB	Output is correct
3	Correct	29 ms	30768 KB	Output is correct
4	Correct	29 ms	30768 KB	Output is correct
5	Correct	2 ms	30768 KB	Output is correct
6	Correct	2 ms	30768 KB	Output is correct
7	Correct	2 ms	30768 KB	Output is correct
8	Correct	2 ms	30768 KB	Output is correct
9	Correct	3 ms	30768 KB	Output is correct
10	Correct	2 ms	30768 KB	Output is correct
11	Correct	2 ms	30768 KB	Output is correct
12	Correct	2 ms	30768 KB	Output is correct
13	Correct	2 ms	30768 KB	Output is correct
14	Correct	2 ms	30768 KB	Output is correct
15	Correct	2 ms	30768 KB	Output is correct
16	Correct	2 ms	30768 KB	Output is correct
17	Correct	3 ms	30768 KB	Output is correct
18	Correct	3 ms	30768 KB	Output is correct
19	Correct	3 ms	30768 KB	Output is correct
20	Correct	3 ms	30768 KB	Output is correct
21	Correct	3 ms	30768 KB	Output is correct
22	Correct	3 ms	30768 KB	Output is correct
23	Correct	4 ms	30768 KB	Output is correct
24	Correct	3 ms	30768 KB	Output is correct
25	Correct	3 ms	30768 KB	Output is correct
26	Correct	3 ms	30768 KB	Output is correct
27	Correct	7 ms	30768 KB	Output is correct
28	Correct	7 ms	30768 KB	Output is correct
29	Correct	9 ms	30768 KB	Output is correct
30	Correct	10 ms	30768 KB	Output is correct
31	Correct	8 ms	30768 KB	Output is correct
32	Correct	8 ms	30768 KB	Output is correct
33	Correct	10 ms	30768 KB	Output is correct
34	Correct	7 ms	30768 KB	Output is correct
35	Correct	10 ms	30768 KB	Output is correct
36	Correct	13 ms	30768 KB	Output is correct
37	Correct	2 ms	30768 KB	Output is correct
38	Correct	514 ms	88972 KB	Output is correct
39	Correct	2 ms	88972 KB	Output is correct
40	Correct	55 ms	88972 KB	Output is correct
41	Correct	2 ms	88972 KB	Output is correct
42	Correct	3 ms	88972 KB	Output is correct
43	Correct	407 ms	95764 KB	Output is correct
44	Correct	12 ms	95764 KB	Output is correct
45	Correct	380 ms	102256 KB	Output is correct
46	Correct	344 ms	108180 KB	Output is correct
47	Correct	426 ms	114332 KB	Output is correct
48	Correct	365 ms	120552 KB	Output is correct
49	Correct	491 ms	126532 KB	Output is correct
50	Runtime error	389 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.
51	Runtime error	383 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.
52	Runtime error	365 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.
53	Runtime error	395 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.
54	Runtime error	289 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.
55	Runtime error	273 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.
56	Runtime error	514 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	289 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	284 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	279 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	352 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	496 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	507 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	503 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	272 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	369 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	367 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	405 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	400 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	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.
70	Runtime error	154 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	266 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	272 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	283 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	279 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	312 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	297 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	289 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	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.
79	Runtime error	200 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	190 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	204 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	291 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	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.
84	Runtime error	212 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	283 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	463 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	272 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	304 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	346 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	167 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	322 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	350 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	506 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	357 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	300 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	296 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	485 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	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.
99	Runtime error	343 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	461 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.

답안 #87289

Compilation message

Subtask #1 49.0 / 100.0

Subtask #1
49.0 / 100.0