oj.uz

답안 #340415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
340415 2020-12-27T14:52:14 Z mihai145 Solar Storm (NOI20_solarstorm) C++14
36 / 100
 558 ms 116324 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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    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[opt[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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 1516 KB Output is correct
3 Correct 4 ms 1644 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 1388 KB Output is correct
7 Correct 3 ms 1388 KB Output is correct
8 Correct 4 ms 1644 KB Output is correct
9 Correct 3 ms 1132 KB Output is correct
10 Correct 4 ms 1516 KB Output is correct
11 Correct 4 ms 1644 KB Output is correct
12 Correct 3 ms 876 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 382 ms 95084 KB Output is correct
2 Correct 237 ms 61036 KB Output is correct
3 Correct 251 ms 65132 KB Output is correct
4 Correct 286 ms 71020 KB Output is correct
5 Correct 328 ms 83200 KB Output is correct
6 Correct 433 ms 110316 KB Output is correct
7 Correct 296 ms 73324 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 1516 KB Output is correct
3 Correct 4 ms 1644 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 1388 KB Output is correct
7 Correct 3 ms 1388 KB Output is correct
8 Correct 4 ms 1644 KB Output is correct
9 Correct 3 ms 1132 KB Output is correct
10 Correct 4 ms 1516 KB Output is correct
11 Correct 4 ms 1644 KB Output is correct
12 Correct 3 ms 876 KB Output is correct
13 Correct 382 ms 95084 KB Output is correct
14 Correct 237 ms 61036 KB Output is correct
15 Correct 251 ms 65132 KB Output is correct
16 Correct 286 ms 71020 KB Output is correct
17 Correct 328 ms 83200 KB Output is correct
18 Correct 433 ms 110316 KB Output is correct
19 Correct 296 ms 73324 KB Output is correct
20 Correct 250 ms 61164 KB Output is correct
21 Correct 315 ms 74604 KB Output is correct
22 Correct 375 ms 88572 KB Output is correct
23 Correct 354 ms 91384 KB Output is correct
24 Correct 335 ms 82412 KB Output is correct
25 Correct 343 ms 82412 KB Output is correct
26 Correct 256 ms 61952 KB Output is correct
27 Correct 329 ms 78956 KB Output is correct
28 Correct 321 ms 77932 KB Output is correct
29 Correct 416 ms 100844 KB Output is correct
30 Correct 347 ms 82796 KB Output is correct
31 Correct 308 ms 72684 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 429 ms 95324 KB Output is correct
2 Correct 232 ms 56684 KB Output is correct
3 Correct 245 ms 60652 KB Output is correct
4 Correct 351 ms 87276 KB Output is correct
5 Correct 337 ms 84716 KB Output is correct
6 Correct 360 ms 89740 KB Output is correct
7 Correct 558 ms 116324 KB Output is correct

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 1516 KB Output is correct
3 Correct 4 ms 1644 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 1388 KB Output is correct
7 Correct 3 ms 1388 KB Output is correct
8 Correct 4 ms 1644 KB Output is correct
9 Correct 3 ms 1132 KB Output is correct
10 Correct 4 ms 1516 KB Output is correct
11 Correct 4 ms 1644 KB Output is correct
12 Correct 3 ms 876 KB Output is correct
13 Correct 5 ms 1516 KB Output is correct
14 Incorrect 3 ms 1388 KB Damaged module blocking communication between protected modules
15 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 1516 KB Output is correct
3 Correct 4 ms 1644 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 1388 KB Output is correct
7 Correct 3 ms 1388 KB Output is correct
8 Correct 4 ms 1644 KB Output is correct
9 Correct 3 ms 1132 KB Output is correct
10 Correct 4 ms 1516 KB Output is correct
11 Correct 4 ms 1644 KB Output is correct
12 Correct 3 ms 876 KB Output is correct
13 Correct 382 ms 95084 KB Output is correct
14 Correct 237 ms 61036 KB Output is correct
15 Correct 251 ms 65132 KB Output is correct
16 Correct 286 ms 71020 KB Output is correct
17 Correct 328 ms 83200 KB Output is correct
18 Correct 433 ms 110316 KB Output is correct
19 Correct 296 ms 73324 KB Output is correct
20 Correct 250 ms 61164 KB Output is correct
21 Correct 315 ms 74604 KB Output is correct
22 Correct 375 ms 88572 KB Output is correct
23 Correct 354 ms 91384 KB Output is correct
24 Correct 335 ms 82412 KB Output is correct
25 Correct 343 ms 82412 KB Output is correct
26 Correct 256 ms 61952 KB Output is correct
27 Correct 329 ms 78956 KB Output is correct
28 Correct 321 ms 77932 KB Output is correct
29 Correct 416 ms 100844 KB Output is correct
30 Correct 347 ms 82796 KB Output is correct
31 Correct 308 ms 72684 KB Output is correct
32 Correct 394 ms 96748 KB Output is correct
33 Incorrect 306 ms 74348 KB Damaged module blocking communication between protected modules
34 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 1516 KB Output is correct
3 Correct 4 ms 1644 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 1388 KB Output is correct
7 Correct 3 ms 1388 KB Output is correct
8 Correct 4 ms 1644 KB Output is correct
9 Correct 3 ms 1132 KB Output is correct
10 Correct 4 ms 1516 KB Output is correct
11 Correct 4 ms 1644 KB Output is correct
12 Correct 3 ms 876 KB Output is correct
13 Correct 382 ms 95084 KB Output is correct
14 Correct 237 ms 61036 KB Output is correct
15 Correct 251 ms 65132 KB Output is correct
16 Correct 286 ms 71020 KB Output is correct
17 Correct 328 ms 83200 KB Output is correct
18 Correct 433 ms 110316 KB Output is correct
19 Correct 296 ms 73324 KB Output is correct
20 Correct 250 ms 61164 KB Output is correct
21 Correct 315 ms 74604 KB Output is correct
22 Correct 375 ms 88572 KB Output is correct
23 Correct 354 ms 91384 KB Output is correct
24 Correct 335 ms 82412 KB Output is correct
25 Correct 343 ms 82412 KB Output is correct
26 Correct 256 ms 61952 KB Output is correct
27 Correct 329 ms 78956 KB Output is correct
28 Correct 321 ms 77932 KB Output is correct
29 Correct 416 ms 100844 KB Output is correct
30 Correct 347 ms 82796 KB Output is correct
31 Correct 308 ms 72684 KB Output is correct
32 Correct 429 ms 95324 KB Output is correct
33 Correct 232 ms 56684 KB Output is correct
34 Correct 245 ms 60652 KB Output is correct
35 Correct 351 ms 87276 KB Output is correct
36 Correct 337 ms 84716 KB Output is correct
37 Correct 360 ms 89740 KB Output is correct
38 Correct 558 ms 116324 KB Output is correct
39 Correct 5 ms 1516 KB Output is correct
40 Incorrect 3 ms 1388 KB Damaged module blocking communication between protected modules
41 Halted 0 ms 0 KB -