Submission #1301412

#TimeUsernameProblemLanguageResultExecution timeMemory
1301412samarthkulkarniSolar Storm (NOI20_solarstorm)C++20
36 / 100
1091 ms184356 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pr pair<ll, ll>
#define ff first
#define ss second

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}

const int N = 1000200;
const int K = 24;
ll n, s, k;
ll a[N], v[N];
int nxt[N], BL[N][K];


pr pos(int i) {
	pr ans;
	ll p = 1, q = i;
	while (p <= q) {
		ll mid = (p+q)/2;
		if (a[i]-a[mid] <= k) {
			ans.ff = mid;
			q = mid-1;
		} else p = mid+1;
	}

	p = i, q = n;
	while (p <= q) {
		ll mid  = (p + q)/2;
		if (a[mid]-a[i] <= k) {
			ans.ss = mid;
			p = mid+1;
		} else q = mid-1;
	}

	return ans;
}
ll cost(pr m) {
	return v[m.ss] - v[m.ff-1];
} 
pr mq(pr p1, pr p2) {
	if (p1.ff > p2.ff) return p1;
	return p2;
}
int jump(int i) {
	for (int j = K-1; j >= 0; j--) {
		if ((s-1) & (1 << j)) i = BL[i][j];
	}
	return i;
}


void solution() {
	iota(nxt, nxt+N, 0);

	cin >> n >> s >> k;
	for (int i = 2; i <= n; i++) {cin >> a[i]; a[i] += a[i-1];}
	for (int i = 1; i <= n; i++) {cin >> v[i]; v[i] += v[i-1];}


	map<ll, pr> hm;

	for (int i = n; i >= 1; i--) {
		pr m = pos(i);

		if (hm.count(m.ss+1)) {
			nxt[i] = hm[m.ss+1].ss;
		} 
		// else if (hm.count(m.ss)) {
		// 	nxt[i] = hm[m.ss].ss;
		// }
		// hm[i] = mq(hm[i], {m.ss, i});
		hm[m.ff] = mq(hm[m.ff], {m.ss, i});
	}


	for (int j = 0; j < K; j++) {
		for (int i = 1; i <= n; i++) {
			if (j == 0) {BL[i][j] = nxt[i]; continue;}
			BL[i][j] = BL[BL[i][j-1]][j-1];
		}
	}


	ll b = 0, mx = 0;
	for (int i = 1; i <= n; i++) {
		int j = jump(i);

		ll c = cost({pos(i).ff, pos(j).ss});

		if (mx < c) {
			b = i;
			mx = c;
		}
	}


	vi ans;
	for (int i = 0; i < s; i++) {
		ans.push_back(b);
		b = nxt[b];
	}

	ans.erase(unique(all(ans)), ans.end());


	cout << ans.size() << endl;
	for (auto val : ans) cout << val << " ";

}
#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...