oj.uz

Submission #494643

# Submission time Handle Problem Language Result Execution time Memory
494643 2021-12-16T00:33:53 Z SirCovidThe19th Brunhilda’s Birthday (BOI13_brunhilda) C++17
80.3175 / 100
 302 ms 80680 KB 
#include <bits/stdc++.h>
using namespace std;

const int mx = 1e7 + 5;
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int n, q; cin >> n >> q; 
    int A[n], bst[mx] = {}, dp[mx];
    for (int i = 0; i < n; i++){
        cin >> A[i];
        for (int mul = A[i] - 1; mul < mx; mul += A[i]) bst[mul] = max(bst[mul], A[i] - 1);
    }
    for (int i = mx - 2; i; i--) bst[i] = max(bst[i], bst[i + 1] - 1);

    fill(dp, dp + mx, 1e9); dp[0] = 0; 
    for (int i = 1; i < mx; i++) dp[i] = dp[i - bst[i]] + 1;
    
    while (q--){
        int x; cin >> x;
        cout<<(dp[x] >= 1e9 ? "oo" : to_string(dp[x]))<<"\n";
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 78568 KB Output is correct
2 Correct 122 ms 78564 KB Output is correct
3 Correct 111 ms 78484 KB Output is correct
4 Correct 94 ms 78588 KB Output is correct
5 Correct 102 ms 78564 KB Output is correct
6 Correct 94 ms 78572 KB Output is correct
7 Correct 109 ms 78560 KB Output is correct
8 Correct 123 ms 78568 KB Output is correct
9 Correct 125 ms 78560 KB Output is correct
10 Correct 132 ms 78568 KB Output is correct
11 Correct 145 ms 78660 KB Output is correct
12 Correct 98 ms 78564 KB Output is correct
13 Correct 221 ms 78544 KB Output is correct
14 Correct 199 ms 78584 KB Output is correct
15 Correct 121 ms 78560 KB Output is correct
16 Correct 122 ms 78588 KB Output is correct
17 Correct 128 ms 78608 KB Output is correct
18 Correct 90 ms 78608 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 78644 KB Output is correct
2 Correct 139 ms 79736 KB Output is correct
3 Correct 243 ms 79268 KB Output is correct
4 Correct 125 ms 78540 KB Output is correct
5 Correct 221 ms 79032 KB Output is correct
6 Correct 110 ms 78540 KB Output is correct
7 Correct 105 ms 78696 KB Output is correct
8 Correct 123 ms 78576 KB Output is correct
9 Correct 218 ms 79284 KB Output is correct
10 Correct 295 ms 79268 KB Output is correct
11 Incorrect 231 ms 78920 KB Output isn't correct
12 Correct 151 ms 78660 KB Output is correct
13 Correct 124 ms 78568 KB Output is correct
14 Correct 127 ms 78600 KB Output is correct
15 Correct 205 ms 78912 KB Output is correct
16 Correct 121 ms 79628 KB Output is correct
17 Correct 229 ms 78676 KB Output is correct
18 Correct 217 ms 79660 KB Output is correct

Subtask #3
41.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 79428 KB Output is correct
2 Correct 287 ms 79340 KB Output is correct
3 Correct 263 ms 79668 KB Output is correct
4 Incorrect 173 ms 79536 KB Output isn't correct
5 Incorrect 165 ms 80676 KB Output isn't correct
6 Correct 250 ms 79536 KB Output is correct
7 Correct 196 ms 80132 KB Output is correct
8 Correct 217 ms 79448 KB Output is correct
9 Correct 218 ms 79472 KB Output is correct
10 Correct 169 ms 78704 KB Output is correct
11 Incorrect 180 ms 78764 KB Output isn't correct
12 Correct 201 ms 78808 KB Output is correct
13 Correct 249 ms 79756 KB Output is correct
14 Correct 160 ms 79760 KB Output is correct
15 Incorrect 229 ms 78824 KB Output isn't correct
16 Correct 245 ms 78772 KB Output is correct
17 Correct 209 ms 79108 KB Output is correct
18 Correct 263 ms 79264 KB Output is correct
19 Incorrect 108 ms 78824 KB Output isn't correct
20 Correct 265 ms 79576 KB Output is correct
21 Incorrect 199 ms 79900 KB Output isn't correct
22 Correct 265 ms 80612 KB Output is correct
23 Correct 157 ms 79812 KB Output is correct
24 Correct 134 ms 79508 KB Output is correct
25 Correct 220 ms 79596 KB Output is correct
26 Incorrect 215 ms 79524 KB Output isn't correct
27 Correct 302 ms 80116 KB Output is correct
28 Incorrect 131 ms 79652 KB Output isn't correct
29 Correct 261 ms 80672 KB Output is correct
30 Correct 266 ms 80232 KB Output is correct
31 Correct 145 ms 79400 KB Output is correct
32 Incorrect 155 ms 79524 KB Output isn't correct
33 Incorrect 139 ms 79508 KB Output isn't correct
34 Correct 213 ms 80220 KB Output is correct
35 Incorrect 136 ms 79624 KB Output isn't correct
36 Correct 260 ms 80504 KB Output is correct
37 Incorrect 149 ms 80680 KB Output isn't correct
38 Correct 225 ms 79540 KB Output is correct
39 Incorrect 130 ms 79584 KB Output isn't correct
40 Correct 198 ms 79588 KB Output is correct
41 Correct 192 ms 80240 KB Output is correct
42 Correct 277 ms 79780 KB Output is correct