답안 #527574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
527574	2022-02-17T17:07:12 Z	SlavicG	Bali Sculptures (APIO15_sculpture)	C++17	16 / 100	822 ms	170460 KB

sculpture

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 100, K = 2200;
int p[N];
int sum(int l, int r) {
    return p[r] - (l ? p[l - 1] : 0);
}

//dp[index][OR][number of subarrays] = 1 if possible to obtain such partition

int dp[N][K][N];
void solve() { 
    int n, A, B;
    cin >> n >> A >> B;
    vector<int> a(n);
    for(int i = 0;i < n; ++i) {
        cin >> a[i];
        p[i] = (i ? p[i - 1] : 0) + a[i];
    }

    dp[0][0][0] = 1;

    for(int i = 1; i <= n; ++i) {
        for(int j = 0;j < i; ++j) {
            for(int OR = 0; OR < K; ++OR) {
                int s = sum(j, i - 1);
                for(int k = 0; k < B; ++k) {
                    dp[i][OR | s][k + 1] |= dp[j][OR][k]; 
                }
            }
        }
    }
    int ans = INT_MAX;
    for(int i = A; i <= B; ++i) {
        for(int OR = 0; OR < K; ++OR) {
            if(dp[n][OR][i]) ans = min(ans, OR);
        }
    }
    cout << ans << "\n";
} 
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

Subtask #1
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5452 KB	Output is correct
2	Correct	3 ms	7116 KB	Output is correct
3	Correct	1 ms	1100 KB	Output is correct
4	Correct	2 ms	4556 KB	Output is correct
5	Correct	4 ms	8944 KB	Output is correct
6	Correct	14 ms	13204 KB	Output is correct
7	Correct	9 ms	14924 KB	Output is correct
8	Correct	12 ms	17484 KB	Output is correct
9	Correct	10 ms	17484 KB	Output is correct
10	Correct	12 ms	17436 KB	Output is correct
11	Correct	10 ms	17484 KB	Output is correct
12	Correct	10 ms	17484 KB	Output is correct
13	Correct	26 ms	17548 KB	Output is correct
14	Correct	3 ms	5452 KB	Output is correct
15	Correct	3 ms	5452 KB	Output is correct
16	Correct	3 ms	5452 KB	Output is correct
17	Correct	2 ms	4556 KB	Output is correct
18	Correct	4 ms	8908 KB	Output is correct
19	Correct	14 ms	13236 KB	Output is correct
20	Correct	8 ms	14924 KB	Output is correct
21	Correct	19 ms	17448 KB	Output is correct
22	Correct	14 ms	17428 KB	Output is correct
23	Correct	14 ms	17488 KB	Output is correct
24	Correct	10 ms	17468 KB	Output is correct
25	Correct	17 ms	17548 KB	Output is correct
26	Correct	22 ms	17460 KB	Output is correct
27	Runtime error	2 ms	460 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	5396 KB	Output is correct
2	Correct	3 ms	7116 KB	Output is correct
3	Correct	1 ms	1100 KB	Output is correct
4	Correct	2 ms	4556 KB	Output is correct
5	Correct	4 ms	8908 KB	Output is correct
6	Correct	13 ms	13132 KB	Output is correct
7	Correct	10 ms	14924 KB	Output is correct
8	Correct	10 ms	17516 KB	Output is correct
9	Correct	10 ms	17464 KB	Output is correct
10	Correct	13 ms	17484 KB	Output is correct
11	Correct	10 ms	17436 KB	Output is correct
12	Correct	10 ms	17488 KB	Output is correct
13	Correct	25 ms	17484 KB	Output is correct
14	Correct	3 ms	5436 KB	Output is correct
15	Correct	3 ms	5452 KB	Output is correct
16	Correct	3 ms	5452 KB	Output is correct
17	Correct	2 ms	4556 KB	Output is correct
18	Correct	4 ms	8908 KB	Output is correct
19	Correct	15 ms	13252 KB	Output is correct
20	Correct	8 ms	14924 KB	Output is correct
21	Correct	15 ms	17524 KB	Output is correct
22	Correct	14 ms	17416 KB	Output is correct
23	Correct	15 ms	17412 KB	Output is correct
24	Correct	10 ms	17464 KB	Output is correct
25	Correct	19 ms	17484 KB	Output is correct
26	Correct	22 ms	17472 KB	Output is correct
27	Correct	33 ms	18412 KB	Output is correct
28	Correct	38 ms	21728 KB	Output is correct
29	Correct	42 ms	32964 KB	Output is correct
30	Correct	105 ms	36472 KB	Output is correct
31	Correct	138 ms	43380 KB	Output is correct
32	Correct	171 ms	43332 KB	Output is correct
33	Correct	50 ms	43332 KB	Output is correct
34	Correct	144 ms	43400 KB	Output is correct
35	Correct	143 ms	43332 KB	Output is correct
36	Correct	115 ms	43380 KB	Output is correct

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5452 KB	Output is correct
2	Correct	5 ms	7124 KB	Output is correct
3	Correct	1 ms	1100 KB	Output is correct
4	Correct	2 ms	4556 KB	Output is correct
5	Correct	4 ms	8908 KB	Output is correct
6	Correct	13 ms	13248 KB	Output is correct
7	Correct	8 ms	14924 KB	Output is correct
8	Correct	11 ms	17484 KB	Output is correct
9	Correct	10 ms	17484 KB	Output is correct
10	Correct	11 ms	17480 KB	Output is correct
11	Correct	10 ms	17484 KB	Output is correct
12	Correct	10 ms	17488 KB	Output is correct
13	Correct	25 ms	17460 KB	Output is correct
14	Correct	30 ms	18368 KB	Output is correct
15	Correct	30 ms	21736 KB	Output is correct
16	Correct	45 ms	33212 KB	Output is correct
17	Correct	105 ms	36416 KB	Output is correct
18	Correct	176 ms	43452 KB	Output is correct
19	Correct	158 ms	43380 KB	Output is correct
20	Correct	39 ms	43332 KB	Output is correct
21	Correct	158 ms	43332 KB	Output is correct
22	Correct	151 ms	43332 KB	Output is correct
23	Correct	109 ms	43332 KB	Output is correct
24	Correct	150 ms	43740 KB	Output is correct
25	Correct	185 ms	55724 KB	Output is correct
26	Correct	260 ms	66832 KB	Output is correct
27	Correct	432 ms	77988 KB	Output is correct
28	Runtime error	822 ms	170460 KB	Execution killed with signal 11
29	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	5452 KB	Output is correct
2	Correct	4 ms	7116 KB	Output is correct
3	Correct	1 ms	1100 KB	Output is correct
4	Correct	3 ms	4556 KB	Output is correct
5	Correct	4 ms	8908 KB	Output is correct
6	Correct	14 ms	13236 KB	Output is correct
7	Correct	9 ms	14924 KB	Output is correct
8	Correct	10 ms	17496 KB	Output is correct
9	Correct	11 ms	17448 KB	Output is correct
10	Correct	10 ms	17408 KB	Output is correct
11	Correct	10 ms	17492 KB	Output is correct
12	Correct	11 ms	17484 KB	Output is correct
13	Correct	29 ms	17584 KB	Output is correct
14	Correct	3 ms	5452 KB	Output is correct
15	Correct	3 ms	5452 KB	Output is correct
16	Correct	3 ms	5456 KB	Output is correct
17	Correct	2 ms	4556 KB	Output is correct
18	Correct	5 ms	8900 KB	Output is correct
19	Correct	13 ms	13252 KB	Output is correct
20	Correct	10 ms	14924 KB	Output is correct
21	Correct	23 ms	17536 KB	Output is correct
22	Correct	16 ms	17428 KB	Output is correct
23	Correct	19 ms	17452 KB	Output is correct
24	Correct	10 ms	17476 KB	Output is correct
25	Correct	14 ms	17476 KB	Output is correct
26	Correct	23 ms	17484 KB	Output is correct
27	Runtime error	2 ms	460 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

Subtask #5
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5440 KB	Output is correct
2	Correct	4 ms	7116 KB	Output is correct
3	Correct	1 ms	1108 KB	Output is correct
4	Correct	2 ms	4556 KB	Output is correct
5	Correct	5 ms	8912 KB	Output is correct
6	Correct	14 ms	13156 KB	Output is correct
7	Correct	11 ms	14924 KB	Output is correct
8	Correct	11 ms	17484 KB	Output is correct
9	Correct	13 ms	17540 KB	Output is correct
10	Correct	11 ms	17472 KB	Output is correct
11	Correct	11 ms	17476 KB	Output is correct
12	Correct	11 ms	17568 KB	Output is correct
13	Correct	25 ms	17548 KB	Output is correct
14	Runtime error	2 ms	460 KB	Execution killed with signal 11
15	Halted	0 ms	0 KB	-

답안 #527574

Compilation message

Subtask #1 0 / 9.0

Subtask #2 16.0 / 16.0

Subtask #3 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
0 / 21.0

Subtask #4
0 / 25.0

Subtask #5
0 / 29.0