Submission #1280281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280281		aryan	Solar Storm (NOI20_solarstorm)	C++20	52 / 100	692 ms	166656 KiB

SolarStorm

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;


int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,s;
    i64 k;
    cin >> n >> s >> k;
    vector<i64> d(n);
    for(int i = 1;i < n;i++){
        cin >> d[i];
        d[i] += d[i - 1];
    }
    vector<int> v(n);
    vector<i64> pref(n);
    for(int i = 0;i < n;i++){
        cin >> v[i];
        pref[i] = v[i];
        if(i) pref[i] += pref[i - 1];
    }

    vector<int> best(n); // what is the best node top put sheild if we want to take node i
    vector<int> nx(n); // next empty node if we take index i
    for(int i = 0;i < n;i++){
        int ind = upper_bound(d.begin(),d.end(),d[i] + k) - d.begin();
        nx[i] = ind;
        ind --;
        best[i] = ind;
    }

    auto S = [&](int l,int r){
        if(l > r) return 0LL;
        return pref[r] - (l ? pref[l - 1] : 0);
    };

    const int lg = 23;
    // vector<vector<pair<i64,int>>> tot(n + 1,vector<pair<i64,int>>(lg + 1)); //
    vector<vector<int>> tot(n + 1,vector<int>(lg + 1));
    for(int l = 0;l < lg;l++){
        for(int i = 0;i < n;i++){
            if(l == 0){
                int cur = i;
                int af = nx[best[cur]];
                // tot[i][0] = {S(cur,af - 1),af};
                tot[i][0] = af;
                continue;
            }
            int af = tot[i][l - 1];
            // i64 res = tot[af][l - 1].first;
            // tot[i][l].first = tot[i][l - 1].first + res;
            tot[i][l] = tot[af][l - 1];
        }
    }
    i64 ans = -1;
    int mi = -1;
    for(int i = 0;i < n;i++){
        int left = s;
        i64 val = 0;
        int cur = i;
        for(int l = lg;l >= 0;l--){
            if((1 << l) <= left){
                // val += tot[cur][l].first;
                val += S(cur,tot[cur][l] - 1);
                cur = tot[cur][l];
                left -= (1 << l);
            }
        }
        if(val > ans){
            ans = val;
            mi = i;
        }
    }    

    vector<int> res;
    while(mi < n && (int)res.size() < s){
        res.push_back(best[mi]);
        mi = nx[best[mi]];
    }

    cout << (int) res.size() << '\n';
    for(int &e : res){
        cout << e + 1 << " ";
    }
    cout << '\n';
}

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