Submission #1307584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307584		ndn_it81	Solar Storm (NOI20_solarstorm)	C++20	100 / 100	547 ms	242160 KiB

SolarStorm

#include <bits/stdc++.h>
#define int long long
#define fr(i,a,n) for(int i=a;i<=n;i++)
#define fx(i,a,b) for(int i=a;i>=b;i--)
#define endl "\n"
using namespace std;
const int N=1e6+6;
int nxt[N][25];
int x[N],v[N],vt[N],cnt[N];
void sol(){
    int n,k,r;
    if(!(cin>>n>>k>>r)) return;
    x[1]=0;
    fr(i,1,n-1){
        int d; cin>>d;
        x[i+1]=x[i]+d;
    }
    fr(i,1,n){
        cin>>v[i];
        cnt[i]=cnt[i-1]+v[i];
    }
    int idx=1;
    int j=1;
    fr(i,1,n){
        while(idx+1<=n && x[idx+1]<=x[i]+r) ++idx;
        vt[i]=idx;
        if(j<idx) j=idx;
        while(j+1<=n && x[j+1]<=x[idx]+r) ++j;
        nxt[i][0]=j+1;
    }
    fr(p,0,22) nxt[n+1][p]=n+1;
    fr(p,1,22){
        fr(i,1,n) nxt[i][p]=nxt[nxt[i][p-1]][p-1];
    }
    int ans=-1;
    int L=1,R=1;
    fr(i,1,n){
        int cur=i;
        int tmp=k;
        fx(p,22,0){
            if((tmp>>p)&1){
                cur=nxt[cur][p];
                if(cur>n) break;
            }
        }
        int sum=cnt[min(n,cur-1)]-cnt[i-1];
        if(sum>ans){
            ans=sum;
            L=i;
            R=min(n,cur-1);
        }
    }
    vector<int> res;
    idx=L;
    while(idx<=R && (int)res.size()<k){
        res.push_back(vt[idx]);
        idx=nxt[idx][0];
    }
    cout<<res.size()<<"\n";
    fr(i,0,(int)res.size()-1) cout<<res[i]<<(i==(int)res.size()-1?"":" ");
}
signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    sol();
    return 0;
}

• 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