oj.uz

Submission #546527

# Submission time Handle Problem Language Result Execution time Memory
546527 2022-04-07T18:12:04 Z _martynas Brunhilda’s Birthday (BOI13_brunhilda) C++11
80.3175 / 100
 294 ms 127988 KB 
#include <bits/stdc++.h>

using namespace std;

#define PB push_back
#define F first
#define S second

using pii = pair<int, int>;

const int MXN = 1e6+5;
const int MXM = 1e7+5;
const int INF = 1e8;

int m, q;
int P[MXN];
int dp[MXM];
int add[MXM];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> m >> q;

    for(int i = 0; i < m; i++) {
        cin >> P[i];
    }

    fill(dp, dp + MXM, INF);

    for(int i = 0; i < m; i++) {
        for(int p = P[i]; p < MXM; p += P[i]) {
            add[p - P[i]] = P[i];
        }
    }

    dp[0] = 0;
    queue<pii> Q;
    for(int i = 0; i < MXM; i++) {
        while(!Q.empty() && Q.front().F + Q.front().S <= i) {
            Q.pop();
        }

        if(!Q.empty()) {
            dp[i] = dp[Q.front().S]+1;
        }

        if(add[i]) {
            Q.push({add[i], i});
        }
    }

    for(int qq = 0; qq < q; qq++) {
        int n;
        cin >> n;
        if(dp[n] >= INF) {
            cout << "oo\n";
        }
        else {
            cout << dp[n] << "\n";
        }
    }

    return 0;
}
/*
2 2
2 3
5
6
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 78540 KB Output is correct
2 Correct 104 ms 78492 KB Output is correct
3 Correct 100 ms 78588 KB Output is correct
4 Correct 66 ms 78540 KB Output is correct
5 Correct 102 ms 78516 KB Output is correct
6 Correct 84 ms 78592 KB Output is correct
7 Correct 99 ms 78516 KB Output is correct
8 Correct 109 ms 78588 KB Output is correct
9 Correct 136 ms 78668 KB Output is correct
10 Correct 153 ms 78540 KB Output is correct
11 Correct 139 ms 78596 KB Output is correct
12 Correct 75 ms 78548 KB Output is correct
13 Correct 196 ms 78676 KB Output is correct
14 Correct 181 ms 78768 KB Output is correct
15 Correct 118 ms 78540 KB Output is correct
16 Correct 125 ms 78596 KB Output is correct
17 Correct 108 ms 78656 KB Output is correct
18 Correct 61 ms 78548 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 79884 KB Output is correct
2 Correct 113 ms 95648 KB Output is correct
3 Correct 234 ms 98860 KB Output is correct
4 Correct 140 ms 78944 KB Output is correct
5 Correct 176 ms 88224 KB Output is correct
6 Correct 92 ms 79012 KB Output is correct
7 Correct 81 ms 79992 KB Output is correct
8 Correct 120 ms 78600 KB Output is correct
9 Correct 199 ms 89044 KB Output is correct
10 Correct 222 ms 98908 KB Output is correct
11 Incorrect 222 ms 86232 KB Output isn't correct
12 Correct 177 ms 78944 KB Output is correct
13 Correct 82 ms 79548 KB Output is correct
14 Correct 120 ms 78876 KB Output is correct
15 Correct 186 ms 85200 KB Output is correct
16 Correct 108 ms 95648 KB Output is correct
17 Correct 182 ms 79052 KB Output is correct
18 Correct 236 ms 116112 KB Output is correct

Subtask #3
41.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 87228 KB Output is correct
2 Correct 242 ms 84928 KB Output is correct
3 Correct 277 ms 86980 KB Output is correct
4 Incorrect 187 ms 80120 KB Output isn't correct
5 Incorrect 126 ms 88488 KB Output isn't correct
6 Correct 235 ms 80656 KB Output is correct
7 Correct 191 ms 97104 KB Output is correct
8 Correct 204 ms 87152 KB Output is correct
9 Correct 202 ms 87104 KB Output is correct
10 Correct 173 ms 79384 KB Output is correct
11 Incorrect 171 ms 79436 KB Output isn't correct
12 Correct 197 ms 79620 KB Output is correct
13 Correct 233 ms 85324 KB Output is correct
14 Correct 169 ms 79904 KB Output is correct
15 Incorrect 190 ms 79492 KB Output isn't correct
16 Correct 208 ms 79464 KB Output is correct
17 Correct 194 ms 84920 KB Output is correct
18 Correct 256 ms 84924 KB Output is correct
19 Incorrect 100 ms 81280 KB Output isn't correct
20 Correct 241 ms 87036 KB Output is correct
21 Incorrect 222 ms 79952 KB Output isn't correct
22 Correct 272 ms 92036 KB Output is correct
23 Correct 173 ms 82152 KB Output is correct
24 Correct 113 ms 79716 KB Output is correct
25 Correct 184 ms 80016 KB Output is correct
26 Incorrect 178 ms 80248 KB Output isn't correct
27 Correct 257 ms 93060 KB Output is correct
28 Incorrect 108 ms 80172 KB Output isn't correct
29 Correct 244 ms 91920 KB Output is correct
30 Correct 244 ms 87052 KB Output is correct
31 Correct 141 ms 80404 KB Output is correct
32 Incorrect 158 ms 79992 KB Output isn't correct
33 Incorrect 98 ms 79632 KB Output isn't correct
34 Correct 204 ms 97020 KB Output is correct
35 Incorrect 120 ms 80244 KB Output isn't correct
36 Correct 294 ms 92376 KB Output is correct
37 Incorrect 128 ms 88584 KB Output isn't correct
38 Correct 207 ms 80588 KB Output is correct
39 Incorrect 116 ms 79816 KB Output isn't correct
40 Correct 203 ms 81184 KB Output is correct
41 Correct 180 ms 127988 KB Output is correct
42 Correct 225 ms 80196 KB Output is correct