oj.uz

Submission #522429

# Submission time Handle Problem Language Result Execution time Memory
522429 2022-02-05T02:33:37 Z Hamed5001 Brunhilda’s Birthday (BOI13_brunhilda) C++14
77.4603 / 100
 277 ms 79180 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e7+1;
int dp[mxN], dp2[mxN];

void solve() {
    int M, Q;
    cin >> M >> Q;
    vector<int> primes(M);
    for (auto &a : primes) cin >> a;
    
    for (auto p : primes) {
        for (int i = p; i <= mxN; i += p) {
            dp2[i - 1] = max(dp2[i - 1], p - 1);
        }
    }
    for (int i = mxN - 2; i >= 0; --i) {
        dp2[i] = max(dp2[i], dp2[i + 1] - 1);
    }
    
    dp[0] = 0;
    for (int i = 1; i < mxN; ++i) {
        dp[i] = 1e9;
        dp[i] = dp[i - dp2[i]] + 1;
    }
    
    while(Q--) {
        int n;
        cin >> n;
        int ans = dp[n];
        if (ans >= 1e9) cout << "oo\n";
        else cout << dp[n] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 78532 KB Output is correct
2 Correct 104 ms 78472 KB Output is correct
3 Correct 94 ms 78472 KB Output is correct
4 Correct 86 ms 78476 KB Output is correct
5 Correct 96 ms 78560 KB Output is correct
6 Correct 89 ms 78588 KB Output is correct
7 Correct 94 ms 78472 KB Output is correct
8 Correct 114 ms 78472 KB Output is correct
9 Correct 112 ms 78480 KB Output is correct
10 Correct 126 ms 78532 KB Output is correct
11 Correct 123 ms 78516 KB Output is correct
12 Correct 84 ms 78468 KB Output is correct
13 Correct 194 ms 78532 KB Output is correct
14 Correct 194 ms 78476 KB Output is correct
15 Correct 116 ms 78532 KB Output is correct
16 Correct 103 ms 78472 KB Output is correct
17 Correct 105 ms 78488 KB Output is correct
18 Correct 85 ms 78532 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 78532 KB Output is correct
2 Correct 116 ms 78948 KB Output is correct
3 Correct 254 ms 78792 KB Output is correct
4 Correct 111 ms 78488 KB Output is correct
5 Correct 173 ms 78688 KB Output is correct
6 Correct 103 ms 78480 KB Output is correct
7 Correct 96 ms 78528 KB Output is correct
8 Correct 114 ms 78532 KB Output is correct
9 Correct 192 ms 78848 KB Output is correct
10 Correct 241 ms 78788 KB Output is correct
11 Incorrect 238 ms 78644 KB Output isn't correct
12 Correct 145 ms 78472 KB Output is correct
13 Correct 92 ms 78468 KB Output is correct
14 Correct 118 ms 78484 KB Output is correct
15 Correct 193 ms 78656 KB Output is correct
16 Correct 105 ms 78892 KB Output is correct
17 Correct 208 ms 78468 KB Output is correct
18 Correct 192 ms 78880 KB Output is correct

Subtask #3
38.5714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 78808 KB Output is correct
2 Correct 240 ms 78828 KB Output is correct
3 Correct 263 ms 78900 KB Output is correct
4 Incorrect 161 ms 78744 KB Output isn't correct
5 Incorrect 127 ms 79172 KB Output isn't correct
6 Correct 216 ms 78788 KB Output is correct
7 Correct 180 ms 79000 KB Output is correct
8 Correct 199 ms 78788 KB Output is correct
9 Correct 212 ms 78920 KB Output is correct
10 Correct 162 ms 78624 KB Output is correct
11 Incorrect 145 ms 78652 KB Output isn't correct
12 Correct 185 ms 78660 KB Output is correct
13 Correct 247 ms 78856 KB Output is correct
14 Correct 152 ms 79120 KB Output is correct
15 Incorrect 195 ms 78624 KB Output isn't correct
16 Correct 224 ms 78656 KB Output is correct
17 Correct 188 ms 78788 KB Output is correct
18 Correct 241 ms 78816 KB Output is correct
19 Incorrect 100 ms 78592 KB Output isn't correct
20 Correct 247 ms 78948 KB Output is correct
21 Incorrect 180 ms 79180 KB Output isn't correct
22 Correct 255 ms 79152 KB Output is correct
23 Correct 133 ms 78852 KB Output is correct
24 Correct 114 ms 78752 KB Output is correct
25 Incorrect 177 ms 78868 KB Output isn't correct
26 Incorrect 169 ms 78816 KB Output isn't correct
27 Correct 277 ms 79044 KB Output is correct
28 Incorrect 113 ms 78860 KB Output isn't correct
29 Correct 239 ms 79100 KB Output is correct
30 Correct 220 ms 79020 KB Output is correct
31 Correct 129 ms 78784 KB Output is correct
32 Incorrect 140 ms 78776 KB Output isn't correct
33 Incorrect 115 ms 78788 KB Output isn't correct
34 Correct 180 ms 79004 KB Output is correct
35 Incorrect 119 ms 78788 KB Output isn't correct
36 Correct 247 ms 79044 KB Output is correct
37 Incorrect 129 ms 79172 KB Output isn't correct
38 Correct 214 ms 78772 KB Output is correct
39 Incorrect 125 ms 78896 KB Output isn't correct
40 Correct 188 ms 78768 KB Output is correct
41 Correct 168 ms 79004 KB Output is correct
42 Incorrect 240 ms 79000 KB Output isn't correct