Submission #211484

#	Time	Username	Problem	Language	Result	Execution time	Memory
211484		popovicirobert	Solar Storm (NOI20_solarstorm)	C++14	36 / 100	379 ms	102064 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));
	int pos = 1;
	for(i = 1; i <= n; i++) {
		while(pos <= n && x[pos] - x[i] <= k) {
			pos++;
		}
		anc[0][i] = (pos == n + 1 ? 0 : pos);
	}
	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;
	ll ans = 0;
	int l = 1, id;
	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 << bit))) {
				r = anc[bit][r];
			}
		}
		if(r == 0) {
			r = n;
		}
		else {
			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: 0 / 18
• Subtask 6: 0 / 16
• Subtask 7: 0 / 30