oj.uz

Submission #1069163

# Submission time Handle Problem Language Result Execution time Memory
1069163 2024-08-21T16:40:49 Z ortsac Brunhilda’s Birthday (BOI13_brunhilda) C++17
56.0317 / 100
 1000 ms 80680 KB 
#include <bits/stdc++.h>
 
using namespace std;

#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second

int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 1e7;
int dp[MAXN + 10];
priority_queue<pii> pq;

int32_t main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        pq.push({0, a});
    }
    for (int i = 1; i <= MAXN; i++) {
        dp[i] = inf;
        while ((pq.top().se - pq.top().fr) <= i) {
            auto u = pq.top();
            pq.pop();
            pq.push({u.fr - u.se, u.se});
        }
        dp[i] = min(dp[i], dp[-pq.top().fr] + 1);
    }
    while (q--) {
        int x;
        cin >> x;
        if (dp[x] == inf) cout << "oo\n";
        else cout << dp[x] << "\n";
    }
}

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 78508 KB Output is correct
2 Correct 370 ms 78676 KB Output is correct
3 Correct 203 ms 78452 KB Output is correct
4 Correct 88 ms 78676 KB Output is correct
5 Correct 123 ms 78472 KB Output is correct
6 Correct 60 ms 78500 KB Output is correct
7 Correct 204 ms 78676 KB Output is correct
8 Correct 244 ms 78460 KB Output is correct
9 Correct 401 ms 78692 KB Output is correct
10 Correct 549 ms 78672 KB Output is correct
11 Correct 401 ms 78676 KB Output is correct
12 Correct 58 ms 78676 KB Output is correct
13 Execution timed out 1069 ms 58008 KB Time limit exceeded
14 Execution timed out 1018 ms 53876 KB Time limit exceeded
15 Correct 385 ms 78672 KB Output is correct
16 Correct 343 ms 78448 KB Output is correct
17 Correct 166 ms 78676 KB Output is correct
18 Correct 76 ms 78676 KB Output is correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 78896 KB Output is correct
2 Correct 168 ms 80060 KB Output is correct
3 Execution timed out 1054 ms 46932 KB Time limit exceeded
4 Correct 369 ms 78816 KB Output is correct
5 Execution timed out 1068 ms 77512 KB Time limit exceeded
6 Correct 351 ms 78496 KB Output is correct
7 Correct 178 ms 78788 KB Output is correct
8 Correct 289 ms 78676 KB Output is correct
9 Execution timed out 1086 ms 63824 KB Time limit exceeded
10 Execution timed out 1039 ms 42684 KB Time limit exceeded
11 Execution timed out 1018 ms 44480 KB Time limit exceeded
12 Correct 744 ms 78788 KB Output is correct
13 Correct 158 ms 78556 KB Output is correct
14 Correct 372 ms 78560 KB Output is correct
15 Execution timed out 1038 ms 52640 KB Time limit exceeded
16 Correct 161 ms 80064 KB Output is correct
17 Execution timed out 1073 ms 54100 KB Time limit exceeded
18 Execution timed out 1041 ms 79708 KB Time limit exceeded

Subtask #3
27.1428571429 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1045 ms 56872 KB Time limit exceeded
2 Execution timed out 1004 ms 40528 KB Time limit exceeded
3 Execution timed out 1077 ms 42528 KB Time limit exceeded
4 Correct 931 ms 79444 KB Output is correct
5 Correct 384 ms 80508 KB Output is correct
6 Execution timed out 1032 ms 61012 KB Time limit exceeded
7 Correct 970 ms 80652 KB Output is correct
8 Execution timed out 1049 ms 56336 KB Time limit exceeded
9 Execution timed out 1062 ms 56828 KB Time limit exceeded
10 Correct 886 ms 78752 KB Output is correct
11 Correct 675 ms 78896 KB Output is correct
12 Execution timed out 1056 ms 65868 KB Time limit exceeded
13 Execution timed out 1042 ms 52440 KB Time limit exceeded
14 Correct 744 ms 79904 KB Output is correct
15 Execution timed out 1037 ms 57496 KB Time limit exceeded
16 Execution timed out 1030 ms 50020 KB Time limit exceeded
17 Execution timed out 1075 ms 69060 KB Time limit exceeded
18 Execution timed out 1024 ms 42528 KB Time limit exceeded
19 Correct 285 ms 78928 KB Output is correct
20 Execution timed out 1083 ms 48652 KB Time limit exceeded
21 Execution timed out 1027 ms 79956 KB Time limit exceeded
22 Execution timed out 1025 ms 49340 KB Time limit exceeded
23 Correct 438 ms 79300 KB Output is correct
24 Correct 277 ms 78932 KB Output is correct
25 Execution timed out 1018 ms 79564 KB Time limit exceeded
26 Correct 894 ms 79440 KB Output is correct
27 Execution timed out 1062 ms 43200 KB Time limit exceeded
28 Correct 343 ms 78988 KB Output is correct
29 Execution timed out 1035 ms 60604 KB Time limit exceeded
30 Execution timed out 1037 ms 66124 KB Time limit exceeded
31 Correct 408 ms 78912 KB Output is correct
32 Correct 551 ms 78928 KB Output is correct
33 Correct 231 ms 78760 KB Output is correct
34 Correct 927 ms 80536 KB Output is correct
35 Correct 434 ms 79012 KB Output is correct
36 Execution timed out 1022 ms 49340 KB Time limit exceeded
37 Correct 402 ms 80320 KB Output is correct
38 Execution timed out 1049 ms 62320 KB Time limit exceeded
39 Correct 369 ms 79076 KB Output is correct
40 Execution timed out 1029 ms 73600 KB Time limit exceeded
41 Correct 875 ms 80680 KB Output is correct
42 Execution timed out 1082 ms 54000 KB Time limit exceeded