#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x))
using namespace std;
int main() {
#ifdef HOME
ifstream cin("C.in");
ofstream cout("C.out");
#endif
int i, n, s;
ll k;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> s >> k;
vector<ll> x(n + 1), v(n + 1);
for(i = 2; i <= n; i++) {
int d; cin >> d;
x[i] = x[i - 1] + d;
}
for(i = 1; i <= n; i++) {
cin >> v[i];
v[i] += v[i - 1];
}
vector<vector<int>> anc(20, vector<int>(n + 1));
vector<int> nxt(n + 1);
int a = 1, b = 1;
for(i = 1; i <= n; i++) {
while(a <= n && x[a] - x[i] <= k) {
a++;
}
nxt[i] = a - 1;
while(b <= n && x[b] - x[a] <= k) {
b++;
}
anc[0][i] = b - 1;
}
for(int bit = 1; bit < 20; bit++) {
for(i = 1; i <= n; i++) {
anc[bit][i] = anc[bit - 1][anc[bit - 1][i]];
}
}
x[0] = 1e18;
int id, l = 1;
ll ans = 0;
for(i = 1; i <= n; i++) {
while(x[i] - x[l] > k) {
l++;
}
int r = i;
for(int bit = 19; bit >= 0; bit--) {
if((s - 1) & (1 << bit)) {
r = anc[bit][r];
}
}
r = nxt[r];
//cerr << i << " " << l << " " << r << "\n";
if(ans < v[r] - v[l - 1]) {
ans = v[r] - v[l - 1];
id = i;
}
}
vector<int> sol;
while(s > 0 && id != 0) {
sol.push_back(id);
id = anc[0][id];
s--;
}
cout << sol.size() << "\n";
for(auto it : sol) {
cout << it << " ";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
7 ms |
1280 KB |
Output is correct |
3 |
Correct |
8 ms |
1280 KB |
Output is correct |
4 |
Correct |
6 ms |
768 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
1152 KB |
Output is correct |
7 |
Correct |
7 ms |
1152 KB |
Output is correct |
8 |
Correct |
7 ms |
1280 KB |
Output is correct |
9 |
Correct |
6 ms |
896 KB |
Output is correct |
10 |
Correct |
8 ms |
1280 KB |
Output is correct |
11 |
Correct |
8 ms |
1280 KB |
Output is correct |
12 |
Correct |
6 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
248 ms |
84420 KB |
Output is correct |
2 |
Correct |
162 ms |
53752 KB |
Output is correct |
3 |
Correct |
162 ms |
57592 KB |
Output is correct |
4 |
Correct |
177 ms |
62780 KB |
Output is correct |
5 |
Correct |
207 ms |
73488 KB |
Output is correct |
6 |
Correct |
276 ms |
97984 KB |
Output is correct |
7 |
Correct |
183 ms |
64760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
7 ms |
1280 KB |
Output is correct |
3 |
Correct |
8 ms |
1280 KB |
Output is correct |
4 |
Correct |
6 ms |
768 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
1152 KB |
Output is correct |
7 |
Correct |
7 ms |
1152 KB |
Output is correct |
8 |
Correct |
7 ms |
1280 KB |
Output is correct |
9 |
Correct |
6 ms |
896 KB |
Output is correct |
10 |
Correct |
8 ms |
1280 KB |
Output is correct |
11 |
Correct |
8 ms |
1280 KB |
Output is correct |
12 |
Correct |
6 ms |
768 KB |
Output is correct |
13 |
Correct |
248 ms |
84420 KB |
Output is correct |
14 |
Correct |
162 ms |
53752 KB |
Output is correct |
15 |
Correct |
162 ms |
57592 KB |
Output is correct |
16 |
Correct |
177 ms |
62780 KB |
Output is correct |
17 |
Correct |
207 ms |
73488 KB |
Output is correct |
18 |
Correct |
276 ms |
97984 KB |
Output is correct |
19 |
Correct |
183 ms |
64760 KB |
Output is correct |
20 |
Correct |
193 ms |
53672 KB |
Output is correct |
21 |
Correct |
228 ms |
65784 KB |
Output is correct |
22 |
Correct |
261 ms |
77944 KB |
Output is correct |
23 |
Correct |
246 ms |
80256 KB |
Output is correct |
24 |
Correct |
269 ms |
72504 KB |
Output is correct |
25 |
Correct |
257 ms |
72628 KB |
Output is correct |
26 |
Correct |
203 ms |
54168 KB |
Output is correct |
27 |
Correct |
253 ms |
69428 KB |
Output is correct |
28 |
Correct |
261 ms |
68688 KB |
Output is correct |
29 |
Correct |
328 ms |
89244 KB |
Output is correct |
30 |
Correct |
277 ms |
72992 KB |
Output is correct |
31 |
Correct |
235 ms |
64136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
283 ms |
89296 KB |
Output is correct |
2 |
Correct |
139 ms |
50116 KB |
Output is correct |
3 |
Correct |
144 ms |
53548 KB |
Output is correct |
4 |
Correct |
230 ms |
77432 KB |
Output is correct |
5 |
Correct |
206 ms |
75128 KB |
Output is correct |
6 |
Correct |
226 ms |
79520 KB |
Output is correct |
7 |
Correct |
378 ms |
106032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
7 ms |
1280 KB |
Output is correct |
3 |
Correct |
8 ms |
1280 KB |
Output is correct |
4 |
Correct |
6 ms |
768 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
1152 KB |
Output is correct |
7 |
Correct |
7 ms |
1152 KB |
Output is correct |
8 |
Correct |
7 ms |
1280 KB |
Output is correct |
9 |
Correct |
6 ms |
896 KB |
Output is correct |
10 |
Correct |
8 ms |
1280 KB |
Output is correct |
11 |
Correct |
8 ms |
1280 KB |
Output is correct |
12 |
Correct |
6 ms |
768 KB |
Output is correct |
13 |
Correct |
8 ms |
1280 KB |
Output is correct |
14 |
Correct |
7 ms |
1152 KB |
Output is correct |
15 |
Correct |
7 ms |
1152 KB |
Output is correct |
16 |
Correct |
6 ms |
896 KB |
Output is correct |
17 |
Correct |
7 ms |
1024 KB |
Output is correct |
18 |
Correct |
7 ms |
1280 KB |
Output is correct |
19 |
Correct |
7 ms |
1152 KB |
Output is correct |
20 |
Correct |
7 ms |
1024 KB |
Output is correct |
21 |
Correct |
9 ms |
1408 KB |
Output is correct |
22 |
Correct |
8 ms |
1280 KB |
Output is correct |
23 |
Correct |
8 ms |
1280 KB |
Output is correct |
24 |
Correct |
8 ms |
1280 KB |
Output is correct |
25 |
Correct |
8 ms |
1280 KB |
Output is correct |
26 |
Correct |
7 ms |
1280 KB |
Output is correct |
27 |
Correct |
7 ms |
1024 KB |
Output is correct |
28 |
Correct |
7 ms |
1024 KB |
Output is correct |
29 |
Correct |
7 ms |
1024 KB |
Output is correct |
30 |
Correct |
7 ms |
1280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
7 ms |
1280 KB |
Output is correct |
3 |
Correct |
8 ms |
1280 KB |
Output is correct |
4 |
Correct |
6 ms |
768 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
1152 KB |
Output is correct |
7 |
Correct |
7 ms |
1152 KB |
Output is correct |
8 |
Correct |
7 ms |
1280 KB |
Output is correct |
9 |
Correct |
6 ms |
896 KB |
Output is correct |
10 |
Correct |
8 ms |
1280 KB |
Output is correct |
11 |
Correct |
8 ms |
1280 KB |
Output is correct |
12 |
Correct |
6 ms |
768 KB |
Output is correct |
13 |
Correct |
248 ms |
84420 KB |
Output is correct |
14 |
Correct |
162 ms |
53752 KB |
Output is correct |
15 |
Correct |
162 ms |
57592 KB |
Output is correct |
16 |
Correct |
177 ms |
62780 KB |
Output is correct |
17 |
Correct |
207 ms |
73488 KB |
Output is correct |
18 |
Correct |
276 ms |
97984 KB |
Output is correct |
19 |
Correct |
183 ms |
64760 KB |
Output is correct |
20 |
Correct |
193 ms |
53672 KB |
Output is correct |
21 |
Correct |
228 ms |
65784 KB |
Output is correct |
22 |
Correct |
261 ms |
77944 KB |
Output is correct |
23 |
Correct |
246 ms |
80256 KB |
Output is correct |
24 |
Correct |
269 ms |
72504 KB |
Output is correct |
25 |
Correct |
257 ms |
72628 KB |
Output is correct |
26 |
Correct |
203 ms |
54168 KB |
Output is correct |
27 |
Correct |
253 ms |
69428 KB |
Output is correct |
28 |
Correct |
261 ms |
68688 KB |
Output is correct |
29 |
Correct |
328 ms |
89244 KB |
Output is correct |
30 |
Correct |
277 ms |
72992 KB |
Output is correct |
31 |
Correct |
235 ms |
64136 KB |
Output is correct |
32 |
Correct |
276 ms |
85624 KB |
Output is correct |
33 |
Correct |
230 ms |
65656 KB |
Output is correct |
34 |
Correct |
323 ms |
90232 KB |
Output is correct |
35 |
Correct |
199 ms |
54392 KB |
Output is correct |
36 |
Correct |
205 ms |
58104 KB |
Output is correct |
37 |
Correct |
231 ms |
64132 KB |
Output is correct |
38 |
Correct |
349 ms |
97400 KB |
Output is correct |
39 |
Correct |
251 ms |
73208 KB |
Output is correct |
40 |
Correct |
339 ms |
98300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
7 ms |
1280 KB |
Output is correct |
3 |
Correct |
8 ms |
1280 KB |
Output is correct |
4 |
Correct |
6 ms |
768 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
1152 KB |
Output is correct |
7 |
Correct |
7 ms |
1152 KB |
Output is correct |
8 |
Correct |
7 ms |
1280 KB |
Output is correct |
9 |
Correct |
6 ms |
896 KB |
Output is correct |
10 |
Correct |
8 ms |
1280 KB |
Output is correct |
11 |
Correct |
8 ms |
1280 KB |
Output is correct |
12 |
Correct |
6 ms |
768 KB |
Output is correct |
13 |
Correct |
248 ms |
84420 KB |
Output is correct |
14 |
Correct |
162 ms |
53752 KB |
Output is correct |
15 |
Correct |
162 ms |
57592 KB |
Output is correct |
16 |
Correct |
177 ms |
62780 KB |
Output is correct |
17 |
Correct |
207 ms |
73488 KB |
Output is correct |
18 |
Correct |
276 ms |
97984 KB |
Output is correct |
19 |
Correct |
183 ms |
64760 KB |
Output is correct |
20 |
Correct |
193 ms |
53672 KB |
Output is correct |
21 |
Correct |
228 ms |
65784 KB |
Output is correct |
22 |
Correct |
261 ms |
77944 KB |
Output is correct |
23 |
Correct |
246 ms |
80256 KB |
Output is correct |
24 |
Correct |
269 ms |
72504 KB |
Output is correct |
25 |
Correct |
257 ms |
72628 KB |
Output is correct |
26 |
Correct |
203 ms |
54168 KB |
Output is correct |
27 |
Correct |
253 ms |
69428 KB |
Output is correct |
28 |
Correct |
261 ms |
68688 KB |
Output is correct |
29 |
Correct |
328 ms |
89244 KB |
Output is correct |
30 |
Correct |
277 ms |
72992 KB |
Output is correct |
31 |
Correct |
235 ms |
64136 KB |
Output is correct |
32 |
Correct |
283 ms |
89296 KB |
Output is correct |
33 |
Correct |
139 ms |
50116 KB |
Output is correct |
34 |
Correct |
144 ms |
53548 KB |
Output is correct |
35 |
Correct |
230 ms |
77432 KB |
Output is correct |
36 |
Correct |
206 ms |
75128 KB |
Output is correct |
37 |
Correct |
226 ms |
79520 KB |
Output is correct |
38 |
Correct |
378 ms |
106032 KB |
Output is correct |
39 |
Correct |
8 ms |
1280 KB |
Output is correct |
40 |
Correct |
7 ms |
1152 KB |
Output is correct |
41 |
Correct |
7 ms |
1152 KB |
Output is correct |
42 |
Correct |
6 ms |
896 KB |
Output is correct |
43 |
Correct |
7 ms |
1024 KB |
Output is correct |
44 |
Correct |
7 ms |
1280 KB |
Output is correct |
45 |
Correct |
7 ms |
1152 KB |
Output is correct |
46 |
Correct |
7 ms |
1024 KB |
Output is correct |
47 |
Correct |
9 ms |
1408 KB |
Output is correct |
48 |
Correct |
8 ms |
1280 KB |
Output is correct |
49 |
Correct |
8 ms |
1280 KB |
Output is correct |
50 |
Correct |
8 ms |
1280 KB |
Output is correct |
51 |
Correct |
8 ms |
1280 KB |
Output is correct |
52 |
Correct |
7 ms |
1280 KB |
Output is correct |
53 |
Correct |
7 ms |
1024 KB |
Output is correct |
54 |
Correct |
7 ms |
1024 KB |
Output is correct |
55 |
Correct |
7 ms |
1024 KB |
Output is correct |
56 |
Correct |
7 ms |
1280 KB |
Output is correct |
57 |
Correct |
276 ms |
85624 KB |
Output is correct |
58 |
Correct |
230 ms |
65656 KB |
Output is correct |
59 |
Correct |
323 ms |
90232 KB |
Output is correct |
60 |
Correct |
199 ms |
54392 KB |
Output is correct |
61 |
Correct |
205 ms |
58104 KB |
Output is correct |
62 |
Correct |
231 ms |
64132 KB |
Output is correct |
63 |
Correct |
349 ms |
97400 KB |
Output is correct |
64 |
Correct |
251 ms |
73208 KB |
Output is correct |
65 |
Correct |
339 ms |
98300 KB |
Output is correct |
66 |
Correct |
284 ms |
69136 KB |
Output is correct |
67 |
Correct |
336 ms |
87168 KB |
Output is correct |
68 |
Correct |
239 ms |
63648 KB |
Output is correct |
69 |
Correct |
277 ms |
78672 KB |
Output is correct |
70 |
Correct |
209 ms |
61308 KB |
Output is correct |
71 |
Correct |
363 ms |
97528 KB |
Output is correct |
72 |
Correct |
252 ms |
61688 KB |
Output is correct |
73 |
Correct |
298 ms |
80764 KB |
Output is correct |
74 |
Correct |
180 ms |
50352 KB |
Output is correct |
75 |
Correct |
280 ms |
82844 KB |
Output is correct |
76 |
Correct |
199 ms |
57736 KB |
Output is correct |
77 |
Correct |
303 ms |
79100 KB |
Output is correct |
78 |
Correct |
196 ms |
54904 KB |
Output is correct |
79 |
Correct |
235 ms |
71292 KB |
Output is correct |
80 |
Correct |
298 ms |
89120 KB |
Output is correct |
81 |
Correct |
198 ms |
58744 KB |
Output is correct |
82 |
Correct |
264 ms |
74364 KB |
Output is correct |
83 |
Correct |
182 ms |
49612 KB |
Output is correct |
84 |
Correct |
200 ms |
53796 KB |
Output is correct |
85 |
Correct |
182 ms |
50348 KB |
Output is correct |
86 |
Correct |
316 ms |
88824 KB |
Output is correct |
87 |
Correct |
191 ms |
50596 KB |
Output is correct |
88 |
Correct |
407 ms |
99880 KB |
Output is correct |
89 |
Correct |
242 ms |
72056 KB |
Output is correct |
90 |
Correct |
216 ms |
65144 KB |
Output is correct |
91 |
Correct |
459 ms |
113200 KB |
Output is correct |
92 |
Correct |
351 ms |
99508 KB |
Output is correct |
93 |
Correct |
445 ms |
106036 KB |
Output is correct |
94 |
Correct |
444 ms |
106160 KB |
Output is correct |
95 |
Correct |
380 ms |
93656 KB |
Output is correct |
96 |
Correct |
306 ms |
80200 KB |
Output is correct |
97 |
Correct |
374 ms |
100104 KB |
Output is correct |
98 |
Correct |
289 ms |
67672 KB |
Output is correct |
99 |
Correct |
280 ms |
77492 KB |
Output is correct |
100 |
Correct |
278 ms |
74892 KB |
Output is correct |