#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int MOD = 998244353;
ll binpow(ll a, ll p, int mod = MOD) {
ll res = 1;
while (p) {
if (p & 1) {
(res *= a) %= mod;
}
p >>= 1;
(a *= a) %= mod;
}
return res;
}
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
void solve() {
int s, n;
ll k;
cin >> n >> s >> k;
vector<ll> pos(n + 1);
pos[0] = -1;
for (int i = 2; i <= n; i++) {
cin >> pos[i];
pos[i] += pos[i - 1];
}
vector<ll> value(n + 1);
for (int i = 1; i <= n; i++) {
cin >> value[i];
value[i] += value[i - 1];
}
const int K = 21;
vector<vector<int>> go(n + 2, vector<int>(K));
go[n + 1].assign(K, n + 1);
ll best_value = -1;
ll start = 0;
for (int i = n; i >= 1; i--) {
int mid = upper_bound(pos.begin() + i, pos.end(), pos[i] + k) - pos.begin() - 1;
int lst = upper_bound(pos.begin() + mid, pos.end(), pos[mid] + k) - pos.begin();
go[i][0] = lst;
for (int j = 1; j < K; j++) {
go[i][j] = go[go[i][j - 1]][j - 1];
}
int cur = i;
for (int j = K - 1; j >= 0; j--) {
if (s >> j & 1) {
cur = go[cur][j];
}
}
ll cur_value = value[cur - 1] - value[i - 1];
if (cur_value > best_value) {
best_value = cur_value;
start = i;
}
}
vector<int> ans;
while (s && start <= n) {
int mid = upper_bound(pos.begin() + start, pos.end(), pos[start] + k) - pos.begin() - 1;
ans.push_back(mid);
start = go[start][0];
s--;
}
cout << ans.size() << endl;
for (int i : ans) {
cout << i << ' ';
}
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
for (int tc = 1; tc <= T; tc++) {
// cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
5 ms |
1484 KB |
Output is correct |
3 |
Correct |
8 ms |
1620 KB |
Output is correct |
4 |
Correct |
3 ms |
844 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
5 ms |
1356 KB |
Output is correct |
7 |
Correct |
5 ms |
1356 KB |
Output is correct |
8 |
Correct |
6 ms |
1612 KB |
Output is correct |
9 |
Correct |
4 ms |
1100 KB |
Output is correct |
10 |
Correct |
6 ms |
1612 KB |
Output is correct |
11 |
Correct |
6 ms |
1612 KB |
Output is correct |
12 |
Correct |
3 ms |
844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
413 ms |
114404 KB |
Output is correct |
2 |
Correct |
293 ms |
72840 KB |
Output is correct |
3 |
Correct |
329 ms |
78032 KB |
Output is correct |
4 |
Correct |
448 ms |
85120 KB |
Output is correct |
5 |
Correct |
538 ms |
99868 KB |
Output is correct |
6 |
Correct |
755 ms |
132912 KB |
Output is correct |
7 |
Correct |
528 ms |
87916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
5 ms |
1484 KB |
Output is correct |
3 |
Correct |
8 ms |
1620 KB |
Output is correct |
4 |
Correct |
3 ms |
844 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
5 ms |
1356 KB |
Output is correct |
7 |
Correct |
5 ms |
1356 KB |
Output is correct |
8 |
Correct |
6 ms |
1612 KB |
Output is correct |
9 |
Correct |
4 ms |
1100 KB |
Output is correct |
10 |
Correct |
6 ms |
1612 KB |
Output is correct |
11 |
Correct |
6 ms |
1612 KB |
Output is correct |
12 |
Correct |
3 ms |
844 KB |
Output is correct |
13 |
Correct |
413 ms |
114404 KB |
Output is correct |
14 |
Correct |
293 ms |
72840 KB |
Output is correct |
15 |
Correct |
329 ms |
78032 KB |
Output is correct |
16 |
Correct |
448 ms |
85120 KB |
Output is correct |
17 |
Correct |
538 ms |
99868 KB |
Output is correct |
18 |
Correct |
755 ms |
132912 KB |
Output is correct |
19 |
Correct |
528 ms |
87916 KB |
Output is correct |
20 |
Correct |
316 ms |
72568 KB |
Output is correct |
21 |
Correct |
566 ms |
89072 KB |
Output is correct |
22 |
Correct |
652 ms |
105848 KB |
Output is correct |
23 |
Correct |
409 ms |
108924 KB |
Output is correct |
24 |
Correct |
392 ms |
98380 KB |
Output is correct |
25 |
Correct |
454 ms |
98388 KB |
Output is correct |
26 |
Correct |
307 ms |
73328 KB |
Output is correct |
27 |
Correct |
453 ms |
94148 KB |
Output is correct |
28 |
Correct |
569 ms |
93144 KB |
Output is correct |
29 |
Correct |
626 ms |
121184 KB |
Output is correct |
30 |
Correct |
642 ms |
99044 KB |
Output is correct |
31 |
Correct |
516 ms |
86884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
858 ms |
113232 KB |
Output is correct |
2 |
Correct |
532 ms |
67668 KB |
Output is correct |
3 |
Correct |
381 ms |
72640 KB |
Output is correct |
4 |
Correct |
555 ms |
105156 KB |
Output is correct |
5 |
Correct |
578 ms |
101828 KB |
Output is correct |
6 |
Correct |
635 ms |
107844 KB |
Output is correct |
7 |
Correct |
1617 ms |
139272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
5 ms |
1484 KB |
Output is correct |
3 |
Correct |
8 ms |
1620 KB |
Output is correct |
4 |
Correct |
3 ms |
844 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
5 ms |
1356 KB |
Output is correct |
7 |
Correct |
5 ms |
1356 KB |
Output is correct |
8 |
Correct |
6 ms |
1612 KB |
Output is correct |
9 |
Correct |
4 ms |
1100 KB |
Output is correct |
10 |
Correct |
6 ms |
1612 KB |
Output is correct |
11 |
Correct |
6 ms |
1612 KB |
Output is correct |
12 |
Correct |
3 ms |
844 KB |
Output is correct |
13 |
Correct |
6 ms |
1612 KB |
Output is correct |
14 |
Correct |
5 ms |
1356 KB |
Output is correct |
15 |
Correct |
5 ms |
1356 KB |
Output is correct |
16 |
Correct |
5 ms |
972 KB |
Output is correct |
17 |
Correct |
4 ms |
1316 KB |
Output is correct |
18 |
Correct |
6 ms |
1484 KB |
Output is correct |
19 |
Correct |
5 ms |
1356 KB |
Output is correct |
20 |
Correct |
4 ms |
1100 KB |
Output is correct |
21 |
Correct |
7 ms |
1740 KB |
Output is correct |
22 |
Correct |
7 ms |
1612 KB |
Output is correct |
23 |
Correct |
6 ms |
1612 KB |
Output is correct |
24 |
Correct |
5 ms |
1356 KB |
Output is correct |
25 |
Correct |
6 ms |
1404 KB |
Output is correct |
26 |
Correct |
6 ms |
1484 KB |
Output is correct |
27 |
Correct |
5 ms |
1228 KB |
Output is correct |
28 |
Correct |
5 ms |
1228 KB |
Output is correct |
29 |
Correct |
5 ms |
1264 KB |
Output is correct |
30 |
Correct |
6 ms |
1484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
5 ms |
1484 KB |
Output is correct |
3 |
Correct |
8 ms |
1620 KB |
Output is correct |
4 |
Correct |
3 ms |
844 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
5 ms |
1356 KB |
Output is correct |
7 |
Correct |
5 ms |
1356 KB |
Output is correct |
8 |
Correct |
6 ms |
1612 KB |
Output is correct |
9 |
Correct |
4 ms |
1100 KB |
Output is correct |
10 |
Correct |
6 ms |
1612 KB |
Output is correct |
11 |
Correct |
6 ms |
1612 KB |
Output is correct |
12 |
Correct |
3 ms |
844 KB |
Output is correct |
13 |
Correct |
413 ms |
114404 KB |
Output is correct |
14 |
Correct |
293 ms |
72840 KB |
Output is correct |
15 |
Correct |
329 ms |
78032 KB |
Output is correct |
16 |
Correct |
448 ms |
85120 KB |
Output is correct |
17 |
Correct |
538 ms |
99868 KB |
Output is correct |
18 |
Correct |
755 ms |
132912 KB |
Output is correct |
19 |
Correct |
528 ms |
87916 KB |
Output is correct |
20 |
Correct |
316 ms |
72568 KB |
Output is correct |
21 |
Correct |
566 ms |
89072 KB |
Output is correct |
22 |
Correct |
652 ms |
105848 KB |
Output is correct |
23 |
Correct |
409 ms |
108924 KB |
Output is correct |
24 |
Correct |
392 ms |
98380 KB |
Output is correct |
25 |
Correct |
454 ms |
98388 KB |
Output is correct |
26 |
Correct |
307 ms |
73328 KB |
Output is correct |
27 |
Correct |
453 ms |
94148 KB |
Output is correct |
28 |
Correct |
569 ms |
93144 KB |
Output is correct |
29 |
Correct |
626 ms |
121184 KB |
Output is correct |
30 |
Correct |
642 ms |
99044 KB |
Output is correct |
31 |
Correct |
516 ms |
86884 KB |
Output is correct |
32 |
Correct |
446 ms |
116192 KB |
Output is correct |
33 |
Correct |
371 ms |
89028 KB |
Output is correct |
34 |
Correct |
766 ms |
122564 KB |
Output is correct |
35 |
Correct |
372 ms |
73704 KB |
Output is correct |
36 |
Correct |
381 ms |
78912 KB |
Output is correct |
37 |
Correct |
425 ms |
87032 KB |
Output is correct |
38 |
Correct |
1040 ms |
132424 KB |
Output is correct |
39 |
Correct |
562 ms |
99404 KB |
Output is correct |
40 |
Correct |
827 ms |
133448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
5 ms |
1484 KB |
Output is correct |
3 |
Correct |
8 ms |
1620 KB |
Output is correct |
4 |
Correct |
3 ms |
844 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
5 ms |
1356 KB |
Output is correct |
7 |
Correct |
5 ms |
1356 KB |
Output is correct |
8 |
Correct |
6 ms |
1612 KB |
Output is correct |
9 |
Correct |
4 ms |
1100 KB |
Output is correct |
10 |
Correct |
6 ms |
1612 KB |
Output is correct |
11 |
Correct |
6 ms |
1612 KB |
Output is correct |
12 |
Correct |
3 ms |
844 KB |
Output is correct |
13 |
Correct |
413 ms |
114404 KB |
Output is correct |
14 |
Correct |
293 ms |
72840 KB |
Output is correct |
15 |
Correct |
329 ms |
78032 KB |
Output is correct |
16 |
Correct |
448 ms |
85120 KB |
Output is correct |
17 |
Correct |
538 ms |
99868 KB |
Output is correct |
18 |
Correct |
755 ms |
132912 KB |
Output is correct |
19 |
Correct |
528 ms |
87916 KB |
Output is correct |
20 |
Correct |
316 ms |
72568 KB |
Output is correct |
21 |
Correct |
566 ms |
89072 KB |
Output is correct |
22 |
Correct |
652 ms |
105848 KB |
Output is correct |
23 |
Correct |
409 ms |
108924 KB |
Output is correct |
24 |
Correct |
392 ms |
98380 KB |
Output is correct |
25 |
Correct |
454 ms |
98388 KB |
Output is correct |
26 |
Correct |
307 ms |
73328 KB |
Output is correct |
27 |
Correct |
453 ms |
94148 KB |
Output is correct |
28 |
Correct |
569 ms |
93144 KB |
Output is correct |
29 |
Correct |
626 ms |
121184 KB |
Output is correct |
30 |
Correct |
642 ms |
99044 KB |
Output is correct |
31 |
Correct |
516 ms |
86884 KB |
Output is correct |
32 |
Correct |
858 ms |
113232 KB |
Output is correct |
33 |
Correct |
532 ms |
67668 KB |
Output is correct |
34 |
Correct |
381 ms |
72640 KB |
Output is correct |
35 |
Correct |
555 ms |
105156 KB |
Output is correct |
36 |
Correct |
578 ms |
101828 KB |
Output is correct |
37 |
Correct |
635 ms |
107844 KB |
Output is correct |
38 |
Correct |
1617 ms |
139272 KB |
Output is correct |
39 |
Correct |
6 ms |
1612 KB |
Output is correct |
40 |
Correct |
5 ms |
1356 KB |
Output is correct |
41 |
Correct |
5 ms |
1356 KB |
Output is correct |
42 |
Correct |
5 ms |
972 KB |
Output is correct |
43 |
Correct |
4 ms |
1316 KB |
Output is correct |
44 |
Correct |
6 ms |
1484 KB |
Output is correct |
45 |
Correct |
5 ms |
1356 KB |
Output is correct |
46 |
Correct |
4 ms |
1100 KB |
Output is correct |
47 |
Correct |
7 ms |
1740 KB |
Output is correct |
48 |
Correct |
7 ms |
1612 KB |
Output is correct |
49 |
Correct |
6 ms |
1612 KB |
Output is correct |
50 |
Correct |
5 ms |
1356 KB |
Output is correct |
51 |
Correct |
6 ms |
1404 KB |
Output is correct |
52 |
Correct |
6 ms |
1484 KB |
Output is correct |
53 |
Correct |
5 ms |
1228 KB |
Output is correct |
54 |
Correct |
5 ms |
1228 KB |
Output is correct |
55 |
Correct |
5 ms |
1264 KB |
Output is correct |
56 |
Correct |
6 ms |
1484 KB |
Output is correct |
57 |
Correct |
446 ms |
116192 KB |
Output is correct |
58 |
Correct |
371 ms |
89028 KB |
Output is correct |
59 |
Correct |
766 ms |
122564 KB |
Output is correct |
60 |
Correct |
372 ms |
73704 KB |
Output is correct |
61 |
Correct |
381 ms |
78912 KB |
Output is correct |
62 |
Correct |
425 ms |
87032 KB |
Output is correct |
63 |
Correct |
1040 ms |
132424 KB |
Output is correct |
64 |
Correct |
562 ms |
99404 KB |
Output is correct |
65 |
Correct |
827 ms |
133448 KB |
Output is correct |
66 |
Correct |
316 ms |
79676 KB |
Output is correct |
67 |
Correct |
1176 ms |
113816 KB |
Output is correct |
68 |
Correct |
484 ms |
78820 KB |
Output is correct |
69 |
Correct |
1205 ms |
104632 KB |
Output is correct |
70 |
Correct |
309 ms |
82888 KB |
Output is correct |
71 |
Correct |
700 ms |
132504 KB |
Output is correct |
72 |
Correct |
393 ms |
83668 KB |
Output is correct |
73 |
Correct |
518 ms |
109508 KB |
Output is correct |
74 |
Correct |
427 ms |
68036 KB |
Output is correct |
75 |
Correct |
811 ms |
112424 KB |
Output is correct |
76 |
Correct |
446 ms |
78212 KB |
Output is correct |
77 |
Correct |
516 ms |
104812 KB |
Output is correct |
78 |
Correct |
428 ms |
74548 KB |
Output is correct |
79 |
Correct |
569 ms |
96732 KB |
Output is correct |
80 |
Correct |
765 ms |
120948 KB |
Output is correct |
81 |
Correct |
300 ms |
79740 KB |
Output is correct |
82 |
Correct |
451 ms |
100956 KB |
Output is correct |
83 |
Correct |
350 ms |
67280 KB |
Output is correct |
84 |
Correct |
369 ms |
72900 KB |
Output is correct |
85 |
Correct |
331 ms |
68232 KB |
Output is correct |
86 |
Correct |
546 ms |
120644 KB |
Output is correct |
87 |
Correct |
411 ms |
68460 KB |
Output is correct |
88 |
Correct |
703 ms |
120816 KB |
Output is correct |
89 |
Correct |
621 ms |
97616 KB |
Output is correct |
90 |
Correct |
501 ms |
88444 KB |
Output is correct |
91 |
Correct |
1025 ms |
144384 KB |
Output is correct |
92 |
Correct |
1269 ms |
134208 KB |
Output is correct |
93 |
Correct |
1672 ms |
139244 KB |
Output is correct |
94 |
Correct |
1616 ms |
139264 KB |
Output is correct |
95 |
Correct |
652 ms |
118888 KB |
Output is correct |
96 |
Correct |
426 ms |
93380 KB |
Output is correct |
97 |
Correct |
696 ms |
127240 KB |
Output is correct |
98 |
Correct |
572 ms |
84696 KB |
Output is correct |
99 |
Correct |
577 ms |
96820 KB |
Output is correct |
100 |
Correct |
616 ms |
93612 KB |
Output is correct |