제출 #1279950

#제출 시각아이디문제언어결과실행 시간메모리
1279950aryanSolar Storm (NOI20_solarstorm)C++20
36 / 100
2095 ms49696 KiB
#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);
    };

    i64 ans = -1;
    vector<int> fn;
    vector<bool> vis(n,false);
    for(int i = 0;i < n;i++){
        if(vis[i]) continue;
        int cur = i;
        i64 tot = 0;
        vector<pair<int,i64>> res;
        int left = n + 10;
        while(cur < n && left > 0){
           if(vis[cur]){
              left = min(s,(int)res.size());
           }
           vis[cur] = true;
           int sh = best[cur];
           int af = nx[sh];
           tot += S(cur,af - 1);
           res.emplace_back(cur,S(cur,af - 1));
           cur = af;    
           left --;
        }
        i64 cv = 0;
        for(int j = 0;j < min(s,(int)res.size());j++){
            cv += res[j].second;
        }
        i64 mv = cv;
        int mi = 0;
        for(int j = 1;j < (int)res.size();j++){
            cv -= res[j - 1].second;
            if(j + s - 1 < (int) res.size()) cv += res[j + s - 1].second;
            if(cv > mv){
                mv = cv;
                mi = j;
            }
        }
        if(mv > ans){
            ans = mv;
            vector<int> my;
            for(int j = mi;j < min(mi + s,(int)res.size());j++){
                my.push_back(best[res[j].first]);
            }
            fn = my;
        }
    }
    cout << (int) fn.size() << '\n';
    for(int &e : fn) cout << e + 1 << " ";
    cout << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...