oj.uz

Submission #587323

# Submission time Handle Problem Language Result Execution time Memory
587323 2022-07-01T16:26:44 Z Vanilla Bali Sculptures (APIO15_sculpture) C++17
16 / 100
 1000 ms 239448 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -