Submission #1193111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193111		loom	Solar Storm (NOI20_solarstorm)	C++20	100 / 100	483 ms	195176 KiB

SolarStorm

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'

int s;
int up[1000001][20];

int sth(int x){
	for(int i=0; i<20; i++){
		if(s & (1<<i)) x = up[x][i];
	}
	return x;
}

inline void solve(){
	int n, k;
	cin>>n>>s>>k;

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

	vector<int> r(n+1, n-1);
	int i = 0, j = 0, dist = 0;
	while(i < n and j < n){
		if(j+1 < n and dist + d[j] <= k){
			dist += d[j];
			j++;
		}else{
			r[i] = j;
			dist -= d[i];
			i++;
		}
	}

	for(int i=0; i<n; i++){
		up[i][0] = r[r[i]]+1;
	}
	up[n][0] = n;

	for(int j=1; j<20; j++){
		for(int i=0; i<=n; i++){
			up[i][j] = up[up[i][j-1]][j-1];
		}
	}

	int ans = 0, ix = -1;
	for(int i=0; i<n; i++){
		int val = v[sth(i)-1] - (i == 0 ? 0 : v[i-1]);
		if(ans < val){
			ans = val;
			ix = i;
		}
	}

	vector<int> fans;
	while(s-- and ix != n){
		ix = r[ix];
		fans.push_back(ix);
		ix = r[ix]+1;
	}

	cout<<fans.size()<<nl;
	for(int x : fans) cout<<x+1<<" ";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);cout.tie(NULL);

	int t = 1;
	//cin>>t;
	while(t--) solve();

	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