Submission #832636

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
832636	2023-08-21T12:50:42 Z	NK_	Solar Storm (NOI20_solarstorm)	C++17	25 / 100	559 ms	165424 KB

SolarStorm

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 20;

int main() {
	cin.tie(0)->sync_with_stdio(0);
  	
	int N, S, K; cin >> N >> S >> K;

	vl A(N); for(int i = 1; i < N; i++) {
		cin >> A[i]; A[i] += A[i-1];
	}

	vl X(N); for(auto& x : X) cin >> x;

	vl P = {0}; for(auto& x : X) P.pb(P.back() + x);

	auto query = [&](int l, int r) {
		return P[r + 1] - P[l];
	};


	vpi nxt(N+1);
	for(int i = 0; i < N; i++) {
		int j = (--upper_bound(begin(A), end(A), A[i] + K)) - begin(A);
		int k = (--upper_bound(begin(A), end(A), A[j] + K)) - begin(A);

		nxt[i] = mp(k + 1, j); // first not chosen is k + 1, placed the shield on j
	}
	nxt[N] = mp(N, -1);

	V<vi> up(N+1, vi(LG));
	for(int i = N; i >= 0; i--) {
		up[i][0] = nxt[i].f;
		for(int x = 1; x < LG; x++) up[i][x] = up[up[i][x-1]][x-1];
	}

	auto jmp = [&](int u, int d) {
		for(int i = 0; i < LG; i++) if ((d >> i) & 1) u = up[u][i];
		return u;
	};


	ll ans = -1, best = -1;
	for(int l = 0; l < N; l++) {
		int r = jmp(l, S) - 1;
		ll res = query(l, r);
		if (ans < res) ans = res, best = l;
	}

	vi pos;
	while(S--) {
		auto [nbest, loc] = nxt[best];
		if (loc != -1) pos.pb(loc + 1); 
		best = nbest;
	}

	cout << sz(pos) << nl;
	for(auto& x : pos) cout << x << " ";
	cout << nl;

    return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	5 ms	1748 KB	Output is correct
3	Correct	6 ms	1876 KB	Output is correct
4	Correct	2 ms	980 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	3 ms	1612 KB	Output is correct
7	Correct	3 ms	1612 KB	Output is correct
8	Correct	3 ms	1876 KB	Output is correct
9	Correct	3 ms	1236 KB	Output is correct
10	Correct	4 ms	1788 KB	Output is correct
11	Correct	4 ms	1876 KB	Output is correct
12	Correct	2 ms	852 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	195 ms	127832 KB	Output is correct
2	Correct	185 ms	86080 KB	Output is correct
3	Correct	212 ms	92228 KB	Output is correct
4	Correct	269 ms	100576 KB	Output is correct
5	Correct	316 ms	117960 KB	Output is correct
6	Correct	439 ms	157184 KB	Output is correct
7	Correct	296 ms	103876 KB	Output is correct

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	5 ms	1748 KB	Output is correct
3	Correct	6 ms	1876 KB	Output is correct
4	Correct	2 ms	980 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	3 ms	1612 KB	Output is correct
7	Correct	3 ms	1612 KB	Output is correct
8	Correct	3 ms	1876 KB	Output is correct
9	Correct	3 ms	1236 KB	Output is correct
10	Correct	4 ms	1788 KB	Output is correct
11	Correct	4 ms	1876 KB	Output is correct
12	Correct	2 ms	852 KB	Output is correct
13	Correct	195 ms	127832 KB	Output is correct
14	Correct	185 ms	86080 KB	Output is correct
15	Correct	212 ms	92228 KB	Output is correct
16	Correct	269 ms	100576 KB	Output is correct
17	Correct	316 ms	117960 KB	Output is correct
18	Correct	439 ms	157184 KB	Output is correct
19	Correct	296 ms	103876 KB	Output is correct
20	Incorrect	125 ms	81160 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	397 ms	136656 KB	Output is correct
2	Correct	219 ms	80008 KB	Output is correct
3	Correct	248 ms	85940 KB	Output is correct
4	Correct	342 ms	124216 KB	Output is correct
5	Correct	331 ms	120476 KB	Output is correct
6	Correct	348 ms	127648 KB	Output is correct
7	Correct	559 ms	165424 KB	Output is correct

Subtask #5
0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	5 ms	1748 KB	Output is correct
3	Correct	6 ms	1876 KB	Output is correct
4	Correct	2 ms	980 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	3 ms	1612 KB	Output is correct
7	Correct	3 ms	1612 KB	Output is correct
8	Correct	3 ms	1876 KB	Output is correct
9	Correct	3 ms	1236 KB	Output is correct
10	Correct	4 ms	1788 KB	Output is correct
11	Correct	4 ms	1876 KB	Output is correct
12	Correct	2 ms	852 KB	Output is correct
13	Incorrect	3 ms	1736 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #6
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	5 ms	1748 KB	Output is correct
3	Correct	6 ms	1876 KB	Output is correct
4	Correct	2 ms	980 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	3 ms	1612 KB	Output is correct
7	Correct	3 ms	1612 KB	Output is correct
8	Correct	3 ms	1876 KB	Output is correct
9	Correct	3 ms	1236 KB	Output is correct
10	Correct	4 ms	1788 KB	Output is correct
11	Correct	4 ms	1876 KB	Output is correct
12	Correct	2 ms	852 KB	Output is correct
13	Correct	195 ms	127832 KB	Output is correct
14	Correct	185 ms	86080 KB	Output is correct
15	Correct	212 ms	92228 KB	Output is correct
16	Correct	269 ms	100576 KB	Output is correct
17	Correct	316 ms	117960 KB	Output is correct
18	Correct	439 ms	157184 KB	Output is correct
19	Correct	296 ms	103876 KB	Output is correct
20	Incorrect	125 ms	81160 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #7
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	5 ms	1748 KB	Output is correct
3	Correct	6 ms	1876 KB	Output is correct
4	Correct	2 ms	980 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	3 ms	1612 KB	Output is correct
7	Correct	3 ms	1612 KB	Output is correct
8	Correct	3 ms	1876 KB	Output is correct
9	Correct	3 ms	1236 KB	Output is correct
10	Correct	4 ms	1788 KB	Output is correct
11	Correct	4 ms	1876 KB	Output is correct
12	Correct	2 ms	852 KB	Output is correct
13	Correct	195 ms	127832 KB	Output is correct
14	Correct	185 ms	86080 KB	Output is correct
15	Correct	212 ms	92228 KB	Output is correct
16	Correct	269 ms	100576 KB	Output is correct
17	Correct	316 ms	117960 KB	Output is correct
18	Correct	439 ms	157184 KB	Output is correct
19	Correct	296 ms	103876 KB	Output is correct
20	Incorrect	125 ms	81160 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #832636

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 11.0

Subtask #4 8.0 / 8.0

Subtask #5 0 / 18.0

Subtask #6 0 / 16.0

Subtask #7 0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 11.0

Subtask #4
8.0 / 8.0

Subtask #5
0 / 18.0

Subtask #6
0 / 16.0

Subtask #7
0 / 30.0