#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
#define ll long long
ll A[N], prefix[N];
int V[N];
int nxt[N], before[N], parent[N];
vector<int> adj[N];
int n, s, ans_start;
ll ans = 0;
vector<int> LOL;
void dfs(int u) {
LOL.push_back(u);
if(u != n) {
int l = before[u];
int r = nxt[LOL[max(0, (int)LOL.size() - s)]] - 1;
ll candidate = prefix[r] - (l == -1 ? 0 : prefix[l]);
//cout<<"DBG --> "<<u<<" : "<<l<<" "<<r<<" : "<<candidate<<endl;
if(candidate > ans) {
ans = candidate;
ans_start = u;
}
}
for(auto v : adj[u]) {
dfs(v);
}
LOL.pop_back();
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int diff;
ll k;
cin>>n>>s>>k;
A[0] = 0;
for(int i = 1; i < n; i++) {
cin>>diff;
A[i] = A[i - 1] + diff;
}
for(int i = 0; i < n; i++) {
cin>>V[i];
prefix[i] = (i == 0 ? 0 : prefix[i - 1]) + V[i];
}
prefix[n] = prefix[n - 1];
A[n] = A[n - 1] + 2*k;
int current_ptr = 0;
nxt[n] = n;
for(int i = 0; i < n; i++) {
for(int j = current_ptr; j <= n; j++) {
if(A[j] - A[i] > k) {
current_ptr = j;
nxt[i] = j;
break;
}
}
}
current_ptr = n;
for(int i = n; i >= 0; i--) {
for(int j = current_ptr; j >= -1; j--) {
if(j == -1 or A[i] - A[j] > k) {
current_ptr = j;
before[i] = j;
break;
}
}
}
// for(int i = 0; i < n; i++) cout<<i<<" Before: "<<before[i]<<", Next: "<<nxt[i]<<endl;
for(int i = 0; i < n; i++) {
int jump_to = nxt[i];
if(jump_to != n) {
jump_to = nxt[jump_to] - 1;
}
//cout<<i<<" --> "<<jump_to<<endl;
adj[jump_to].push_back(i);
parent[i] = jump_to;
}
dfs(n);
vector<int> Q;
for(int i = 0; i < s; i++) {
Q.push_back(ans_start);
ans_start = parent[ans_start];
if(ans_start == n) break;
}
cout<<Q.size()<<endl;
for(auto v : Q) cout<<v + 1<<" ";
cout<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
24952 KB |
Output is correct |
3 |
Correct |
25 ms |
25080 KB |
Output is correct |
4 |
Correct |
21 ms |
24440 KB |
Output is correct |
5 |
Correct |
22 ms |
23800 KB |
Output is correct |
6 |
Correct |
21 ms |
24184 KB |
Output is correct |
7 |
Correct |
25 ms |
24216 KB |
Output is correct |
8 |
Correct |
22 ms |
24312 KB |
Output is correct |
9 |
Correct |
22 ms |
24184 KB |
Output is correct |
10 |
Correct |
30 ms |
24356 KB |
Output is correct |
11 |
Correct |
29 ms |
24440 KB |
Output is correct |
12 |
Correct |
21 ms |
24312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
253 ms |
54240 KB |
Output is correct |
2 |
Correct |
157 ms |
45912 KB |
Output is correct |
3 |
Correct |
167 ms |
56436 KB |
Output is correct |
4 |
Correct |
232 ms |
63712 KB |
Output is correct |
5 |
Correct |
292 ms |
70648 KB |
Output is correct |
6 |
Correct |
336 ms |
86536 KB |
Output is correct |
7 |
Correct |
231 ms |
76396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
24952 KB |
Output is correct |
3 |
Correct |
25 ms |
25080 KB |
Output is correct |
4 |
Correct |
21 ms |
24440 KB |
Output is correct |
5 |
Correct |
22 ms |
23800 KB |
Output is correct |
6 |
Correct |
21 ms |
24184 KB |
Output is correct |
7 |
Correct |
25 ms |
24216 KB |
Output is correct |
8 |
Correct |
22 ms |
24312 KB |
Output is correct |
9 |
Correct |
22 ms |
24184 KB |
Output is correct |
10 |
Correct |
30 ms |
24356 KB |
Output is correct |
11 |
Correct |
29 ms |
24440 KB |
Output is correct |
12 |
Correct |
21 ms |
24312 KB |
Output is correct |
13 |
Correct |
253 ms |
54240 KB |
Output is correct |
14 |
Correct |
157 ms |
45912 KB |
Output is correct |
15 |
Correct |
167 ms |
56436 KB |
Output is correct |
16 |
Correct |
232 ms |
63712 KB |
Output is correct |
17 |
Correct |
292 ms |
70648 KB |
Output is correct |
18 |
Correct |
336 ms |
86536 KB |
Output is correct |
19 |
Correct |
231 ms |
76396 KB |
Output is correct |
20 |
Correct |
176 ms |
43252 KB |
Output is correct |
21 |
Correct |
279 ms |
99656 KB |
Output is correct |
22 |
Correct |
327 ms |
113912 KB |
Output is correct |
23 |
Correct |
224 ms |
52812 KB |
Output is correct |
24 |
Correct |
251 ms |
50312 KB |
Output is correct |
25 |
Correct |
282 ms |
58584 KB |
Output is correct |
26 |
Correct |
215 ms |
47676 KB |
Output is correct |
27 |
Correct |
280 ms |
57564 KB |
Output is correct |
28 |
Correct |
315 ms |
58232 KB |
Output is correct |
29 |
Correct |
373 ms |
68704 KB |
Output is correct |
30 |
Correct |
293 ms |
70768 KB |
Output is correct |
31 |
Correct |
264 ms |
80360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
321 ms |
121148 KB |
Output is correct |
2 |
Correct |
176 ms |
81508 KB |
Output is correct |
3 |
Correct |
190 ms |
86820 KB |
Output is correct |
4 |
Correct |
252 ms |
113372 KB |
Output is correct |
5 |
Correct |
250 ms |
110680 KB |
Output is correct |
6 |
Correct |
267 ms |
115812 KB |
Output is correct |
7 |
Correct |
381 ms |
145116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
24952 KB |
Output is correct |
3 |
Correct |
25 ms |
25080 KB |
Output is correct |
4 |
Correct |
21 ms |
24440 KB |
Output is correct |
5 |
Correct |
22 ms |
23800 KB |
Output is correct |
6 |
Correct |
21 ms |
24184 KB |
Output is correct |
7 |
Correct |
25 ms |
24216 KB |
Output is correct |
8 |
Correct |
22 ms |
24312 KB |
Output is correct |
9 |
Correct |
22 ms |
24184 KB |
Output is correct |
10 |
Correct |
30 ms |
24356 KB |
Output is correct |
11 |
Correct |
29 ms |
24440 KB |
Output is correct |
12 |
Correct |
21 ms |
24312 KB |
Output is correct |
13 |
Correct |
22 ms |
24312 KB |
Output is correct |
14 |
Correct |
23 ms |
24312 KB |
Output is correct |
15 |
Correct |
23 ms |
24312 KB |
Output is correct |
16 |
Correct |
21 ms |
24184 KB |
Output is correct |
17 |
Correct |
21 ms |
24696 KB |
Output is correct |
18 |
Correct |
23 ms |
24952 KB |
Output is correct |
19 |
Correct |
22 ms |
24824 KB |
Output is correct |
20 |
Correct |
22 ms |
24696 KB |
Output is correct |
21 |
Correct |
24 ms |
25208 KB |
Output is correct |
22 |
Correct |
23 ms |
25080 KB |
Output is correct |
23 |
Correct |
23 ms |
24312 KB |
Output is correct |
24 |
Correct |
22 ms |
24312 KB |
Output is correct |
25 |
Correct |
26 ms |
24568 KB |
Output is correct |
26 |
Correct |
22 ms |
24824 KB |
Output is correct |
27 |
Correct |
22 ms |
24696 KB |
Output is correct |
28 |
Correct |
23 ms |
24696 KB |
Output is correct |
29 |
Correct |
24 ms |
24700 KB |
Output is correct |
30 |
Correct |
20 ms |
24184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
24952 KB |
Output is correct |
3 |
Correct |
25 ms |
25080 KB |
Output is correct |
4 |
Correct |
21 ms |
24440 KB |
Output is correct |
5 |
Correct |
22 ms |
23800 KB |
Output is correct |
6 |
Correct |
21 ms |
24184 KB |
Output is correct |
7 |
Correct |
25 ms |
24216 KB |
Output is correct |
8 |
Correct |
22 ms |
24312 KB |
Output is correct |
9 |
Correct |
22 ms |
24184 KB |
Output is correct |
10 |
Correct |
30 ms |
24356 KB |
Output is correct |
11 |
Correct |
29 ms |
24440 KB |
Output is correct |
12 |
Correct |
21 ms |
24312 KB |
Output is correct |
13 |
Correct |
253 ms |
54240 KB |
Output is correct |
14 |
Correct |
157 ms |
45912 KB |
Output is correct |
15 |
Correct |
167 ms |
56436 KB |
Output is correct |
16 |
Correct |
232 ms |
63712 KB |
Output is correct |
17 |
Correct |
292 ms |
70648 KB |
Output is correct |
18 |
Correct |
336 ms |
86536 KB |
Output is correct |
19 |
Correct |
231 ms |
76396 KB |
Output is correct |
20 |
Correct |
176 ms |
43252 KB |
Output is correct |
21 |
Correct |
279 ms |
99656 KB |
Output is correct |
22 |
Correct |
327 ms |
113912 KB |
Output is correct |
23 |
Correct |
224 ms |
52812 KB |
Output is correct |
24 |
Correct |
251 ms |
50312 KB |
Output is correct |
25 |
Correct |
282 ms |
58584 KB |
Output is correct |
26 |
Correct |
215 ms |
47676 KB |
Output is correct |
27 |
Correct |
280 ms |
57564 KB |
Output is correct |
28 |
Correct |
315 ms |
58232 KB |
Output is correct |
29 |
Correct |
373 ms |
68704 KB |
Output is correct |
30 |
Correct |
293 ms |
70768 KB |
Output is correct |
31 |
Correct |
264 ms |
80360 KB |
Output is correct |
32 |
Correct |
386 ms |
54624 KB |
Output is correct |
33 |
Correct |
235 ms |
53648 KB |
Output is correct |
34 |
Correct |
353 ms |
68996 KB |
Output is correct |
35 |
Correct |
229 ms |
51064 KB |
Output is correct |
36 |
Correct |
249 ms |
53212 KB |
Output is correct |
37 |
Correct |
283 ms |
57568 KB |
Output is correct |
38 |
Correct |
402 ms |
94540 KB |
Output is correct |
39 |
Correct |
298 ms |
107296 KB |
Output is correct |
40 |
Correct |
393 ms |
137388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
24952 KB |
Output is correct |
3 |
Correct |
25 ms |
25080 KB |
Output is correct |
4 |
Correct |
21 ms |
24440 KB |
Output is correct |
5 |
Correct |
22 ms |
23800 KB |
Output is correct |
6 |
Correct |
21 ms |
24184 KB |
Output is correct |
7 |
Correct |
25 ms |
24216 KB |
Output is correct |
8 |
Correct |
22 ms |
24312 KB |
Output is correct |
9 |
Correct |
22 ms |
24184 KB |
Output is correct |
10 |
Correct |
30 ms |
24356 KB |
Output is correct |
11 |
Correct |
29 ms |
24440 KB |
Output is correct |
12 |
Correct |
21 ms |
24312 KB |
Output is correct |
13 |
Correct |
253 ms |
54240 KB |
Output is correct |
14 |
Correct |
157 ms |
45912 KB |
Output is correct |
15 |
Correct |
167 ms |
56436 KB |
Output is correct |
16 |
Correct |
232 ms |
63712 KB |
Output is correct |
17 |
Correct |
292 ms |
70648 KB |
Output is correct |
18 |
Correct |
336 ms |
86536 KB |
Output is correct |
19 |
Correct |
231 ms |
76396 KB |
Output is correct |
20 |
Correct |
176 ms |
43252 KB |
Output is correct |
21 |
Correct |
279 ms |
99656 KB |
Output is correct |
22 |
Correct |
327 ms |
113912 KB |
Output is correct |
23 |
Correct |
224 ms |
52812 KB |
Output is correct |
24 |
Correct |
251 ms |
50312 KB |
Output is correct |
25 |
Correct |
282 ms |
58584 KB |
Output is correct |
26 |
Correct |
215 ms |
47676 KB |
Output is correct |
27 |
Correct |
280 ms |
57564 KB |
Output is correct |
28 |
Correct |
315 ms |
58232 KB |
Output is correct |
29 |
Correct |
373 ms |
68704 KB |
Output is correct |
30 |
Correct |
293 ms |
70768 KB |
Output is correct |
31 |
Correct |
264 ms |
80360 KB |
Output is correct |
32 |
Correct |
321 ms |
121148 KB |
Output is correct |
33 |
Correct |
176 ms |
81508 KB |
Output is correct |
34 |
Correct |
190 ms |
86820 KB |
Output is correct |
35 |
Correct |
252 ms |
113372 KB |
Output is correct |
36 |
Correct |
250 ms |
110680 KB |
Output is correct |
37 |
Correct |
267 ms |
115812 KB |
Output is correct |
38 |
Correct |
381 ms |
145116 KB |
Output is correct |
39 |
Correct |
22 ms |
24312 KB |
Output is correct |
40 |
Correct |
23 ms |
24312 KB |
Output is correct |
41 |
Correct |
23 ms |
24312 KB |
Output is correct |
42 |
Correct |
21 ms |
24184 KB |
Output is correct |
43 |
Correct |
21 ms |
24696 KB |
Output is correct |
44 |
Correct |
23 ms |
24952 KB |
Output is correct |
45 |
Correct |
22 ms |
24824 KB |
Output is correct |
46 |
Correct |
22 ms |
24696 KB |
Output is correct |
47 |
Correct |
24 ms |
25208 KB |
Output is correct |
48 |
Correct |
23 ms |
25080 KB |
Output is correct |
49 |
Correct |
23 ms |
24312 KB |
Output is correct |
50 |
Correct |
22 ms |
24312 KB |
Output is correct |
51 |
Correct |
26 ms |
24568 KB |
Output is correct |
52 |
Correct |
22 ms |
24824 KB |
Output is correct |
53 |
Correct |
22 ms |
24696 KB |
Output is correct |
54 |
Correct |
23 ms |
24696 KB |
Output is correct |
55 |
Correct |
24 ms |
24700 KB |
Output is correct |
56 |
Correct |
20 ms |
24184 KB |
Output is correct |
57 |
Correct |
386 ms |
54624 KB |
Output is correct |
58 |
Correct |
235 ms |
53648 KB |
Output is correct |
59 |
Correct |
353 ms |
68996 KB |
Output is correct |
60 |
Correct |
229 ms |
51064 KB |
Output is correct |
61 |
Correct |
249 ms |
53212 KB |
Output is correct |
62 |
Correct |
283 ms |
57568 KB |
Output is correct |
63 |
Correct |
402 ms |
94540 KB |
Output is correct |
64 |
Correct |
298 ms |
107296 KB |
Output is correct |
65 |
Correct |
393 ms |
137388 KB |
Output is correct |
66 |
Correct |
180 ms |
46568 KB |
Output is correct |
67 |
Correct |
354 ms |
123332 KB |
Output is correct |
68 |
Correct |
270 ms |
91996 KB |
Output is correct |
69 |
Correct |
329 ms |
114120 KB |
Output is correct |
70 |
Correct |
203 ms |
47208 KB |
Output is correct |
71 |
Correct |
392 ms |
72752 KB |
Output is correct |
72 |
Correct |
258 ms |
54904 KB |
Output is correct |
73 |
Correct |
349 ms |
65836 KB |
Output is correct |
74 |
Correct |
214 ms |
66532 KB |
Output is correct |
75 |
Correct |
317 ms |
116704 KB |
Output is correct |
76 |
Correct |
242 ms |
90332 KB |
Output is correct |
77 |
Correct |
313 ms |
61688 KB |
Output is correct |
78 |
Correct |
220 ms |
87656 KB |
Output is correct |
79 |
Correct |
296 ms |
106184 KB |
Output is correct |
80 |
Correct |
363 ms |
126936 KB |
Output is correct |
81 |
Correct |
190 ms |
46568 KB |
Output is correct |
82 |
Correct |
275 ms |
57868 KB |
Output is correct |
83 |
Correct |
208 ms |
48504 KB |
Output is correct |
84 |
Correct |
228 ms |
50808 KB |
Output is correct |
85 |
Correct |
211 ms |
49144 KB |
Output is correct |
86 |
Correct |
379 ms |
70520 KB |
Output is correct |
87 |
Correct |
214 ms |
62824 KB |
Output is correct |
88 |
Correct |
353 ms |
68344 KB |
Output is correct |
89 |
Correct |
278 ms |
106336 KB |
Output is correct |
90 |
Correct |
266 ms |
98632 KB |
Output is correct |
91 |
Correct |
527 ms |
148288 KB |
Output is correct |
92 |
Correct |
384 ms |
138588 KB |
Output is correct |
93 |
Correct |
447 ms |
145116 KB |
Output is correct |
94 |
Correct |
433 ms |
145100 KB |
Output is correct |
95 |
Correct |
360 ms |
67772 KB |
Output is correct |
96 |
Correct |
291 ms |
58520 KB |
Output is correct |
97 |
Correct |
388 ms |
76384 KB |
Output is correct |
98 |
Correct |
268 ms |
67048 KB |
Output is correct |
99 |
Correct |
331 ms |
105404 KB |
Output is correct |
100 |
Correct |
316 ms |
104284 KB |
Output is correct |