oj.uz

Submission #340419

# Submission time Handle Problem Language Result Execution time Memory
340419 2020-12-27T15:05:47 Z mihai145 Solar Storm (NOI20_solarstorm) C++14
100 / 100
 1044 ms 121172 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/*
ifstream cin("txt.in");
ofstream cout("txt.out");
*/

const int NMAX = 1e6;
const long long INF = 1e15;
const int LGMAX = 20;

int N, S;
long long K, d[NMAX + 5], v[NMAX + 5];

int opt[NMAX + 5], lft[NMAX + 5];
int binaryLift[NMAX + 2][LGMAX + 2];

int main()
{
    cin >> N >> S >> K;

    d[0] = -INF;
    d[1] = 0;
    for(int i = 2; i <= N; i++)
    {
        cin >> d[i];
        d[i] += d[i - 1];
    }

    v[0] = 0;
    for(int i = 1; i <= N; i++)
    {
        cin >> v[i];
        v[i] += v[i - 1];
    }

    int j = 0;
    for(int i = 1; i <= N; i++)
    {
        while(j < i && d[i] - d[j] > K)
            j++;

        opt[i] = j;
        lft[i] = j - 1;
        binaryLift[i][0] = lft[opt[i]];
    }

    for(int step = 1; step <= LGMAX; step++)
        for(int i = 1; i <= N; i++)
            binaryLift[i][step] = binaryLift[binaryLift[i][step - 1]][step - 1];

    pair <long long, pair<int, int>> bst = {-1, {0, 0}};

    for(int rg = 1; rg <= N; rg++)
    {

        int s = S, lf = rg;

        for(int step = LGMAX; step >= 0; step--)
            if(s >= (1 << step))
            {
                lf = binaryLift[lf][step];
                s -= (1 << step);
            }

        bst = max(bst, {v[rg] - v[lf], {lf, rg}});
    }

    vector <int> sol;

    int curr = bst.second.second;
    while(curr > bst.second.first)
    {
        sol.push_back(opt[curr]);
        curr = binaryLift[curr][0];
    }

    reverse(sol.begin(), sol.end());

    cout << (int)sol.size() << '\n';
    for(auto it : sol)
        cout << it << ' ';

    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 1388 KB Output is correct
3 Correct 7 ms 1388 KB Output is correct
4 Correct 3 ms 876 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct
7 Correct 6 ms 1260 KB Output is correct
8 Correct 7 ms 1388 KB Output is correct
9 Correct 5 ms 1004 KB Output is correct
10 Correct 7 ms 1388 KB Output is correct
11 Correct 7 ms 1388 KB Output is correct
12 Correct 3 ms 748 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 94332 KB Output is correct
2 Correct 399 ms 60124 KB Output is correct
3 Correct 424 ms 64492 KB Output is correct
4 Correct 478 ms 70300 KB Output is correct
5 Correct 558 ms 82284 KB Output is correct
6 Correct 749 ms 109568 KB Output is correct
7 Correct 493 ms 72428 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 1388 KB Output is correct
3 Correct 7 ms 1388 KB Output is correct
4 Correct 3 ms 876 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct
7 Correct 6 ms 1260 KB Output is correct
8 Correct 7 ms 1388 KB Output is correct
9 Correct 5 ms 1004 KB Output is correct
10 Correct 7 ms 1388 KB Output is correct
11 Correct 7 ms 1388 KB Output is correct
12 Correct 3 ms 748 KB Output is correct
13 Correct 642 ms 94332 KB Output is correct
14 Correct 399 ms 60124 KB Output is correct
15 Correct 424 ms 64492 KB Output is correct
16 Correct 478 ms 70300 KB Output is correct
17 Correct 558 ms 82284 KB Output is correct
18 Correct 749 ms 109568 KB Output is correct
19 Correct 493 ms 72428 KB Output is correct
20 Correct 481 ms 60012 KB Output is correct
21 Correct 606 ms 73580 KB Output is correct
22 Correct 712 ms 87276 KB Output is correct
23 Correct 646 ms 90220 KB Output is correct
24 Correct 649 ms 81132 KB Output is correct
25 Correct 681 ms 81292 KB Output is correct
26 Correct 493 ms 60652 KB Output is correct
27 Correct 635 ms 77836 KB Output is correct
28 Correct 625 ms 76908 KB Output is correct
29 Correct 815 ms 99948 KB Output is correct
30 Correct 669 ms 81900 KB Output is correct
31 Correct 595 ms 71720 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 94676 KB Output is correct
2 Correct 387 ms 56044 KB Output is correct
3 Correct 406 ms 59884 KB Output is correct
4 Correct 587 ms 86764 KB Output is correct
5 Correct 572 ms 84332 KB Output is correct
6 Correct 605 ms 89068 KB Output is correct
7 Correct 882 ms 115816 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 1388 KB Output is correct
3 Correct 7 ms 1388 KB Output is correct
4 Correct 3 ms 876 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct
7 Correct 6 ms 1260 KB Output is correct
8 Correct 7 ms 1388 KB Output is correct
9 Correct 5 ms 1004 KB Output is correct
10 Correct 7 ms 1388 KB Output is correct
11 Correct 7 ms 1388 KB Output is correct
12 Correct 3 ms 748 KB Output is correct
13 Correct 8 ms 1388 KB Output is correct
14 Correct 7 ms 1260 KB Output is correct
15 Correct 7 ms 1260 KB Output is correct
16 Correct 5 ms 1004 KB Output is correct
17 Correct 6 ms 1260 KB Output is correct
18 Correct 8 ms 1516 KB Output is correct
19 Correct 6 ms 1388 KB Output is correct
20 Correct 6 ms 1132 KB Output is correct
21 Correct 10 ms 1772 KB Output is correct
22 Correct 9 ms 1644 KB Output is correct
23 Correct 9 ms 1516 KB Output is correct
24 Correct 7 ms 1388 KB Output is correct
25 Correct 8 ms 1516 KB Output is correct
26 Correct 8 ms 1516 KB Output is correct
27 Correct 6 ms 1260 KB Output is correct
28 Correct 7 ms 1260 KB Output is correct
29 Correct 8 ms 1260 KB Output is correct
30 Correct 8 ms 1516 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 1388 KB Output is correct
3 Correct 7 ms 1388 KB Output is correct
4 Correct 3 ms 876 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct
7 Correct 6 ms 1260 KB Output is correct
8 Correct 7 ms 1388 KB Output is correct
9 Correct 5 ms 1004 KB Output is correct
10 Correct 7 ms 1388 KB Output is correct
11 Correct 7 ms 1388 KB Output is correct
12 Correct 3 ms 748 KB Output is correct
13 Correct 642 ms 94332 KB Output is correct
14 Correct 399 ms 60124 KB Output is correct
15 Correct 424 ms 64492 KB Output is correct
16 Correct 478 ms 70300 KB Output is correct
17 Correct 558 ms 82284 KB Output is correct
18 Correct 749 ms 109568 KB Output is correct
19 Correct 493 ms 72428 KB Output is correct
20 Correct 481 ms 60012 KB Output is correct
21 Correct 606 ms 73580 KB Output is correct
22 Correct 712 ms 87276 KB Output is correct
23 Correct 646 ms 90220 KB Output is correct
24 Correct 649 ms 81132 KB Output is correct
25 Correct 681 ms 81292 KB Output is correct
26 Correct 493 ms 60652 KB Output is correct
27 Correct 635 ms 77836 KB Output is correct
28 Correct 625 ms 76908 KB Output is correct
29 Correct 815 ms 99948 KB Output is correct
30 Correct 669 ms 81900 KB Output is correct
31 Correct 595 ms 71720 KB Output is correct
32 Correct 771 ms 95852 KB Output is correct
33 Correct 594 ms 73452 KB Output is correct
34 Correct 828 ms 101980 KB Output is correct
35 Correct 500 ms 61864 KB Output is correct
36 Correct 529 ms 66028 KB Output is correct
37 Correct 582 ms 73068 KB Output is correct
38 Correct 890 ms 110060 KB Output is correct
39 Correct 672 ms 82964 KB Output is correct
40 Correct 902 ms 110700 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 1388 KB Output is correct
3 Correct 7 ms 1388 KB Output is correct
4 Correct 3 ms 876 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct
7 Correct 6 ms 1260 KB Output is correct
8 Correct 7 ms 1388 KB Output is correct
9 Correct 5 ms 1004 KB Output is correct
10 Correct 7 ms 1388 KB Output is correct
11 Correct 7 ms 1388 KB Output is correct
12 Correct 3 ms 748 KB Output is correct
13 Correct 642 ms 94332 KB Output is correct
14 Correct 399 ms 60124 KB Output is correct
15 Correct 424 ms 64492 KB Output is correct
16 Correct 478 ms 70300 KB Output is correct
17 Correct 558 ms 82284 KB Output is correct
18 Correct 749 ms 109568 KB Output is correct
19 Correct 493 ms 72428 KB Output is correct
20 Correct 481 ms 60012 KB Output is correct
21 Correct 606 ms 73580 KB Output is correct
22 Correct 712 ms 87276 KB Output is correct
23 Correct 646 ms 90220 KB Output is correct
24 Correct 649 ms 81132 KB Output is correct
25 Correct 681 ms 81292 KB Output is correct
26 Correct 493 ms 60652 KB Output is correct
27 Correct 635 ms 77836 KB Output is correct
28 Correct 625 ms 76908 KB Output is correct
29 Correct 815 ms 99948 KB Output is correct
30 Correct 669 ms 81900 KB Output is correct
31 Correct 595 ms 71720 KB Output is correct
32 Correct 691 ms 94676 KB Output is correct
33 Correct 387 ms 56044 KB Output is correct
34 Correct 406 ms 59884 KB Output is correct
35 Correct 587 ms 86764 KB Output is correct
36 Correct 572 ms 84332 KB Output is correct
37 Correct 605 ms 89068 KB Output is correct
38 Correct 882 ms 115816 KB Output is correct
39 Correct 8 ms 1388 KB Output is correct
40 Correct 7 ms 1260 KB Output is correct
41 Correct 7 ms 1260 KB Output is correct
42 Correct 5 ms 1004 KB Output is correct
43 Correct 6 ms 1260 KB Output is correct
44 Correct 8 ms 1516 KB Output is correct
45 Correct 6 ms 1388 KB Output is correct
46 Correct 6 ms 1132 KB Output is correct
47 Correct 10 ms 1772 KB Output is correct
48 Correct 9 ms 1644 KB Output is correct
49 Correct 9 ms 1516 KB Output is correct
50 Correct 7 ms 1388 KB Output is correct
51 Correct 8 ms 1516 KB Output is correct
52 Correct 8 ms 1516 KB Output is correct
53 Correct 6 ms 1260 KB Output is correct
54 Correct 7 ms 1260 KB Output is correct
55 Correct 8 ms 1260 KB Output is correct
56 Correct 8 ms 1516 KB Output is correct
57 Correct 771 ms 95852 KB Output is correct
58 Correct 594 ms 73452 KB Output is correct
59 Correct 828 ms 101980 KB Output is correct
60 Correct 500 ms 61864 KB Output is correct
61 Correct 529 ms 66028 KB Output is correct
62 Correct 582 ms 73068 KB Output is correct
63 Correct 890 ms 110060 KB Output is correct
64 Correct 672 ms 82964 KB Output is correct
65 Correct 902 ms 110700 KB Output is correct
66 Correct 540 ms 66948 KB Output is correct
67 Correct 811 ms 95708 KB Output is correct
68 Correct 574 ms 67028 KB Output is correct
69 Correct 753 ms 87648 KB Output is correct
70 Correct 547 ms 69468 KB Output is correct
71 Correct 897 ms 110060 KB Output is correct
72 Correct 566 ms 69740 KB Output is correct
73 Correct 732 ms 90988 KB Output is correct
74 Correct 461 ms 57196 KB Output is correct
75 Correct 768 ms 93548 KB Output is correct
76 Correct 528 ms 65388 KB Output is correct
77 Correct 776 ms 87276 KB Output is correct
78 Correct 506 ms 62444 KB Output is correct
79 Correct 660 ms 80620 KB Output is correct
80 Correct 818 ms 100332 KB Output is correct
81 Correct 523 ms 66284 KB Output is correct
82 Correct 668 ms 83712 KB Output is correct
83 Correct 452 ms 56172 KB Output is correct
84 Correct 497 ms 60652 KB Output is correct
85 Correct 466 ms 56752 KB Output is correct
86 Correct 829 ms 99948 KB Output is correct
87 Correct 460 ms 57196 KB Output is correct
88 Correct 825 ms 100204 KB Output is correct
89 Correct 652 ms 80876 KB Output is correct
90 Correct 592 ms 73068 KB Output is correct
91 Correct 1044 ms 121172 KB Output is correct
92 Correct 924 ms 110948 KB Output is correct
93 Correct 1037 ms 116140 KB Output is correct
94 Correct 1032 ms 116188 KB Output is correct
95 Correct 816 ms 98292 KB Output is correct
96 Correct 623 ms 77292 KB Output is correct
97 Correct 876 ms 105188 KB Output is correct
98 Correct 615 ms 70496 KB Output is correct
99 Correct 701 ms 81236 KB Output is correct
100 Correct 680 ms 78548 KB Output is correct