Submission #832637

#	Time	Username	Problem	Language	Result	Execution time	Memory
832637		NK_	Solar Storm (NOI20_solarstorm)	C++17	100 / 100	668 ms	177364 KiB

SolarStorm

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 20;

int main() {
	cin.tie(0)->sync_with_stdio(0);
  	
	int N, S; ll K; cin >> N >> S >> K;

	vl A(N); for(int i = 1; i < N; i++) {
		cin >> A[i]; A[i] += A[i-1];
	}

	vl X(N); for(auto& x : X) cin >> x;

	vl P = {0}; for(auto& x : X) P.pb(P.back() + x);

	auto query = [&](int l, int r) {
		return P[r + 1] - P[l];
	};


	vpi nxt(N+1);
	for(int i = 0; i < N; i++) {
		int j = (--upper_bound(begin(A), end(A), A[i] + K)) - begin(A);
		int k = (--upper_bound(begin(A), end(A), A[j] + K)) - begin(A);

		nxt[i] = mp(k + 1, j); // first not chosen is k + 1, placed the shield on j
	}
	nxt[N] = mp(N, -1);

	V<vi> up(N+1, vi(LG));
	for(int i = N; i >= 0; i--) {
		up[i][0] = nxt[i].f;
		for(int x = 1; x < LG; x++) up[i][x] = up[up[i][x-1]][x-1];
	}

	auto jmp = [&](int u, int d) {
		for(int i = 0; i < LG; i++) if ((d >> i) & 1) u = up[u][i];
		return u;
	};


	ll ans = -1, best = -1;
	for(int l = 0; l < N; l++) {
		int r = jmp(l, S) - 1;
		ll res = query(l, r);
		if (ans < res) ans = res, best = l;
	}

	vi pos;
	while(S--) {
		auto [nbest, loc] = nxt[best];
		if (loc != -1) pos.pb(loc + 1); 
		best = nbest;
	}

	cout << sz(pos) << nl;
	for(auto& x : pos) cout << x << " ";
	cout << nl;

    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