oj.uz

Submission #251982

# Submission time Handle Problem Language Result Execution time Memory
251982 2020-07-23T12:08:18 Z abacaba Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 798 ms 158056 KB 
#include <bits/stdc++.h>
using namespace std;
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}

const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 2e7 + 15;
int m, q, mx[N], dp[N];

main() {
    memset(dp, 0x3f, sizeof(dp));
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    cin >> m >> q;
    while(m--) {
        int p;
        cin >> p;
        for(int i = p - 1; i < N; i += p)
            Max(mx[i], p - 1);
    }
    for(int i = N - 2; i; --i)
        Max(mx[i], mx[i + 1] - 1);
    dp[0] = 0;
    for(int i = 1; i < N; ++i)
        Min(dp[i], dp[i - mx[i]] + 1);
    while(q--) {
        int x;
        cin >> x;
        if(dp[x] == inf)
            cout << "oo" << endl;
        else
            cout << dp[x] << endl;
    }
    return 0;
}

Compilation message

brunhilda.cpp:17:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 156920 KB Output is correct
2 Correct 263 ms 156920 KB Output is correct
3 Correct 236 ms 156920 KB Output is correct
4 Correct 235 ms 156920 KB Output is correct
5 Correct 235 ms 157048 KB Output is correct
6 Correct 216 ms 156920 KB Output is correct
7 Correct 240 ms 156920 KB Output is correct
8 Correct 249 ms 157048 KB Output is correct
9 Correct 273 ms 156936 KB Output is correct
10 Correct 314 ms 156952 KB Output is correct
11 Correct 312 ms 156920 KB Output is correct
12 Correct 213 ms 156920 KB Output is correct
13 Correct 465 ms 156920 KB Output is correct
14 Correct 480 ms 157048 KB Output is correct
15 Correct 269 ms 157048 KB Output is correct
16 Correct 266 ms 157048 KB Output is correct
17 Correct 279 ms 157052 KB Output is correct
18 Correct 236 ms 156996 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 156920 KB Output is correct
2 Correct 277 ms 157304 KB Output is correct
3 Correct 582 ms 157176 KB Output is correct
4 Correct 285 ms 156976 KB Output is correct
5 Correct 419 ms 157176 KB Output is correct
6 Correct 255 ms 156920 KB Output is correct
7 Correct 248 ms 157048 KB Output is correct
8 Correct 278 ms 156920 KB Output is correct
9 Correct 463 ms 157304 KB Output is correct
10 Correct 560 ms 157184 KB Output is correct
11 Correct 541 ms 157288 KB Output is correct
12 Correct 341 ms 156980 KB Output is correct
13 Correct 242 ms 156920 KB Output is correct
14 Correct 281 ms 157048 KB Output is correct
15 Correct 473 ms 157292 KB Output is correct
16 Correct 275 ms 157304 KB Output is correct
17 Correct 496 ms 156920 KB Output is correct
18 Correct 487 ms 157180 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 157432 KB Output is correct
2 Correct 628 ms 157304 KB Output is correct
3 Correct 686 ms 157560 KB Output is correct
4 Correct 540 ms 157560 KB Output is correct
5 Correct 490 ms 157560 KB Output is correct
6 Correct 649 ms 157688 KB Output is correct
7 Correct 536 ms 157432 KB Output is correct
8 Correct 553 ms 157472 KB Output is correct
9 Correct 544 ms 157436 KB Output is correct
10 Correct 414 ms 157052 KB Output is correct
11 Correct 393 ms 157084 KB Output is correct
12 Correct 497 ms 157176 KB Output is correct
13 Correct 713 ms 157688 KB Output is correct
14 Correct 520 ms 157816 KB Output is correct
15 Correct 508 ms 157176 KB Output is correct
16 Correct 546 ms 157176 KB Output is correct
17 Correct 474 ms 157432 KB Output is correct
18 Correct 620 ms 157276 KB Output is correct
19 Correct 281 ms 157176 KB Output is correct
20 Correct 670 ms 157432 KB Output is correct
21 Correct 592 ms 158056 KB Output is correct
22 Correct 789 ms 157468 KB Output is correct
23 Correct 484 ms 157592 KB Output is correct
24 Correct 432 ms 157596 KB Output is correct
25 Correct 626 ms 157560 KB Output is correct
26 Correct 576 ms 157688 KB Output is correct
27 Correct 798 ms 157688 KB Output is correct
28 Correct 461 ms 157816 KB Output is correct
29 Correct 731 ms 157560 KB Output is correct
30 Correct 702 ms 157560 KB Output is correct
31 Correct 451 ms 157560 KB Output is correct
32 Correct 483 ms 157688 KB Output is correct
33 Correct 409 ms 157560 KB Output is correct
34 Correct 537 ms 157468 KB Output is correct
35 Correct 473 ms 157816 KB Output is correct
36 Correct 766 ms 157552 KB Output is correct
37 Correct 503 ms 157432 KB Output is correct
38 Correct 648 ms 157688 KB Output is correct
39 Correct 456 ms 157704 KB Output is correct
40 Correct 586 ms 157692 KB Output is correct
41 Correct 495 ms 157432 KB Output is correct
42 Correct 699 ms 157688 KB Output is correct