Submission #224342

#	Time	Username	Problem	Language	Result	Execution time	Memory
224342		maximath_1	Solar Storm (NOI20_solarstorm)	C++14	100 / 100	398 ms	120516 KiB

SolarStorm

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAX=1000005;
const int LOG=21;
int n, s, lf[MAX], rg[MAX], par[LOG][MAX];
ll k, d[MAX], v[MAX], ans;
vector<int>ansv;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>s>>k;
	for(int i=2; i<=n; i++){
		cin>>d[i];
		d[i]+=d[i-1];
	}
	for(int i=1; i<=n; i++){
		cin>>v[i];
		v[i]+=v[i-1];
	}
	rg[0]=1;
	for(int i=1, l=1, r=1, x=0; i<=n; i++){
		for(; r<=n && d[r]<=d[i]+k; r++);
		for(; l<=n && d[l]<d[i]-k; l++);
		for(; rg[x]<l; x++);
		lf[i]=l; rg[i]=r;
		par[0][i]=x;
	}
	for(int lg=1; lg<LOG; lg++)
		for(int i=1; i<=n; i++)
			par[lg][i]=par[lg-1][par[lg-1][i]];
	int pos=0;
	for(int i=1; i<=n; i++){
		int nw=i;
		for(int lg=0; lg<LOG; lg++)
			if(((s-1)>>lg)&1) nw=par[lg][nw];
		ll tmp=v[rg[i]-1]-v[lf[nw]-1];
		if(tmp>ans){ans=tmp; pos=i;}
	}
	for(int i=0; i<s && pos>0; i++){
		ansv.push_back(pos);
		pos=par[0][pos];
	}
	cout<<ansv.size()<<endl;
	for(int i:ansv) cout<<i<<" ";
	cout<<endl;
	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