oj.uz

Submission #1069168

# Submission time Handle Problem Language Result Execution time Memory
1069168 2024-08-21T16:45:37 Z ortsac Brunhilda’s Birthday (BOI13_brunhilda) C++17
58.8889 / 100
 1000 ms 80588 KB 
#pragma GCC optimization("Ofast,unroll-loops")
#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() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    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";
    }
}

Compilation message

brunhilda.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization("Ofast,unroll-loops")
      |

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 78676 KB Output is correct
2 Correct 320 ms 78672 KB Output is correct
3 Correct 194 ms 78676 KB Output is correct
4 Correct 63 ms 78676 KB Output is correct
5 Correct 112 ms 78512 KB Output is correct
6 Correct 51 ms 78684 KB Output is correct
7 Correct 196 ms 78616 KB Output is correct
8 Correct 226 ms 78676 KB Output is correct
9 Correct 393 ms 78676 KB Output is correct
10 Correct 551 ms 78672 KB Output is correct
11 Correct 405 ms 78932 KB Output is correct
12 Correct 49 ms 78672 KB Output is correct
13 Execution timed out 1079 ms 61268 KB Time limit exceeded
14 Execution timed out 1057 ms 58796 KB Time limit exceeded
15 Correct 362 ms 78480 KB Output is correct
16 Correct 319 ms 78676 KB Output is correct
17 Correct 150 ms 78676 KB Output is correct
18 Correct 63 ms 78672 KB Output is correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 78804 KB Output is correct
2 Correct 137 ms 80076 KB Output is correct
3 Execution timed out 1059 ms 46788 KB Time limit exceeded
4 Correct 354 ms 78676 KB Output is correct
5 Execution timed out 1053 ms 79576 KB Time limit exceeded
6 Correct 365 ms 78672 KB Output is correct
7 Correct 164 ms 78808 KB Output is correct
8 Correct 297 ms 78492 KB Output is correct
9 Execution timed out 1045 ms 63396 KB Time limit exceeded
10 Execution timed out 1048 ms 47228 KB Time limit exceeded
11 Execution timed out 1045 ms 44236 KB Time limit exceeded
12 Correct 757 ms 78676 KB Output is correct
13 Correct 170 ms 78596 KB Output is correct
14 Correct 363 ms 78676 KB Output is correct
15 Execution timed out 1062 ms 54744 KB Time limit exceeded
16 Correct 147 ms 80148 KB Output is correct
17 Execution timed out 1071 ms 56076 KB Time limit exceeded
18 Execution timed out 1039 ms 79880 KB Time limit exceeded

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 56776 KB Time limit exceeded
2 Execution timed out 1040 ms 44492 KB Time limit exceeded
3 Execution timed out 1032 ms 44624 KB Time limit exceeded
4 Correct 805 ms 78876 KB Output is correct
5 Correct 240 ms 80588 KB Output is correct
6 Execution timed out 1067 ms 61296 KB Time limit exceeded
7 Correct 861 ms 80460 KB Output is correct
8 Execution timed out 1034 ms 58980 KB Time limit exceeded
9 Execution timed out 1051 ms 58828 KB Time limit exceeded
10 Correct 877 ms 78932 KB Output is correct
11 Correct 631 ms 78928 KB Output is correct
12 Execution timed out 1041 ms 64336 KB Time limit exceeded
13 Execution timed out 1077 ms 52524 KB Time limit exceeded
14 Correct 662 ms 79188 KB Output is correct
15 Execution timed out 1006 ms 56200 KB Time limit exceeded
16 Execution timed out 1055 ms 52052 KB Time limit exceeded
17 Execution timed out 1057 ms 67800 KB Time limit exceeded
18 Execution timed out 1069 ms 44660 KB Time limit exceeded
19 Correct 257 ms 78928 KB Output is correct
20 Execution timed out 1048 ms 42444 KB Time limit exceeded
21 Correct 893 ms 79256 KB Output is correct
22 Execution timed out 1055 ms 49464 KB Time limit exceeded
23 Correct 317 ms 79312 KB Output is correct
24 Correct 163 ms 79048 KB Output is correct
25 Correct 898 ms 78928 KB Output is correct
26 Correct 815 ms 78928 KB Output is correct
27 Execution timed out 1075 ms 45392 KB Time limit exceeded
28 Correct 221 ms 79184 KB Output is correct
29 Execution timed out 1068 ms 63260 KB Time limit exceeded
30 Execution timed out 1046 ms 68036 KB Time limit exceeded
31 Correct 295 ms 78932 KB Output is correct
32 Correct 422 ms 78932 KB Output is correct
33 Correct 101 ms 78800 KB Output is correct
34 Correct 844 ms 80332 KB Output is correct
35 Correct 281 ms 78928 KB Output is correct
36 Execution timed out 1082 ms 53460 KB Time limit exceeded
37 Correct 238 ms 80580 KB Output is correct
38 Execution timed out 1072 ms 63824 KB Time limit exceeded
39 Correct 222 ms 78928 KB Output is correct
40 Execution timed out 1022 ms 77004 KB Time limit exceeded
41 Correct 774 ms 80328 KB Output is correct
42 Execution timed out 1072 ms 53988 KB Time limit exceeded