oj.uz

Submission #375049

# Submission time Handle Problem Language Result Execution time Memory
375049 2021-03-09T01:13:08 Z ijxjdjd Solar Storm (NOI20_solarstorm) C++14
100 / 100
 1386 ms 189228 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const ll INF = (ll)(1e18);
const int MAXN = (int)(1e6) + 5;
const int MAXK = 22;
set<pair<ll, int>> st;
int bk[MAXN][MAXK];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, S;
    ll K;
    cin >> N >> S >> K;
    vector<ll> loc;
    vector<ll> cost;
    cost.resize(N+1);
    loc.resize(N+1);
    loc[0] = -INF;
    cost[0] = 0;
    loc[1] = 1;
    for (int i = 2; i < N+1; i++) {
        cin >> loc[i];
        loc[i] += max(0LL, loc[i-1]);
    }
    for (int i = 1; i <= N; i++) {
        cin >> cost[i];
        cost[i] += cost[i-1];
    }
    for (int i = 0; i <= N; i++) {
        st.insert({loc[i], i});
    }
    ll res = 0;
    int resI = -1;
    for (int j = 1; j <= N; j++) {
        pair<ll, int> ini = *st.lower_bound({loc[j]-K, -1});
        ini = *(prev(st.lower_bound({ini.first-K, -1})));
        bk[j][0] = ini.second;
        for (int k = 1; k < MAXK; k++) {
            bk[j][k] = bk[bk[j][k-1]][k-1];
        }
        int cur = j;
        for (int k = 0; k < MAXK; k++) {
            if (S&(1<<k)) {
                cur = bk[cur][k];
            }
        }
        if (cost[j] - cost[cur] > res) {
            resI = j;
            res = cost[j] - cost[cur];
        }
    }
    vector<int> ans;
    FR(iter, S) {
        pair<ll, int> ini = *st.lower_bound({loc[resI]-K, -1});
        if (ini.second != 0) {
            ans.push_back(ini.second);
        }
        else {
            break;
        }
        resI = (*(prev(st.lower_bound({ini.first-K, -1})))).second;
    }
    cout << ans.size() << '\n';
    for (int j : ans) {
        cout << j << " ";
    }
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 1900 KB Output is correct
3 Correct 8 ms 2176 KB Output is correct
4 Correct 4 ms 1132 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 7 ms 1776 KB Output is correct
7 Correct 6 ms 1900 KB Output is correct
8 Correct 7 ms 2156 KB Output is correct
9 Correct 5 ms 1516 KB Output is correct
10 Correct 8 ms 2028 KB Output is correct
11 Correct 8 ms 2156 KB Output is correct
12 Correct 4 ms 1004 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 148868 KB Output is correct
2 Correct 475 ms 94700 KB Output is correct
3 Correct 537 ms 101484 KB Output is correct
4 Correct 604 ms 110700 KB Output is correct
5 Correct 729 ms 129644 KB Output is correct
6 Correct 961 ms 173024 KB Output is correct
7 Correct 663 ms 114284 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 1900 KB Output is correct
3 Correct 8 ms 2176 KB Output is correct
4 Correct 4 ms 1132 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 7 ms 1776 KB Output is correct
7 Correct 6 ms 1900 KB Output is correct
8 Correct 7 ms 2156 KB Output is correct
9 Correct 5 ms 1516 KB Output is correct
10 Correct 8 ms 2028 KB Output is correct
11 Correct 8 ms 2156 KB Output is correct
12 Correct 4 ms 1004 KB Output is correct
13 Correct 726 ms 148868 KB Output is correct
14 Correct 475 ms 94700 KB Output is correct
15 Correct 537 ms 101484 KB Output is correct
16 Correct 604 ms 110700 KB Output is correct
17 Correct 729 ms 129644 KB Output is correct
18 Correct 961 ms 173024 KB Output is correct
19 Correct 663 ms 114284 KB Output is correct
20 Correct 462 ms 97096 KB Output is correct
21 Correct 663 ms 119020 KB Output is correct
22 Correct 818 ms 141328 KB Output is correct
23 Correct 679 ms 143252 KB Output is correct
24 Correct 646 ms 131620 KB Output is correct
25 Correct 709 ms 131564 KB Output is correct
26 Correct 486 ms 97900 KB Output is correct
27 Correct 692 ms 125804 KB Output is correct
28 Correct 717 ms 124524 KB Output is correct
29 Correct 887 ms 161772 KB Output is correct
30 Correct 776 ms 132588 KB Output is correct
31 Correct 659 ms 116180 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1018 ms 145152 KB Output is correct
2 Correct 489 ms 88044 KB Output is correct
3 Correct 510 ms 94512 KB Output is correct
4 Correct 750 ms 136684 KB Output is correct
5 Correct 746 ms 132604 KB Output is correct
6 Correct 768 ms 140396 KB Output is correct
7 Correct 1174 ms 179244 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 1900 KB Output is correct
3 Correct 8 ms 2176 KB Output is correct
4 Correct 4 ms 1132 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 7 ms 1776 KB Output is correct
7 Correct 6 ms 1900 KB Output is correct
8 Correct 7 ms 2156 KB Output is correct
9 Correct 5 ms 1516 KB Output is correct
10 Correct 8 ms 2028 KB Output is correct
11 Correct 8 ms 2156 KB Output is correct
12 Correct 4 ms 1004 KB Output is correct
13 Correct 7 ms 2284 KB Output is correct
14 Correct 7 ms 1772 KB Output is correct
15 Correct 7 ms 1772 KB Output is correct
16 Correct 5 ms 1260 KB Output is correct
17 Correct 7 ms 1644 KB Output is correct
18 Correct 8 ms 2028 KB Output is correct
19 Correct 7 ms 1772 KB Output is correct
20 Correct 6 ms 1472 KB Output is correct
21 Correct 11 ms 2284 KB Output is correct
22 Correct 9 ms 2156 KB Output is correct
23 Correct 12 ms 2080 KB Output is correct
24 Correct 8 ms 1900 KB Output is correct
25 Correct 8 ms 1900 KB Output is correct
26 Correct 8 ms 1900 KB Output is correct
27 Correct 6 ms 1644 KB Output is correct
28 Correct 6 ms 1644 KB Output is correct
29 Correct 7 ms 1644 KB Output is correct
30 Correct 7 ms 2028 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 1900 KB Output is correct
3 Correct 8 ms 2176 KB Output is correct
4 Correct 4 ms 1132 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 7 ms 1776 KB Output is correct
7 Correct 6 ms 1900 KB Output is correct
8 Correct 7 ms 2156 KB Output is correct
9 Correct 5 ms 1516 KB Output is correct
10 Correct 8 ms 2028 KB Output is correct
11 Correct 8 ms 2156 KB Output is correct
12 Correct 4 ms 1004 KB Output is correct
13 Correct 726 ms 148868 KB Output is correct
14 Correct 475 ms 94700 KB Output is correct
15 Correct 537 ms 101484 KB Output is correct
16 Correct 604 ms 110700 KB Output is correct
17 Correct 729 ms 129644 KB Output is correct
18 Correct 961 ms 173024 KB Output is correct
19 Correct 663 ms 114284 KB Output is correct
20 Correct 462 ms 97096 KB Output is correct
21 Correct 663 ms 119020 KB Output is correct
22 Correct 818 ms 141328 KB Output is correct
23 Correct 679 ms 143252 KB Output is correct
24 Correct 646 ms 131620 KB Output is correct
25 Correct 709 ms 131564 KB Output is correct
26 Correct 486 ms 97900 KB Output is correct
27 Correct 692 ms 125804 KB Output is correct
28 Correct 717 ms 124524 KB Output is correct
29 Correct 887 ms 161772 KB Output is correct
30 Correct 776 ms 132588 KB Output is correct
31 Correct 659 ms 116180 KB Output is correct
32 Correct 741 ms 155240 KB Output is correct
33 Correct 627 ms 118956 KB Output is correct
34 Correct 1002 ms 163712 KB Output is correct
35 Correct 568 ms 98436 KB Output is correct
36 Correct 569 ms 105452 KB Output is correct
37 Correct 618 ms 116332 KB Output is correct
38 Correct 1091 ms 177004 KB Output is correct
39 Correct 722 ms 132744 KB Output is correct
40 Correct 995 ms 178284 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 1900 KB Output is correct
3 Correct 8 ms 2176 KB Output is correct
4 Correct 4 ms 1132 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 7 ms 1776 KB Output is correct
7 Correct 6 ms 1900 KB Output is correct
8 Correct 7 ms 2156 KB Output is correct
9 Correct 5 ms 1516 KB Output is correct
10 Correct 8 ms 2028 KB Output is correct
11 Correct 8 ms 2156 KB Output is correct
12 Correct 4 ms 1004 KB Output is correct
13 Correct 726 ms 148868 KB Output is correct
14 Correct 475 ms 94700 KB Output is correct
15 Correct 537 ms 101484 KB Output is correct
16 Correct 604 ms 110700 KB Output is correct
17 Correct 729 ms 129644 KB Output is correct
18 Correct 961 ms 173024 KB Output is correct
19 Correct 663 ms 114284 KB Output is correct
20 Correct 462 ms 97096 KB Output is correct
21 Correct 663 ms 119020 KB Output is correct
22 Correct 818 ms 141328 KB Output is correct
23 Correct 679 ms 143252 KB Output is correct
24 Correct 646 ms 131620 KB Output is correct
25 Correct 709 ms 131564 KB Output is correct
26 Correct 486 ms 97900 KB Output is correct
27 Correct 692 ms 125804 KB Output is correct
28 Correct 717 ms 124524 KB Output is correct
29 Correct 887 ms 161772 KB Output is correct
30 Correct 776 ms 132588 KB Output is correct
31 Correct 659 ms 116180 KB Output is correct
32 Correct 1018 ms 145152 KB Output is correct
33 Correct 489 ms 88044 KB Output is correct
34 Correct 510 ms 94512 KB Output is correct
35 Correct 750 ms 136684 KB Output is correct
36 Correct 746 ms 132604 KB Output is correct
37 Correct 768 ms 140396 KB Output is correct
38 Correct 1174 ms 179244 KB Output is correct
39 Correct 7 ms 2284 KB Output is correct
40 Correct 7 ms 1772 KB Output is correct
41 Correct 7 ms 1772 KB Output is correct
42 Correct 5 ms 1260 KB Output is correct
43 Correct 7 ms 1644 KB Output is correct
44 Correct 8 ms 2028 KB Output is correct
45 Correct 7 ms 1772 KB Output is correct
46 Correct 6 ms 1472 KB Output is correct
47 Correct 11 ms 2284 KB Output is correct
48 Correct 9 ms 2156 KB Output is correct
49 Correct 12 ms 2080 KB Output is correct
50 Correct 8 ms 1900 KB Output is correct
51 Correct 8 ms 1900 KB Output is correct
52 Correct 8 ms 1900 KB Output is correct
53 Correct 6 ms 1644 KB Output is correct
54 Correct 6 ms 1644 KB Output is correct
55 Correct 7 ms 1644 KB Output is correct
56 Correct 7 ms 2028 KB Output is correct
57 Correct 741 ms 155240 KB Output is correct
58 Correct 627 ms 118956 KB Output is correct
59 Correct 1002 ms 163712 KB Output is correct
60 Correct 568 ms 98436 KB Output is correct
61 Correct 569 ms 105452 KB Output is correct
62 Correct 618 ms 116332 KB Output is correct
63 Correct 1091 ms 177004 KB Output is correct
64 Correct 722 ms 132744 KB Output is correct
65 Correct 995 ms 178284 KB Output is correct
66 Correct 494 ms 106620 KB Output is correct
67 Correct 995 ms 150540 KB Output is correct
68 Correct 725 ms 103536 KB Output is correct
69 Correct 891 ms 139180 KB Output is correct
70 Correct 508 ms 110736 KB Output is correct
71 Correct 1035 ms 177132 KB Output is correct
72 Correct 598 ms 111980 KB Output is correct
73 Correct 778 ms 146412 KB Output is correct
74 Correct 524 ms 90988 KB Output is correct
75 Correct 821 ms 150124 KB Output is correct
76 Correct 566 ms 104556 KB Output is correct
77 Correct 803 ms 140120 KB Output is correct
78 Correct 536 ms 99820 KB Output is correct
79 Correct 697 ms 129388 KB Output is correct
80 Correct 915 ms 161672 KB Output is correct
81 Correct 498 ms 106476 KB Output is correct
82 Correct 697 ms 134892 KB Output is correct
83 Correct 512 ms 89836 KB Output is correct
84 Correct 537 ms 97384 KB Output is correct
85 Correct 494 ms 91188 KB Output is correct
86 Correct 869 ms 161184 KB Output is correct
87 Correct 538 ms 91624 KB Output is correct
88 Correct 989 ms 161260 KB Output is correct
89 Correct 708 ms 130412 KB Output is correct
90 Correct 638 ms 118124 KB Output is correct
91 Correct 1386 ms 189228 KB Output is correct
92 Correct 1022 ms 179404 KB Output is correct
93 Correct 1227 ms 184300 KB Output is correct
94 Correct 1211 ms 184212 KB Output is correct
95 Correct 927 ms 159212 KB Output is correct
96 Correct 687 ms 124780 KB Output is correct
97 Correct 987 ms 169840 KB Output is correct
98 Correct 781 ms 112620 KB Output is correct
99 Correct 907 ms 127080 KB Output is correct
100 Correct 874 ms 122964 KB Output is correct