#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
const int LG = 20, MAX_N = 1e6;
int p[LG][1 + MAX_N];
int nxt[1 + MAX_N];
ll sumd[1 + MAX_N], sumv[1 + MAX_N];
int n;
void lift () {
for (int k = 1; k < LG; k++)
for (int i = 1; i <= n; i++)
p[k][i] = p[k - 1][p[k - 1][i]];
}
int main () {
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
int s, k;
cin >> n >> s >> k; s--;
for (int i = 2; i <= n; i++) {
cin >> sumd[i];
sumd[i] += sumd[i - 1];
}
for (int i = 1; i <= n; i++) {
cin >> sumv[i];
sumv[i] += sumv[i - 1];
}
int a = 1, b = 1;
for (int i = 1; i <= n; i++) {
while (a <= n && sumd[a] - sumd[i] <= k)
a++;
while (b <= n && sumd[b] - sumd[a] <= k)
b++;
nxt[i] = a - 1;
p[0][i] = b - 1;
}
lift ();
int bestsum = 0, bestid = 0, j = 1;
for (int i = 1; i <= n; i++) {
while (sumd[i] - sumd[j] > k)
j++;
int cur = i;
for (int bit = LG - 1; bit >= 0; bit--)
if ((1 << bit) & s)
cur = p[bit][cur];
cur = nxt[cur];
if (bestsum < sumv[cur] - sumv[j - 1]) {
bestsum = sumv[cur] - sumv[j - 1];
bestid = i;
}
}
vector <int> sol;
while (bestid && s >= 0) {
sol.pb (bestid);
bestid = p[0][bestid];
s--;
}
cout << sol.size () << "\n";
for (int x : sol)
cout << x << " ";
cout << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
1408 KB |
Output is correct |
3 |
Correct |
4 ms |
1644 KB |
Output is correct |
4 |
Correct |
2 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
3 ms |
1388 KB |
Output is correct |
7 |
Correct |
3 ms |
1516 KB |
Output is correct |
8 |
Correct |
4 ms |
1644 KB |
Output is correct |
9 |
Correct |
3 ms |
1260 KB |
Output is correct |
10 |
Correct |
3 ms |
1516 KB |
Output is correct |
11 |
Correct |
4 ms |
1644 KB |
Output is correct |
12 |
Correct |
2 ms |
1004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
103 ms |
84332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
1408 KB |
Output is correct |
3 |
Correct |
4 ms |
1644 KB |
Output is correct |
4 |
Correct |
2 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
3 ms |
1388 KB |
Output is correct |
7 |
Correct |
3 ms |
1516 KB |
Output is correct |
8 |
Correct |
4 ms |
1644 KB |
Output is correct |
9 |
Correct |
3 ms |
1260 KB |
Output is correct |
10 |
Correct |
3 ms |
1516 KB |
Output is correct |
11 |
Correct |
4 ms |
1644 KB |
Output is correct |
12 |
Correct |
2 ms |
1004 KB |
Output is correct |
13 |
Incorrect |
103 ms |
84332 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
255 ms |
85536 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
1408 KB |
Output is correct |
3 |
Correct |
4 ms |
1644 KB |
Output is correct |
4 |
Correct |
2 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
3 ms |
1388 KB |
Output is correct |
7 |
Correct |
3 ms |
1516 KB |
Output is correct |
8 |
Correct |
4 ms |
1644 KB |
Output is correct |
9 |
Correct |
3 ms |
1260 KB |
Output is correct |
10 |
Correct |
3 ms |
1516 KB |
Output is correct |
11 |
Correct |
4 ms |
1644 KB |
Output is correct |
12 |
Correct |
2 ms |
1004 KB |
Output is correct |
13 |
Incorrect |
2 ms |
1516 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
1408 KB |
Output is correct |
3 |
Correct |
4 ms |
1644 KB |
Output is correct |
4 |
Correct |
2 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
3 ms |
1388 KB |
Output is correct |
7 |
Correct |
3 ms |
1516 KB |
Output is correct |
8 |
Correct |
4 ms |
1644 KB |
Output is correct |
9 |
Correct |
3 ms |
1260 KB |
Output is correct |
10 |
Correct |
3 ms |
1516 KB |
Output is correct |
11 |
Correct |
4 ms |
1644 KB |
Output is correct |
12 |
Correct |
2 ms |
1004 KB |
Output is correct |
13 |
Incorrect |
103 ms |
84332 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
504 KB |
Output is correct |
2 |
Correct |
3 ms |
1408 KB |
Output is correct |
3 |
Correct |
4 ms |
1644 KB |
Output is correct |
4 |
Correct |
2 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
3 ms |
1388 KB |
Output is correct |
7 |
Correct |
3 ms |
1516 KB |
Output is correct |
8 |
Correct |
4 ms |
1644 KB |
Output is correct |
9 |
Correct |
3 ms |
1260 KB |
Output is correct |
10 |
Correct |
3 ms |
1516 KB |
Output is correct |
11 |
Correct |
4 ms |
1644 KB |
Output is correct |
12 |
Correct |
2 ms |
1004 KB |
Output is correct |
13 |
Incorrect |
103 ms |
84332 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |