Submission #1301447

#TimeUsernameProblemLanguageResultExecution timeMemory
1301447samarthkulkarniSolar Storm (NOI20_solarstorm)C++20
100 / 100
632 ms128652 KiB









// my solutionn  !!!!!!!!!!!!!!!!!!!!!!
#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];
} 
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];}


	ll j = n;
	
	for (int i = n; i >= 1; i--) {
		ll e = pos(i).ss;
		while (pos(j).ff-1 > e) j--;
		nxt[i] = j;
	}


	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];
	}


	sort(all(ans));
	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...