Submission #478193

#	Time	Username	Problem	Language	Result	Execution time	Memory
478193		blue	Solar Storm (NOI20_solarstorm)	C++17	100 / 100	727 ms	169480 KiB

SolarStorm

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxN = 1'000'000;
const int logN = 21;

vector< vector<int> > R(1+maxN+1, vector<int>(1+logN));

vector<long long> val(1+maxN, 0);

int jump(int i, int s)
{
    for(int e = logN; e >= 0; e--)
    {
        if(s & (1 << e)) i = R[i][e];
    }
    return i;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, S;
    long long K;
    cin >> N >> S >> K;

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

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

    int reach_left[1+N], reach_right[1+N];

    reach_left[1] = 1;
    for(int i = 2; i <= N; i++)
    {
        reach_left[i] = reach_left[i-1];
        while(x[i] - x[ reach_left[i] ] > K)
            reach_left[i]++;
    }

    reach_right[N] = N;
    for(int i = N-1; i >= 1; i--)
    {
        reach_right[i] = reach_right[i+1];
        while(x[ reach_right[i] ] - x[i] > K)
            reach_right[i]--;
    }

    R[N+1][0] = N+1;

    vector<int> midval(1+N);

    int mid = N;
    for(int i = N; i >= 1; i--)
    {
        while(i < reach_left[mid]) mid--;
        midval[i] = mid;
        R[i][0] = reach_right[mid] + 1;
    }

    // for(int i = 1; i <= N; i++) cerr << R[i][0] << ' ';
    // cerr << '\n';

    for(int e = 1; e <= logN; e++)
    {
        for(int i = 1; i <= N+1; i++)
        {
            R[i][e] = R[ R[i][e-1] ][e-1];
        }
    }

    int opt = -1;

    long long res = -1;;
    for(int i = 1; i <= N; i++)
    {
        int J = jump(i, S);
        if(val[J - 1] - val[i - 1] > res)
        {
            res = val[J - 1] - val[i - 1];
            opt = i;
        }
    }

    // cerr << "opt = " << opt << '\n';

    vector<int> ans;
    int remaining = S;
    while(remaining > 0 && opt != N+1)
    {
        // cerr << "opt = " << opt << '\n';
        ans.push_back(midval[opt]);
        opt = jump(opt, 1);
        remaining--;
    }

    cout << (int)ans.size() << '\n';
    for(int a:ans) cout << a << ' ';
    cout << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 7 / 7
• Subtask 3: 11 / 11
• Subtask 4: 8 / 8
• Subtask 5: 18 / 18
• Subtask 6: 16 / 16
• Subtask 7: 30 / 30