Submission #677257

#TimeUsernameProblemLanguageResultExecution timeMemory
677257dsyzSolar Storm (NOI20_solarstorm)C++17
36 / 100
519 ms214104 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
vector<ll> v[MAXN];
int parent[20][MAXN]; //(2^19 + 2^18 + 2^17 ... + 2^0) = (2^20 - 1) which is > 10^6
bool visited[MAXN];
void dfs(ll x){
	visited[x] = 1;
	for(auto u : v[x]){
		if(!visited[u]){
			parent[0][u] = x;
			visited[u] = 1;
			dfs(u);
		}
	}
}
ll fp(ll x,ll k){
	for(ll i = 19;i >= 0;i--){
		if(k >= (1<<i)){
			if(x == -1) return -1;
			x = parent[i][x];
			k -= (1<<i);
		}
	}
	return x;
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,S,K;
	cin>>N>>S>>K;
	ll d[N];
	ll arr[N];
	memset(d,0,sizeof(d));
	d[0] = 0;
	for(ll i = 1;i < N;i++){
		ll a;
		cin>>a;
		d[i] = d[i - 1] + a;
	}
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
	}
	ll indeg[N];
	memset(indeg,0,sizeof(indeg));
	for(ll i = 0;i < N;i++){
		ll p = lower_bound(d,d + N,d[i] - K) - d - 1;
		if(p < 0 || p == i) continue;
		p = lower_bound(d,d + N,d[p] - K) - d;
		if(p < 0 || p == i) continue;
		v[p].push_back(i);
		indeg[i]++;
	}
	memset(visited,0,sizeof(visited));
	memset(parent,-1,sizeof(parent));
	for(ll i = 0;i < N;i++){
		if(indeg[i] == 0){
			visited[i] = 1;
			parent[0][i] = -1;
			dfs(i);
		}
	}
	for(ll k = 1;k < 20;k++){
		for(ll i = 0;i < N;i++){
			if(parent[k - 1][i] != -1){
				parent[k][i] = parent[k - 1][parent[k - 1][i]];
			}else{
				parent[k][i] = -1;
			}
		}
	}
	ll psum[N];
	ll cur = 0;
	for(ll i = 0;i < N;i++){
		cur += arr[i];
		psum[i] = cur;
	}
	ll ans = 0;
	pair<ll,ll> range = {-1,-1};
	for(ll r = 0;r < N;r++){
		ll l = fp(r,S - 1);
		if(l == -1) l = 0;
		ll s = lower_bound(d,d + N,d[l] - K) - d;
		ll e = upper_bound(d,d + N,d[r] + K) - d - 1;
		ll sum = psum[e];
		if(s >= 1) sum -= psum[s - 1];
		if(sum > ans){
			range = {s,e};
			ans = sum;
		}
	}
	vector<ll> modules;
	ll E = upper_bound(d,d + N,d[range.first] + K) - d - 1;
	modules.push_back(E + 1);
	ll modulepos = d[E];
	for(ll i = E + 1;i <= range.second;i++){
		E++;
		if(d[i] > modulepos + K){
			modules.push_back(i + 1);
			ll newpos = upper_bound(d,d + N,d[i] + K) - d - 1;
			modulepos = d[newpos];
			i = newpos;
		}
	}
	cout<<modules.size()<<'\n';
	for(auto u : modules){
		cout<<u<<" ";
	}
	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...