oj.uz

Submission #242157

# Submission time Handle Problem Language Result Execution time Memory
242157 2020-06-27T03:11:36 Z thecodingwizard Brunhilda’s Birthday (BOI13_brunhilda) C++11
11.1111 / 100
 1000 ms 11128 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 < 1000001; 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);
        for (int i = begin + 1; i < end; i++) {
            while (!transitions.empty() && transitions.begin()->f <= i) {
                int x = transitions.begin()->s;
                transitions.erase(transitions.begin());
                if (nxtStart+nxtVal < i + x) {
                    nxtStart = i;
                    nxtVal = x;
                }
                if (i+x<10000001) transitions.insert({i+x,x});
            }
            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 9 ms 4224 KB Output is correct
2 Execution timed out 1066 ms 4344 KB Time limit exceeded
3 Correct 24 ms 4224 KB Output is correct
4 Correct 177 ms 4344 KB Output is correct
5 Correct 401 ms 4344 KB Output is correct
6 Correct 9 ms 4224 KB Output is correct
7 Correct 24 ms 4224 KB Output is correct
8 Correct 101 ms 4224 KB Output is correct
9 Execution timed out 1094 ms 4344 KB Time limit exceeded
10 Execution timed out 1092 ms 4472 KB Time limit exceeded
11 Execution timed out 1091 ms 4444 KB Time limit exceeded
12 Correct 115 ms 4344 KB Output is correct
13 Execution timed out 1099 ms 4480 KB Time limit exceeded
14 Execution timed out 1093 ms 4472 KB Time limit exceeded
15 Execution timed out 1088 ms 4436 KB Time limit exceeded
16 Execution timed out 1062 ms 4600 KB Time limit exceeded
17 Correct 522 ms 4344 KB Output is correct
18 Correct 180 ms 4344 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 440 ms 4996 KB Output isn't correct
2 Incorrect 679 ms 9724 KB Output isn't correct
3 Execution timed out 1099 ms 8312 KB Time limit exceeded
4 Incorrect 944 ms 4600 KB Output isn't correct
5 Execution timed out 1099 ms 7160 KB Time limit exceeded
6 Incorrect 841 ms 4352 KB Output isn't correct
7 Incorrect 438 ms 5000 KB Output isn't correct
8 Incorrect 816 ms 4352 KB Output isn't correct
9 Execution timed out 1093 ms 8568 KB Time limit exceeded
10 Execution timed out 1095 ms 8440 KB Time limit exceeded
11 Execution timed out 1097 ms 6520 KB Time limit exceeded
12 Execution timed out 1082 ms 4748 KB Time limit exceeded
13 Incorrect 392 ms 4600 KB Output isn't correct
14 Incorrect 949 ms 4476 KB Output isn't correct
15 Execution timed out 1092 ms 6704 KB Time limit exceeded
16 Incorrect 687 ms 9592 KB Output isn't correct
17 Execution timed out 1089 ms 4352 KB Time limit exceeded
18 Execution timed out 1100 ms 9976 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 7544 KB Time limit exceeded
2 Execution timed out 1099 ms 7416 KB Time limit exceeded
3 Execution timed out 1099 ms 7296 KB Time limit exceeded
4 Execution timed out 1100 ms 4472 KB Time limit exceeded
5 Execution timed out 1046 ms 11128 KB Time limit exceeded
6 Execution timed out 1099 ms 4728 KB Time limit exceeded
7 Execution timed out 1099 ms 10232 KB Time limit exceeded
8 Execution timed out 1092 ms 7416 KB Time limit exceeded
9 Execution timed out 1095 ms 7488 KB Time limit exceeded
10 Execution timed out 1096 ms 4728 KB Time limit exceeded
11 Execution timed out 1089 ms 4896 KB Time limit exceeded
12 Execution timed out 1092 ms 4856 KB Time limit exceeded
13 Execution timed out 1094 ms 6312 KB Time limit exceeded
14 Execution timed out 1096 ms 4472 KB Time limit exceeded
15 Execution timed out 1099 ms 4480 KB Time limit exceeded
16 Execution timed out 1096 ms 4728 KB Time limit exceeded
17 Execution timed out 1090 ms 7032 KB Time limit exceeded
18 Execution timed out 1093 ms 7544 KB Time limit exceeded
19 Incorrect 631 ms 4856 KB Output isn't correct
20 Execution timed out 1089 ms 7520 KB Time limit exceeded
21 Execution timed out 1092 ms 4344 KB Time limit exceeded
22 Execution timed out 1092 ms 10360 KB Time limit exceeded
23 Execution timed out 1099 ms 6648 KB Time limit exceeded
24 Incorrect 607 ms 5496 KB Output isn't correct
25 Execution timed out 1095 ms 4600 KB Time limit exceeded
26 Execution timed out 1089 ms 4472 KB Time limit exceeded
27 Execution timed out 1088 ms 10252 KB Time limit exceeded
28 Incorrect 846 ms 5496 KB Output isn't correct
29 Execution timed out 1090 ms 10488 KB Time limit exceeded
30 Execution timed out 1096 ms 8440 KB Time limit exceeded
31 Execution timed out 1034 ms 5496 KB Time limit exceeded
32 Execution timed out 1052 ms 4464 KB Time limit exceeded
33 Incorrect 429 ms 5368 KB Output isn't correct
34 Execution timed out 1096 ms 10488 KB Time limit exceeded
35 Incorrect 962 ms 5496 KB Output isn't correct
36 Execution timed out 1095 ms 9828 KB Time limit exceeded
37 Execution timed out 1062 ms 11000 KB Time limit exceeded
38 Execution timed out 1093 ms 4728 KB Time limit exceeded
39 Incorrect 762 ms 5368 KB Output isn't correct
40 Execution timed out 1090 ms 4984 KB Time limit exceeded
41 Execution timed out 1099 ms 10232 KB Time limit exceeded
42 Execution timed out 1093 ms 4476 KB Time limit exceeded