oj.uz

Submission #242158

# Submission time Handle Problem Language Result Execution time Memory
242158 2020-06-27T03:15:52 Z thecodingwizard Brunhilda’s Birthday (BOI13_brunhilda) C++11
31.1111 / 100
 1000 ms 44668 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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