oj.uz

Submission #546534

# Submission time Handle Problem Language Result Execution time Memory
546534 2022-04-07T18:22:08 Z _martynas Brunhilda’s Birthday (BOI13_brunhilda) C++11
80.3175 / 100
 257 ms 127040 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 = 1e5+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] = min(INF, 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 80 ms 78540 KB Output is correct
2 Correct 98 ms 78596 KB Output is correct
3 Correct 100 ms 78584 KB Output is correct
4 Correct 64 ms 78612 KB Output is correct
5 Correct 98 ms 78528 KB Output is correct
6 Correct 80 ms 78588 KB Output is correct
7 Correct 99 ms 78580 KB Output is correct
8 Correct 109 ms 78588 KB Output is correct
9 Correct 127 ms 78540 KB Output is correct
10 Correct 132 ms 78720 KB Output is correct
11 Correct 131 ms 78548 KB Output is correct
12 Correct 59 ms 78508 KB Output is correct
13 Correct 179 ms 78596 KB Output is correct
14 Correct 212 ms 78640 KB Output is correct
15 Correct 113 ms 78588 KB Output is correct
16 Correct 99 ms 78540 KB Output is correct
17 Correct 98 ms 78652 KB Output is correct
18 Correct 63 ms 78640 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 79984 KB Output is correct
2 Correct 102 ms 95308 KB Output is correct
3 Correct 222 ms 98504 KB Output is correct
4 Correct 124 ms 78984 KB Output is correct
5 Correct 169 ms 87976 KB Output is correct
6 Correct 93 ms 79008 KB Output is correct
7 Correct 83 ms 79948 KB Output is correct
8 Correct 118 ms 78696 KB Output is correct
9 Correct 192 ms 88924 KB Output is correct
10 Correct 225 ms 98568 KB Output is correct
11 Incorrect 218 ms 86244 KB Output isn't correct
12 Correct 141 ms 78928 KB Output is correct
13 Correct 81 ms 79628 KB Output is correct
14 Correct 118 ms 78984 KB Output is correct
15 Correct 184 ms 85256 KB Output is correct
16 Correct 104 ms 95192 KB Output is correct
17 Correct 180 ms 79020 KB Output is correct
18 Correct 192 ms 115608 KB Output is correct

Subtask #3
41.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 86904 KB Output is correct
2 Correct 227 ms 84664 KB Output is correct
3 Correct 223 ms 86768 KB Output is correct
4 Incorrect 167 ms 79624 KB Output isn't correct
5 Incorrect 127 ms 87644 KB Output isn't correct
6 Correct 198 ms 80040 KB Output is correct
7 Correct 198 ms 96344 KB Output is correct
8 Correct 197 ms 87000 KB Output is correct
9 Correct 195 ms 86852 KB Output is correct
10 Correct 173 ms 79360 KB Output is correct
11 Incorrect 154 ms 79372 KB Output isn't correct
12 Correct 176 ms 79620 KB Output is correct
13 Correct 220 ms 84944 KB Output is correct
14 Correct 162 ms 79392 KB Output is correct
15 Incorrect 184 ms 79496 KB Output isn't correct
16 Correct 201 ms 79488 KB Output is correct
17 Correct 198 ms 84792 KB Output is correct
18 Correct 221 ms 84668 KB Output is correct
19 Incorrect 91 ms 81204 KB Output isn't correct
20 Correct 229 ms 86804 KB Output is correct
21 Incorrect 167 ms 79352 KB Output isn't correct
22 Correct 248 ms 91372 KB Output is correct
23 Correct 134 ms 81508 KB Output is correct
24 Correct 106 ms 79268 KB Output is correct
25 Correct 180 ms 79436 KB Output is correct
26 Incorrect 166 ms 79692 KB Output isn't correct
27 Correct 243 ms 92528 KB Output is correct
28 Incorrect 111 ms 79624 KB Output isn't correct
29 Correct 229 ms 90836 KB Output is correct
30 Correct 218 ms 86576 KB Output is correct
31 Correct 137 ms 79976 KB Output is correct
32 Incorrect 153 ms 79504 KB Output isn't correct
33 Incorrect 90 ms 79228 KB Output isn't correct
34 Correct 191 ms 96376 KB Output is correct
35 Incorrect 118 ms 79584 KB Output isn't correct
36 Correct 257 ms 91188 KB Output is correct
37 Incorrect 128 ms 87736 KB Output isn't correct
38 Correct 210 ms 80116 KB Output is correct
39 Incorrect 117 ms 79232 KB Output isn't correct
40 Correct 183 ms 80572 KB Output is correct
41 Correct 180 ms 127040 KB Output is correct
42 Correct 207 ms 79628 KB Output is correct