Submission #211486

#	Time	Username	Problem	Language	Result	Execution time	Memory
211486		popovicirobert	Solar Storm (NOI20_solarstorm)	C++14	100 / 100	459 ms	113200 KiB

SolarStorm

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x))

using namespace std;



int main() {
#ifdef HOME
	ifstream cin("C.in");
	ofstream cout("C.out");
#endif
	int i, n, s;
	ll k;
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> s >> k;
	vector<ll> x(n + 1), v(n + 1);
	for(i = 2; i <= n; i++) {
		int d; cin >> d;
		x[i] = x[i - 1] + d;
	}
	for(i = 1; i <= n; i++) {
		cin >> v[i];
		v[i] += v[i - 1];
	}
	vector<vector<int>> anc(20, vector<int>(n + 1));
	vector<int> nxt(n + 1);
	int a = 1, b = 1;
	for(i = 1; i <= n; i++) {
		while(a <= n && x[a] - x[i] <= k) {
			a++;
		}
		nxt[i] = a - 1;
		while(b <= n && x[b] - x[a] <= k) {
			b++;
		}
		anc[0][i] = b - 1;
	}
	for(int bit = 1; bit < 20; bit++) {
		for(i = 1; i <= n; i++) {
			anc[bit][i] = anc[bit - 1][anc[bit - 1][i]];
		}
	}
	x[0] = 1e18;
	int id, l = 1;
	ll ans = 0;
	for(i = 1; i <= n; i++) {
		while(x[i] - x[l] > k) {
			l++;
		}
		int r = i;
		for(int bit = 19; bit >= 0; bit--) {
			if((s - 1) & (1 << bit)) {
				r = anc[bit][r];
			}
		}
		r = nxt[r];
		//cerr << i << " " << l << " " << r << "\n";
		if(ans < v[r] - v[l - 1]) {
			ans = v[r] - v[l - 1];
			id = i;
		}
	}
	vector<int> sol;
	while(s > 0 && id != 0) {
		sol.push_back(id);
		id = anc[0][id];
		s--;
	}
	cout << sol.size() << "\n";
	for(auto it : sol) {
		cout << it << " ";
	}

	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