oj.uz

Submission #138434

# Submission time Handle Problem Language Result Execution time Memory
138434 2019-07-29T23:15:48 Z silxikys Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 804 ms 118656 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e5+5, INF = 2e9+9;
int m, Q;

int dp[10000005];
int mxmod[20000005];

vector<int> primes;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> m >> Q;
    for (int i = 0; i < m; i++) {
        int p; cin >> p;
        primes.push_back(p);
    }
    sort(primes.begin(),primes.end());
    int maxPrime = primes.back();
    for (int i = 1; i < maxPrime; i++) {
        dp[i] = 1;
    }

    for (int p: primes) {
        for (int i = p; i <= 20000000; i += p) {
            mxmod[i-1] = max(mxmod[i-1],p-1);
        }
    }

    for (int i = 20000000; i >= 1; i--) {
        mxmod[i] = max(mxmod[i],mxmod[i+1]-1);
    }

    for (int i = maxPrime; i <= 10000000; i++) {
        dp[i] = INF;
        dp[i] = min(dp[i],1+dp[i-mxmod[i]]);
    }

    /*
    for (int i = 1; i <= 500; i++) {
        cout << i << ": " << dp[i] << '\n';
    }
    */

    /*
    for (int i = 1; i <= 100; i++) {
        int mx = 0;
        for (int j: primes) {
            mx = max(mx,i%j);
        }
        cout << i << ": " << mxmod[i] << ' ' << mx << '\n';
    }
    */

    while (Q--) {
        int qi; cin >> qi;
        if (dp[qi] == INF) cout << "oo\n";
        else cout << dp[qi] << '\n';
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 117716 KB Output is correct
2 Correct 288 ms 117896 KB Output is correct
3 Correct 254 ms 117752 KB Output is correct
4 Correct 249 ms 117752 KB Output is correct
5 Correct 259 ms 117756 KB Output is correct
6 Correct 232 ms 117728 KB Output is correct
7 Correct 259 ms 117684 KB Output is correct
8 Correct 288 ms 117752 KB Output is correct
9 Correct 314 ms 117708 KB Output is correct
10 Correct 355 ms 117948 KB Output is correct
11 Correct 336 ms 117832 KB Output is correct
12 Correct 229 ms 117752 KB Output is correct
13 Correct 594 ms 117896 KB Output is correct
14 Correct 574 ms 117752 KB Output is correct
15 Correct 303 ms 117752 KB Output is correct
16 Correct 287 ms 117788 KB Output is correct
17 Correct 287 ms 117880 KB Output is correct
18 Correct 233 ms 117752 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 117880 KB Output is correct
2 Correct 277 ms 118256 KB Output is correct
3 Correct 687 ms 118256 KB Output is correct
4 Correct 321 ms 117880 KB Output is correct
5 Correct 488 ms 118076 KB Output is correct
6 Correct 286 ms 117752 KB Output is correct
7 Correct 266 ms 117880 KB Output is correct
8 Correct 316 ms 117712 KB Output is correct
9 Correct 575 ms 118260 KB Output is correct
10 Correct 717 ms 118120 KB Output is correct
11 Correct 701 ms 118012 KB Output is correct
12 Correct 409 ms 117776 KB Output is correct
13 Correct 244 ms 117752 KB Output is correct
14 Correct 341 ms 117940 KB Output is correct
15 Correct 565 ms 118008 KB Output is correct
16 Correct 280 ms 118196 KB Output is correct
17 Correct 613 ms 117752 KB Output is correct
18 Correct 569 ms 118272 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 118120 KB Output is correct
2 Correct 706 ms 118136 KB Output is correct
3 Correct 717 ms 118264 KB Output is correct
4 Correct 437 ms 118040 KB Output is correct
5 Correct 327 ms 118516 KB Output is correct
6 Correct 588 ms 118136 KB Output is correct
7 Correct 547 ms 118492 KB Output is correct
8 Correct 608 ms 118232 KB Output is correct
9 Correct 577 ms 118120 KB Output is correct
10 Correct 483 ms 117812 KB Output is correct
11 Correct 415 ms 117880 KB Output is correct
12 Correct 547 ms 118008 KB Output is correct
13 Correct 689 ms 118264 KB Output is correct
14 Correct 396 ms 118392 KB Output is correct
15 Correct 573 ms 117880 KB Output is correct
16 Correct 635 ms 117880 KB Output is correct
17 Correct 567 ms 118216 KB Output is correct
18 Correct 804 ms 118264 KB Output is correct
19 Correct 262 ms 117880 KB Output is correct
20 Correct 742 ms 118268 KB Output is correct
21 Correct 480 ms 118392 KB Output is correct
22 Correct 705 ms 118644 KB Output is correct
23 Correct 340 ms 118264 KB Output is correct
24 Correct 283 ms 118008 KB Output is correct
25 Correct 560 ms 118264 KB Output is correct
26 Correct 460 ms 118136 KB Output is correct
27 Correct 764 ms 118516 KB Output is correct
28 Correct 289 ms 118136 KB Output is correct
29 Correct 804 ms 118656 KB Output is correct
30 Correct 642 ms 118532 KB Output is correct
31 Correct 356 ms 118036 KB Output is correct
32 Correct 374 ms 118136 KB Output is correct
33 Correct 255 ms 118168 KB Output is correct
34 Correct 506 ms 118512 KB Output is correct
35 Correct 305 ms 118136 KB Output is correct
36 Correct 683 ms 118388 KB Output is correct
37 Correct 352 ms 118516 KB Output is correct
38 Correct 597 ms 118264 KB Output is correct
39 Correct 307 ms 118136 KB Output is correct
40 Correct 533 ms 118136 KB Output is correct
41 Correct 483 ms 118388 KB Output is correct
42 Correct 664 ms 118240 KB Output is correct