답안 #242158

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242158	2020-06-27T03:15:52 Z	thecodingwizard	Brunhilda’s Birthday (BOI13_brunhilda)	C++11	31.1111 / 100	1000 ms	44668 KB

brunhilda

#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define f first
#define s second

int A[100000]; 
int dp[10000001]; 
set<ii> transitions;

int main() {
    int m, q; cin >> m >> q;
    for (int i = 0; i < m; i++) cin >> A[i];
    for (int i = 0; i < 10000001; i++) dp[i] = -1;
    dp[0] = 0;

    int nxtStart = 0, nxtVal = 0;
    for (int i = 0; i < m; i++) {
        nxtVal = max(nxtVal, A[i]);

        transitions.insert({A[i],A[i]});
    }

    while (nxtStart != -1) {
        int begin = nxtStart, end = begin + nxtVal;
        nxtStart = -1;
        nxtVal = 0;

        end = min(end, 10000001);

        while (!transitions.empty() && transitions.begin()->f < end) {
            int x = transitions.begin()->s, i = transitions.begin()->f;
            transitions.erase(transitions.begin());
            if (nxtStart+nxtVal < i + x) {
                nxtStart = i;
                nxtVal = x;
            }
            if (i+x<10000001) transitions.insert({i+x,x});
        }

        for (int i = begin + 1; i < end; i++) {
            if (dp[i] == -1) dp[i] = dp[begin]+1;
        }
    }

    for (int i = 0; i < q; i++) {
        int x; cin >> x;
        if (dp[x] == -1) cout << "oo" << "\n";
        else cout << dp[x] << "\n";
    }

    return 0;
}

Subtask #1

11.1111111111 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	39424 KB	Output is correct
2	Execution timed out	1012 ms	39544 KB	Time limit exceeded
3	Correct	40 ms	39424 KB	Output is correct
4	Correct	176 ms	39424 KB	Output is correct
5	Correct	353 ms	39544 KB	Output is correct
6	Correct	27 ms	39424 KB	Output is correct
7	Correct	41 ms	39424 KB	Output is correct
8	Correct	114 ms	39424 KB	Output is correct
9	Execution timed out	1085 ms	39424 KB	Time limit exceeded
10	Execution timed out	1092 ms	39416 KB	Time limit exceeded
11	Execution timed out	1094 ms	39424 KB	Time limit exceeded
12	Correct	111 ms	39424 KB	Output is correct
13	Execution timed out	1093 ms	39552 KB	Time limit exceeded
14	Execution timed out	1084 ms	39552 KB	Time limit exceeded
15	Execution timed out	1097 ms	39424 KB	Time limit exceeded
16	Execution timed out	1010 ms	39500 KB	Time limit exceeded
17	Correct	480 ms	39672 KB	Output is correct
18	Correct	173 ms	39424 KB	Output is correct

Subtask #2

10.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	407 ms	40056 KB	Output is correct
2	Correct	613 ms	44280 KB	Output is correct
3	Execution timed out	1090 ms	43000 KB	Time limit exceeded
4	Correct	876 ms	39672 KB	Output is correct
5	Execution timed out	1096 ms	42104 KB	Time limit exceeded
6	Correct	796 ms	39672 KB	Output is correct
7	Correct	405 ms	40064 KB	Output is correct
8	Correct	762 ms	39552 KB	Output is correct
9	Execution timed out	1096 ms	43000 KB	Time limit exceeded
10	Execution timed out	1093 ms	43000 KB	Time limit exceeded
11	Execution timed out	1089 ms	41464 KB	Time limit exceeded
12	Execution timed out	1097 ms	39552 KB	Time limit exceeded
13	Correct	360 ms	39552 KB	Output is correct
14	Correct	886 ms	39672 KB	Output is correct
15	Execution timed out	1097 ms	41592 KB	Time limit exceeded
16	Correct	626 ms	44280 KB	Output is correct
17	Execution timed out	1099 ms	39552 KB	Time limit exceeded
18	Execution timed out	1092 ms	44536 KB	Time limit exceeded

Subtask #3

10.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1098 ms	41976 KB	Time limit exceeded
2	Execution timed out	1101 ms	42104 KB	Time limit exceeded
3	Execution timed out	1100 ms	41976 KB	Time limit exceeded
4	Execution timed out	1087 ms	39672 KB	Time limit exceeded
5	Execution timed out	1022 ms	44668 KB	Time limit exceeded
6	Execution timed out	1091 ms	39808 KB	Time limit exceeded
7	Execution timed out	1095 ms	44536 KB	Time limit exceeded
8	Execution timed out	1100 ms	41976 KB	Time limit exceeded
9	Execution timed out	1101 ms	41976 KB	Time limit exceeded
10	Execution timed out	1102 ms	39680 KB	Time limit exceeded
11	Execution timed out	1094 ms	39680 KB	Time limit exceeded
12	Execution timed out	1099 ms	39808 KB	Time limit exceeded
13	Execution timed out	1093 ms	40956 KB	Time limit exceeded
14	Execution timed out	1089 ms	39424 KB	Time limit exceeded
15	Execution timed out	1090 ms	39672 KB	Time limit exceeded
16	Execution timed out	1098 ms	39808 KB	Time limit exceeded
17	Execution timed out	1098 ms	41720 KB	Time limit exceeded
18	Execution timed out	1092 ms	42104 KB	Time limit exceeded
19	Correct	600 ms	39928 KB	Output is correct
20	Execution timed out	1100 ms	41976 KB	Time limit exceeded
21	Execution timed out	1093 ms	39552 KB	Time limit exceeded
22	Execution timed out	1087 ms	44664 KB	Time limit exceeded
23	Execution timed out	1028 ms	41184 KB	Time limit exceeded
24	Correct	588 ms	39932 KB	Output is correct
25	Execution timed out	1094 ms	39552 KB	Time limit exceeded
26	Execution timed out	1094 ms	39680 KB	Time limit exceeded
27	Execution timed out	1097 ms	44536 KB	Time limit exceeded
28	Correct	806 ms	39976 KB	Output is correct
29	Execution timed out	1092 ms	44664 KB	Time limit exceeded
30	Execution timed out	1095 ms	43000 KB	Time limit exceeded
31	Correct	980 ms	40056 KB	Output is correct
32	Execution timed out	1096 ms	39928 KB	Time limit exceeded
33	Correct	431 ms	39820 KB	Output is correct
34	Execution timed out	1091 ms	44536 KB	Time limit exceeded
35	Correct	910 ms	40004 KB	Output is correct
36	Execution timed out	1089 ms	44024 KB	Time limit exceeded
37	Execution timed out	1012 ms	44664 KB	Time limit exceeded
38	Execution timed out	1092 ms	39808 KB	Time limit exceeded
39	Correct	741 ms	39932 KB	Output is correct
40	Execution timed out	1096 ms	39936 KB	Time limit exceeded
41	Execution timed out	1101 ms	44536 KB	Time limit exceeded
42	Execution timed out	1094 ms	39552 KB	Time limit exceeded