oj.uz

Submission #522428

# Submission time Handle Problem Language Result Execution time Memory
522428 2022-02-05T02:29:54 Z Hamed5001 Brunhilda’s Birthday (BOI13_brunhilda) C++14
76.3492 / 100
 267 ms 80688 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 85 ms 78524 KB Output is correct
2 Correct 103 ms 78476 KB Output is correct
3 Correct 94 ms 78524 KB Output is correct
4 Correct 85 ms 78528 KB Output is correct
5 Correct 94 ms 78492 KB Output is correct
6 Correct 86 ms 78608 KB Output is correct
7 Correct 93 ms 78476 KB Output is correct
8 Correct 99 ms 78472 KB Output is correct
9 Correct 113 ms 78480 KB Output is correct
10 Correct 123 ms 78488 KB Output is correct
11 Correct 121 ms 78532 KB Output is correct
12 Correct 84 ms 78532 KB Output is correct
13 Correct 212 ms 78552 KB Output is correct
14 Correct 195 ms 78608 KB Output is correct
15 Correct 113 ms 78532 KB Output is correct
16 Correct 110 ms 78480 KB Output is correct
17 Correct 106 ms 78532 KB Output is correct
18 Correct 88 ms 78628 KB Output is correct

Subtask #2
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 78660 KB Output is correct
2 Correct 109 ms 79544 KB Output is correct
3 Correct 234 ms 79300 KB Output is correct
4 Correct 115 ms 78536 KB Output is correct
5 Correct 172 ms 79032 KB Output is correct
6 Correct 104 ms 78496 KB Output is correct
7 Correct 100 ms 78668 KB Output is correct
8 Correct 115 ms 78532 KB Output is correct
9 Correct 194 ms 79320 KB Output is correct
10 Correct 230 ms 79296 KB Output is correct
11 Incorrect 236 ms 78920 KB Output isn't correct
12 Correct 138 ms 78496 KB Output is correct
13 Correct 91 ms 78488 KB Output is correct
14 Correct 112 ms 78532 KB Output is correct
15 Correct 195 ms 78924 KB Output is correct
16 Correct 105 ms 79540 KB Output is correct
17 Correct 210 ms 78532 KB Output is correct
18 Incorrect 194 ms 79684 KB Output isn't correct

Subtask #3
38.5714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 79432 KB Output is correct
2 Correct 242 ms 79320 KB Output is correct
3 Correct 243 ms 79696 KB Output is correct
4 Incorrect 177 ms 79556 KB Output isn't correct
5 Incorrect 129 ms 80656 KB Output isn't correct
6 Correct 228 ms 79648 KB Output is correct
7 Correct 196 ms 80144 KB Output is correct
8 Correct 209 ms 79444 KB Output is correct
9 Correct 204 ms 79464 KB Output is correct
10 Correct 170 ms 78844 KB Output is correct
11 Incorrect 144 ms 78788 KB Output isn't correct
12 Correct 188 ms 78876 KB Output is correct
13 Correct 244 ms 79860 KB Output is correct
14 Correct 149 ms 79812 KB Output is correct
15 Incorrect 191 ms 78864 KB Output isn't correct
16 Correct 220 ms 78836 KB Output is correct
17 Correct 190 ms 79172 KB Output is correct
18 Correct 237 ms 79368 KB Output is correct
19 Incorrect 98 ms 78736 KB Output isn't correct
20 Correct 244 ms 79680 KB Output is correct
21 Incorrect 168 ms 79932 KB Output isn't correct
22 Correct 248 ms 80564 KB Output is correct
23 Correct 134 ms 79784 KB Output is correct
24 Correct 126 ms 79544 KB Output is correct
25 Incorrect 178 ms 79556 KB Output isn't correct
26 Incorrect 162 ms 79492 KB Output isn't correct
27 Correct 267 ms 80204 KB Output is correct
28 Incorrect 113 ms 79644 KB Output isn't correct
29 Correct 242 ms 80688 KB Output is correct
30 Correct 221 ms 80292 KB Output is correct
31 Correct 134 ms 79412 KB Output is correct
32 Incorrect 153 ms 79500 KB Output isn't correct
33 Incorrect 108 ms 79596 KB Output isn't correct
34 Correct 184 ms 80152 KB Output is correct
35 Incorrect 119 ms 79688 KB Output isn't correct
36 Correct 248 ms 80520 KB Output is correct
37 Incorrect 129 ms 80656 KB Output isn't correct
38 Correct 218 ms 79680 KB Output is correct
39 Incorrect 123 ms 79536 KB Output isn't correct
40 Correct 185 ms 79548 KB Output is correct
41 Correct 163 ms 80136 KB Output is correct
42 Incorrect 229 ms 79676 KB Output isn't correct