Submission #1092715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092715		_rain_	Solar Storm (NOI20_solarstorm)	C++14	100 / 100	284 ms	138176 KiB

SolarStorm

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define BIT(mask,x) (((mask)>>(x))&(1))
#define MASK(x) (((ll)(1)<<(x)))

const int maxn = 1e6;
const int maxlog = 20;
ll d[maxn+2] , v[maxn+2] , pre[maxn+2] , sum = 0 , k;
int s , n;

int r[maxn+2] , par[maxn+2][maxlog+2];
int jump(int u , int step){
	for (int i = 0; i <= maxlog; ++i)
		if (BIT(step,i)) u = par[u][i];
	return u;
}
ll Get(int L , int R){
	return pre[R]-pre[L-1];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> s >> k;
	d[1] = 1;
	for (int i = 2; i <= n; ++i) {
		ll x; cin >> x;
		d[i] = d[i - 1] + x;
	}
	for (int i = 1; i <= n; ++i){
		cin >> v[i];
		pre[i] = pre[i - 1] + v[i];
	}
	r[n+1] = n+1;
	for (int i = 1 , j = 1; i <= n; ++i){
		while (j <= n && d[j] - d[i] <= k) ++j;
		r[i] = j - 1;
	}
	for (int i = 1; i <= n; ++i) {
		par[i][0] = r[r[i]] + 1;
	}
	for (int j = 1; j <= maxlog; ++j){
		for (int i = 1; i + MASK(j) - 1 <= n; ++i){
			par[i][j] = par[par[i][j-1]][j-1];
		}
	}
	int source = 1 ;
	ll total = 0;
	for (int i = 1; i <= n; ++i){
		int L = i , R = jump(i,s) - 1;
		if (total < Get(L,R)){
			total = Get(L,R);
			source = i;
		}
	}
	// cout << total << ' ' << source << '\n';
	vector<int> ans;
	while (s--){
		if (source > n) break;
		ans.push_back(r[source]);
		source = par[source][0];
	}
	cout << ans.size() << '\n';
	for (auto& x : ans) cout << x << ' ';
}

• 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