답안 #31400 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31400	2017-08-21T06:45:54 Z	nickyrio	Bali Sculptures (APIO15_sculpture)	C++14	37 / 100	0 ms	6192 KB

sculpture

#include <bits/stdc++.h>
#define N 2020
#define FOR(i, a, b) for (int i = a; i<=b; i++)
#define FORD(i, a, b) for (int i = a; i>=b; i--)
#define REP(i, a) for (int i = 1; i<=a; i++)

using namespace std;

int f[N], c[N], n, a, b;
long long s[N];
bool g[N][N];

const int inf = 1e9;

bool solve1(int k, long long limit) { // N^2 && a == 1
    REP(i, n) f[i] = inf;
    f[0] = 0;
    REP(i, n) FOR(j, 1, i)
        if ((((s[i] - s[j - 1]) | limit) >> k) == (limit >> k)) {
        f[i] = min(f[i], f[j - 1] + 1);
    }
    return f[n] <=b;
}

bool solve2(int k, long long limit) { //N^3 && a > 1
    FOR(i, 0, n) REP(j, n) g[i][j] = false;
    g[0][0] = true;
    FOR(kk, 1, b)
        FOR(j, 1, n)
            FOR(i, j, n) {
        if (((((s[i] - s[j - 1]) | limit) >> k) == (limit >> k)) && g[kk - 1][j - 1])
            g[kk][i] = true;
    }
    FOR(i, a, b) if (g[i][n]) return true;
    return false;
}

bool ok(int k, long long limit) {
    if (a == 1) return solve1(k, limit);
    return solve2(k, limit);
}

int main() {
    //freopen("SCULPTURE.inp","r",stdin);
    //freopen("SCULPTURE.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>n>>a>>b;
    REP(i, n) cin>>c[i];
    long long ans = 0;
    FOR(i, 1, n) s[i] = c[i] + s[i - 1];
    FORD(k, 31, 0) {
        if (!ok(k, ans))
            ans |= (1ll << k);
    }
    cout<<ans;
}

Subtask #1
0 / 9.0

#	결과	메모리	Grader output
1	Correct	6192 KB	Output is correct
2	Correct	6192 KB	Output is correct
3	Correct	6192 KB	Output is correct
4	Correct	6192 KB	Output is correct
5	Correct	6192 KB	Output is correct
6	Correct	6192 KB	Output is correct
7	Correct	6192 KB	Output is correct
8	Correct	6192 KB	Output is correct
9	Correct	6192 KB	Output is correct
10	Correct	6192 KB	Output is correct
11	Correct	6192 KB	Output is correct
12	Correct	6192 KB	Output is correct
13	Correct	6192 KB	Output is correct
14	Correct	6192 KB	Output is correct
15	Correct	6192 KB	Output is correct
16	Correct	6192 KB	Output is correct
17	Correct	6192 KB	Output is correct
18	Correct	6192 KB	Output is correct
19	Correct	6192 KB	Output is correct
20	Correct	6192 KB	Output is correct
21	Correct	6192 KB	Output is correct
22	Correct	6192 KB	Output is correct
23	Correct	6192 KB	Output is correct
24	Correct	6192 KB	Output is correct
25	Correct	6192 KB	Output is correct
26	Correct	6192 KB	Output is correct
27	Correct	6192 KB	Output is correct
28	Correct	6192 KB	Output is correct
29	Correct	6192 KB	Output is correct
30	Correct	6192 KB	Output is correct
31	Correct	6192 KB	Output is correct
32	Incorrect	6192 KB	Output isn't correct
33	Halted	0 KB	-

Subtask #2
16.0 / 16.0

#	결과	메모리	Grader output
1	Correct	6192 KB	Output is correct
2	Correct	6192 KB	Output is correct
3	Correct	6192 KB	Output is correct
4	Correct	6192 KB	Output is correct
5	Correct	6192 KB	Output is correct
6	Correct	6192 KB	Output is correct
7	Correct	6192 KB	Output is correct
8	Correct	6192 KB	Output is correct
9	Correct	6192 KB	Output is correct
10	Correct	6192 KB	Output is correct
11	Correct	6192 KB	Output is correct
12	Correct	6192 KB	Output is correct
13	Correct	6192 KB	Output is correct
14	Correct	6192 KB	Output is correct
15	Correct	6192 KB	Output is correct
16	Correct	6192 KB	Output is correct
17	Correct	6192 KB	Output is correct
18	Correct	6192 KB	Output is correct
19	Correct	6192 KB	Output is correct
20	Correct	6192 KB	Output is correct
21	Correct	6192 KB	Output is correct
22	Correct	6192 KB	Output is correct
23	Correct	6192 KB	Output is correct
24	Correct	6192 KB	Output is correct
25	Correct	6192 KB	Output is correct
26	Correct	6192 KB	Output is correct
27	Correct	6192 KB	Output is correct
28	Correct	6192 KB	Output is correct
29	Correct	6192 KB	Output is correct
30	Correct	6192 KB	Output is correct
31	Correct	6192 KB	Output is correct
32	Correct	6192 KB	Output is correct
33	Correct	6192 KB	Output is correct
34	Correct	6192 KB	Output is correct
35	Correct	6192 KB	Output is correct
36	Correct	6192 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	메모리	Grader output
1	Correct	6192 KB	Output is correct
2	Correct	6192 KB	Output is correct
3	Correct	6192 KB	Output is correct
4	Correct	6192 KB	Output is correct
5	Correct	6192 KB	Output is correct
6	Correct	6192 KB	Output is correct
7	Correct	6192 KB	Output is correct
8	Correct	6192 KB	Output is correct
9	Correct	6192 KB	Output is correct
10	Correct	6192 KB	Output is correct
11	Correct	6192 KB	Output is correct
12	Correct	6192 KB	Output is correct
13	Correct	6192 KB	Output is correct
14	Correct	6192 KB	Output is correct
15	Correct	6192 KB	Output is correct
16	Correct	6192 KB	Output is correct
17	Correct	6192 KB	Output is correct
18	Correct	6192 KB	Output is correct
19	Correct	6192 KB	Output is correct
20	Correct	6192 KB	Output is correct
21	Correct	6192 KB	Output is correct
22	Correct	6192 KB	Output is correct
23	Correct	6192 KB	Output is correct
24	Correct	6192 KB	Output is correct
25	Correct	6192 KB	Output is correct
26	Correct	6192 KB	Output is correct
27	Correct	6192 KB	Output is correct
28	Correct	6192 KB	Output is correct
29	Correct	6192 KB	Output is correct
30	Correct	6192 KB	Output is correct
31	Correct	6192 KB	Output is correct
32	Correct	6192 KB	Output is correct

Subtask #4
0 / 25.0

#	결과	메모리	Grader output
1	Correct	6192 KB	Output is correct
2	Correct	6192 KB	Output is correct
3	Correct	6192 KB	Output is correct
4	Correct	6192 KB	Output is correct
5	Correct	6192 KB	Output is correct
6	Correct	6192 KB	Output is correct
7	Correct	6192 KB	Output is correct
8	Correct	6192 KB	Output is correct
9	Correct	6192 KB	Output is correct
10	Correct	6192 KB	Output is correct
11	Correct	6192 KB	Output is correct
12	Correct	6192 KB	Output is correct
13	Correct	6192 KB	Output is correct
14	Correct	6192 KB	Output is correct
15	Correct	6192 KB	Output is correct
16	Correct	6192 KB	Output is correct
17	Correct	6192 KB	Output is correct
18	Correct	6192 KB	Output is correct
19	Correct	6192 KB	Output is correct
20	Correct	6192 KB	Output is correct
21	Correct	6192 KB	Output is correct
22	Correct	6192 KB	Output is correct
23	Correct	6192 KB	Output is correct
24	Correct	6192 KB	Output is correct
25	Correct	6192 KB	Output is correct
26	Correct	6192 KB	Output is correct
27	Correct	6192 KB	Output is correct
28	Correct	6192 KB	Output is correct
29	Correct	6192 KB	Output is correct
30	Correct	6192 KB	Output is correct
31	Correct	6192 KB	Output is correct
32	Incorrect	6192 KB	Output isn't correct
33	Halted	0 KB	-

Subtask #5
0 / 29.0

#	결과	메모리	Grader output
1	Correct	6192 KB	Output is correct
2	Correct	6192 KB	Output is correct
3	Correct	6192 KB	Output is correct
4	Correct	6192 KB	Output is correct
5	Correct	6192 KB	Output is correct
6	Correct	6192 KB	Output is correct
7	Correct	6192 KB	Output is correct
8	Correct	6192 KB	Output is correct
9	Correct	6192 KB	Output is correct
10	Correct	6192 KB	Output is correct
11	Correct	6192 KB	Output is correct
12	Correct	6192 KB	Output is correct
13	Correct	6192 KB	Output is correct
14	Correct	6192 KB	Output is correct
15	Correct	6192 KB	Output is correct
16	Correct	6192 KB	Output is correct
17	Correct	6192 KB	Output is correct
18	Correct	6192 KB	Output is correct
19	Incorrect	6192 KB	Output isn't correct
20	Halted	0 KB	-

답안 #31400

Compilation message

Subtask #1 0 / 9.0

Subtask #2 16.0 / 16.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 25.0

Subtask #5 0 / 29.0

Subtask #1
0 / 9.0

Subtask #2
16.0 / 16.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 25.0

Subtask #5
0 / 29.0