답안 #587323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587323	2022-07-01T16:26:44 Z	Vanilla	Bali Sculptures (APIO15_sculpture)	C++17	16 / 100	1000 ms	239448 KB

sculpture

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 1e2 + 2;
const int maxbit = 2048;
bool dp[maxn][maxn][maxbit];
int pref [maxn];
int arr[maxn];
vector <int> v[maxbit][maxbit]; // v[x][y] -> all integer z that x | z = y

int main() {
    int n,a,b;
    cin >> n >> a >> b;
    for (int i = 0; i < maxbit; i++){
        for (int j = 0; j < maxbit; j++){
            v[i][i | j].push_back(j);
        }
    }
    for (int i = 1; i <= n; i++){
        cin >> arr[i];
        pref[i] = pref[i-1] + arr[i];
        dp[i][1][pref[i]] = 1;
    }
    for (int k = 2; k <= b; k++){
        for (int r = 1; r <= n; r++){
            for (int l = 1; l <= r; l++){
                for (int ans = 0; ans < maxbit; ans++){
                    for (int z: v[pref[r] - pref[l - 1]][ans]) dp[r][k][ans] |= dp[l-1][k-1][z];
                    // for (int to = 0; to <= ans; to++){
                }
            }
        }
    }
    int rs = 1e9;
    for (int i = a; i <= b; i++){
        for (int j = 0; j < maxbit; j++)
            rs = min(rs, dp[n][i][j] ? j: (int) 1e9);
    }
    cout << rs << "\n";
    
    return 0;
}

Subtask #1

0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	105 ms	118116 KB	Output is correct
2	Correct	107 ms	118220 KB	Output is correct
3	Correct	105 ms	118144 KB	Output is correct
4	Correct	104 ms	118220 KB	Output is correct
5	Correct	106 ms	118188 KB	Output is correct
6	Correct	110 ms	118628 KB	Output is correct
7	Correct	114 ms	118268 KB	Output is correct
8	Correct	108 ms	118348 KB	Output is correct
9	Correct	111 ms	118356 KB	Output is correct
10	Correct	109 ms	118320 KB	Output is correct
11	Correct	109 ms	118280 KB	Output is correct
12	Correct	107 ms	118264 KB	Output is correct
13	Correct	118 ms	118864 KB	Output is correct
14	Correct	105 ms	118124 KB	Output is correct
15	Correct	108 ms	118196 KB	Output is correct
16	Correct	116 ms	118220 KB	Output is correct
17	Correct	119 ms	118192 KB	Output is correct
18	Correct	109 ms	118200 KB	Output is correct
19	Correct	116 ms	118552 KB	Output is correct
20	Correct	122 ms	118268 KB	Output is correct
21	Correct	115 ms	118440 KB	Output is correct
22	Correct	111 ms	118460 KB	Output is correct
23	Correct	111 ms	118476 KB	Output is correct
24	Correct	104 ms	118344 KB	Output is correct
25	Correct	111 ms	118432 KB	Output is correct
26	Correct	132 ms	118756 KB	Output is correct
27	Runtime error	221 ms	234160 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

Subtask #2

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	107 ms	118136 KB	Output is correct
2	Correct	112 ms	118424 KB	Output is correct
3	Correct	112 ms	118172 KB	Output is correct
4	Correct	103 ms	118108 KB	Output is correct
5	Correct	104 ms	118188 KB	Output is correct
6	Correct	152 ms	118636 KB	Output is correct
7	Correct	110 ms	118356 KB	Output is correct
8	Correct	106 ms	118244 KB	Output is correct
9	Correct	108 ms	118304 KB	Output is correct
10	Correct	106 ms	118348 KB	Output is correct
11	Correct	106 ms	118220 KB	Output is correct
12	Correct	112 ms	118308 KB	Output is correct
13	Correct	119 ms	118800 KB	Output is correct
14	Correct	105 ms	118196 KB	Output is correct
15	Correct	115 ms	118288 KB	Output is correct
16	Correct	115 ms	118208 KB	Output is correct
17	Correct	127 ms	118152 KB	Output is correct
18	Correct	119 ms	118260 KB	Output is correct
19	Correct	124 ms	118604 KB	Output is correct
20	Correct	114 ms	118300 KB	Output is correct
21	Correct	114 ms	118524 KB	Output is correct
22	Correct	116 ms	118524 KB	Output is correct
23	Correct	112 ms	118460 KB	Output is correct
24	Correct	114 ms	118340 KB	Output is correct
25	Correct	129 ms	118416 KB	Output is correct
26	Correct	121 ms	118704 KB	Output is correct
27	Correct	147 ms	119124 KB	Output is correct
28	Correct	121 ms	118808 KB	Output is correct
29	Correct	121 ms	118580 KB	Output is correct
30	Correct	173 ms	119880 KB	Output is correct
31	Correct	255 ms	120408 KB	Output is correct
32	Correct	198 ms	120380 KB	Output is correct
33	Correct	112 ms	118384 KB	Output is correct
34	Correct	224 ms	120376 KB	Output is correct
35	Correct	205 ms	120012 KB	Output is correct
36	Correct	164 ms	119408 KB	Output is correct

Subtask #3

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	119 ms	118212 KB	Output is correct
2	Correct	116 ms	118228 KB	Output is correct
3	Correct	115 ms	118116 KB	Output is correct
4	Correct	116 ms	118120 KB	Output is correct
5	Correct	118 ms	118228 KB	Output is correct
6	Correct	120 ms	118636 KB	Output is correct
7	Correct	117 ms	118328 KB	Output is correct
8	Correct	121 ms	118324 KB	Output is correct
9	Correct	111 ms	118332 KB	Output is correct
10	Correct	116 ms	118432 KB	Output is correct
11	Correct	112 ms	118244 KB	Output is correct
12	Correct	126 ms	118328 KB	Output is correct
13	Correct	177 ms	118824 KB	Output is correct
14	Correct	126 ms	119036 KB	Output is correct
15	Correct	118 ms	118764 KB	Output is correct
16	Correct	126 ms	118660 KB	Output is correct
17	Correct	176 ms	119864 KB	Output is correct
18	Correct	217 ms	120416 KB	Output is correct
19	Correct	222 ms	120316 KB	Output is correct
20	Correct	120 ms	118296 KB	Output is correct
21	Correct	230 ms	120408 KB	Output is correct
22	Correct	206 ms	119920 KB	Output is correct
23	Correct	164 ms	119316 KB	Output is correct
24	Correct	231 ms	120340 KB	Output is correct
25	Correct	229 ms	119772 KB	Output is correct
26	Correct	473 ms	121924 KB	Output is correct
27	Execution timed out	1093 ms	126552 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #4

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	111 ms	118244 KB	Output is correct
2	Correct	111 ms	118328 KB	Output is correct
3	Correct	120 ms	118196 KB	Output is correct
4	Correct	113 ms	118156 KB	Output is correct
5	Correct	114 ms	118208 KB	Output is correct
6	Correct	113 ms	118568 KB	Output is correct
7	Correct	122 ms	118276 KB	Output is correct
8	Correct	121 ms	118300 KB	Output is correct
9	Correct	120 ms	118244 KB	Output is correct
10	Correct	123 ms	118476 KB	Output is correct
11	Correct	121 ms	118252 KB	Output is correct
12	Correct	121 ms	118244 KB	Output is correct
13	Correct	133 ms	118792 KB	Output is correct
14	Correct	112 ms	118220 KB	Output is correct
15	Correct	118 ms	118228 KB	Output is correct
16	Correct	111 ms	118288 KB	Output is correct
17	Correct	111 ms	118180 KB	Output is correct
18	Correct	113 ms	118288 KB	Output is correct
19	Correct	124 ms	118668 KB	Output is correct
20	Correct	118 ms	118364 KB	Output is correct
21	Correct	114 ms	118508 KB	Output is correct
22	Correct	121 ms	118476 KB	Output is correct
23	Correct	116 ms	118404 KB	Output is correct
24	Correct	110 ms	118332 KB	Output is correct
25	Correct	120 ms	118496 KB	Output is correct
26	Correct	118 ms	118700 KB	Output is correct
27	Runtime error	222 ms	239448 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	110 ms	118220 KB	Output is correct
2	Correct	118 ms	118260 KB	Output is correct
3	Correct	112 ms	118180 KB	Output is correct
4	Correct	111 ms	118236 KB	Output is correct
5	Correct	111 ms	118240 KB	Output is correct
6	Correct	131 ms	118704 KB	Output is correct
7	Correct	118 ms	118264 KB	Output is correct
8	Correct	116 ms	118276 KB	Output is correct
9	Correct	111 ms	118280 KB	Output is correct
10	Correct	107 ms	118356 KB	Output is correct
11	Correct	128 ms	118196 KB	Output is correct
12	Correct	123 ms	118280 KB	Output is correct
13	Correct	137 ms	118872 KB	Output is correct
14	Runtime error	190 ms	239424 KB	Execution killed with signal 11
15	Halted	0 ms	0 KB	-