Submission #1301380

#TimeUsernameProblemLanguageResultExecution timeMemory
1301380samarthkulkarniSolar Storm (NOI20_solarstorm)C++20
36 / 100
1345 ms184340 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 long long inf = 1e12;
const int N = 1e6+20;
const int K = log2(N)+5;

ll a[N], v[N];
ll n, s, 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) {
	m.ff--;
	return v[m.ss]-v[m.ff];
}

pr mq(pr p1, pr p2) {
	if (p1.ff > p2.ff) return p1;
	return p2;
}

int nxt[N];
int BL[N][K];

ll dist(ll a, ll m) {
	for (int j = K-1; j >= 0; j--) {
		if (m & (1 << j)) a = BL[a][j];
	}

	return a;
}

void solution() {
	cin >> n >> s >> k;
	iota(nxt, nxt+n+10, 0);


	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];
	for (int i = 1; i <= n; 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;
		} 
		if (nxt[i] == i && 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 ans = 0, mx = 0;



	for (int i = 1; i <= n; i++) {
		ll j = dist(i, s-1);

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

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


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

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


	cout << res.size() << endl;

	for (auto val : res) 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...