답안 #1069168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1069168	2024-08-21T16:45:37 Z	ortsac	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	58.8889 / 100	1000 ms	80588 KB

brunhilda

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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