Submission #211246

#	Time	Username	Problem	Language	Result	Execution time	Memory
211246		socho	Solar Storm (NOI20_solarstorm)	C++14	100 / 100	1494 ms	246120 KiB

SolarStorm

#include "bits/stdc++.h"
using namespace std;

const int MXN = 1000005, MXK = 22;

long long n, s, k;
long long pf[MXN];

vector<int> subs[MXN];

int par[MXN][MXK];
int depth[MXN];

void dfs_decomp(int node, int last, int dep) {
	depth[node] = dep;
	par[node][0] = last;
	for (int i=1; i<MXK; i++) {
		int ab = par[node][i-1];
		if (ab != -1) {
			par[node][i] = par[ab][i-1];
		}
	}
	for (int i=0; i<subs[node].size(); i++) {
		if (subs[node][i] == last) continue;
		dfs_decomp(subs[node][i], node, dep+1);
	}
}

int kth_parent(int n, int k) {
	k = min(k, depth[n]);
	for (int i=0; i<MXK; i++) {
		if ((1 << i) & k) {
			n = par[n][i];
		}
	}
	return n;
}

void setup() {
	for (int i=0; i<MXN; i++) for (int j=0; j<MXK; j++) par[i][j] = -1;
	// dfs_depth(n, -1);
	dfs_decomp(n, -1, 0);
}

long long gpf(int a) {
	if (a < 0) return 0;
	return pf[a];
}

int main() {

	cin >> n >> s >> k;
	long long ad[n-1];
	for (int i=0; i<n-1; i++) cin >> ad[i];
	
	long long tr[n];
	tr[0] = 0;
	for (int i=1; i<n; i++) tr[i] = tr[i-1] + ad[i-1];
	
	long long val[n];
	for (int i=0; i<n; i++) cin >> val[i];
	partial_sum(val, val+n, pf);
	
	long long go[n];
	memset(go, 0, sizeof go);
	int with[n];
	
	for (int i=0; i<n; i++) {
		// if i placed one here
		long long lb = lower_bound(tr, tr+n, tr[i]-k) - tr;
		long long rb = upper_bound(tr, tr+n, tr[i]+k) - tr - 1;
		go[lb] = rb;
		with[lb] = i+1;
	}
	
	for (int i=1; i<n; i++) {
		if (go[i-1] > go[i]) {
			with[i] = with[i-1];
		}
		go[i] = max(go[i], go[i-1]);
	}
	
	for (int i=0; i<n; i++) {
		go[i]++;
		// cout << i << ' ' << go[i] << endl;
		subs[go[i]].push_back(i);
	}
	
	setup();
	
	long long best = 0;
	int at = 0;
	
	for (int i=0; i<n; i++) {
		long long score = gpf(kth_parent(i, s)-1) - gpf(i-1);
		if (score > best) {
			best = score;
			at = i;
		}
	}
	
	// cout << at << endl;
	
	bool can = true;
	int curr = at;
	vector<int> need;
	for (int i=0; i<s && can; i++) {
		need.push_back(with[curr]);
		// cout << curr << endl;
		curr = go[curr];
		if (curr >= n) can = false;
	}
	
	cout << need.size() << endl;
	for (int i=0; i<need.size(); i++) {
		cout << need[i] << ' ';
	}
	cout << endl;
	
}

Compilation message (stderr)

SolarStorm.cpp: In function 'void dfs_decomp(int, int, int)':
SolarStorm.cpp:23:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<subs[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~~
SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:115:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<need.size(); i++) {
                ~^~~~~~~~~~~~

• 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