#include <bits/stdc++.h>
using namespace std;
#define LIFESUCKS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#define ar array
#include<cstdio>
#define vt vector
#include<fstream>
//ifstream fin("QUANMA.INP");
//ofstream fout("QUANMA.OUT");
#include<fstream>
#define pb push_back
#define all(c) (c).begin(), (c).end()
//#define length(x) (int)(x).size()
#define fi first
#define se second
#define vt vector
const int mxn = 1e6;
ll d[mxn + 3];
ll p[mxn + 3];
int main()
{
ll n, s, k; cin >> n >> s >> k;
ll crpos = 0;
vt<ll>prefd; prefd.pb(0);
vt<ll>prefp; prefp.pb(0);
for(int i = 0; i < n - 1; i++){
cin >> d[i];
prefd.pb(prefd[i] + d[i]);
}
for(int i = 0; i < n; i++){
cin >> p[i];
prefp.pb(prefp[i] + p[i]);
}
ll left[n], right[n];
ll id[n];
left[0] = 0;
for(int i = 1; i < n; i++){
int l = 0, r = i - 1, ans = i;
while(l <= r){
//cout << "aa";
int mid = (l + r) / 2;
if(prefd[i] - prefd[mid] <= k){
ans = mid; r = mid - 1;
}else{
l = mid + 1;
}
}
left[i] = ans;
}
right[n - 1] = n - 1;
for(int i = n - 2; i >= 0; i--){
int l = i + 1, r = n - 1, ans = i;
while(l <= r){
int mid = (l + r) / 2;
if(prefd[mid] - prefd[i] <= k){
ans = mid; l = mid + 1;
}else{
r = mid - 1;
}
}
right[i] = ans;
}
int cr = n - 1;
int mx[n];
for(int i = n - 1; i >= 0; i--){
while(cr >= left[i]){
mx[cr] = right[i];
id[cr] = i;
cr--;
}
}
ll ans = 0, idd = -1;
for(int i = 0; i < n; i++){
ll curr = p[i], pos = i;
for(int j = 0; j < s; j++){
curr += prefp[mx[pos] + 1] - prefp[pos + 1];
if(pos == n - 1)break;
pos = mx[pos];
}
if(curr > ans){
idd = i;
ans = curr;
}
}
vt<int>anss; anss.pb(id[idd]);
int pos = idd;
for(int i = 0; i < s - 1; i++){
if(pos == n - 1)break;
pos = mx[pos] + 1;
if(pos == n)break;
anss.pb(id[pos]);
}
cout << anss.size() << "\n";
for(auto i: anss)cout << i + 1 << " ";
return 0;
}
Compilation message
SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:25:8: warning: unused variable 'crpos' [-Wunused-variable]
25 | ll crpos = 0;
| ^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
5 ms |
852 KB |
Output is correct |
3 |
Correct |
6 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
524 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
5 ms |
724 KB |
Output is correct |
7 |
Correct |
5 ms |
896 KB |
Output is correct |
8 |
Correct |
6 ms |
980 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
6 ms |
968 KB |
Output is correct |
11 |
Correct |
6 ms |
980 KB |
Output is correct |
12 |
Correct |
3 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
406 ms |
50704 KB |
Output is correct |
2 |
Correct |
282 ms |
32460 KB |
Output is correct |
3 |
Correct |
313 ms |
34712 KB |
Output is correct |
4 |
Correct |
302 ms |
37780 KB |
Output is correct |
5 |
Correct |
347 ms |
44384 KB |
Output is correct |
6 |
Correct |
471 ms |
58824 KB |
Output is correct |
7 |
Correct |
310 ms |
39016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
5 ms |
852 KB |
Output is correct |
3 |
Correct |
6 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
524 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
5 ms |
724 KB |
Output is correct |
7 |
Correct |
5 ms |
896 KB |
Output is correct |
8 |
Correct |
6 ms |
980 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
6 ms |
968 KB |
Output is correct |
11 |
Correct |
6 ms |
980 KB |
Output is correct |
12 |
Correct |
3 ms |
468 KB |
Output is correct |
13 |
Correct |
406 ms |
50704 KB |
Output is correct |
14 |
Correct |
282 ms |
32460 KB |
Output is correct |
15 |
Correct |
313 ms |
34712 KB |
Output is correct |
16 |
Correct |
302 ms |
37780 KB |
Output is correct |
17 |
Correct |
347 ms |
44384 KB |
Output is correct |
18 |
Correct |
471 ms |
58824 KB |
Output is correct |
19 |
Correct |
310 ms |
39016 KB |
Output is correct |
20 |
Correct |
357 ms |
32312 KB |
Output is correct |
21 |
Correct |
449 ms |
39496 KB |
Output is correct |
22 |
Correct |
496 ms |
46920 KB |
Output is correct |
23 |
Correct |
432 ms |
48440 KB |
Output is correct |
24 |
Correct |
458 ms |
43624 KB |
Output is correct |
25 |
Correct |
472 ms |
43692 KB |
Output is correct |
26 |
Correct |
348 ms |
32644 KB |
Output is correct |
27 |
Correct |
451 ms |
41780 KB |
Output is correct |
28 |
Correct |
458 ms |
41360 KB |
Output is correct |
29 |
Correct |
578 ms |
53904 KB |
Output is correct |
30 |
Correct |
474 ms |
44028 KB |
Output is correct |
31 |
Correct |
394 ms |
38636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2064 ms |
47132 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
5 ms |
852 KB |
Output is correct |
3 |
Correct |
6 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
524 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
5 ms |
724 KB |
Output is correct |
7 |
Correct |
5 ms |
896 KB |
Output is correct |
8 |
Correct |
6 ms |
980 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
6 ms |
968 KB |
Output is correct |
11 |
Correct |
6 ms |
980 KB |
Output is correct |
12 |
Correct |
3 ms |
468 KB |
Output is correct |
13 |
Correct |
6 ms |
1004 KB |
Output is correct |
14 |
Correct |
9 ms |
724 KB |
Output is correct |
15 |
Incorrect |
7 ms |
724 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
5 ms |
852 KB |
Output is correct |
3 |
Correct |
6 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
524 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
5 ms |
724 KB |
Output is correct |
7 |
Correct |
5 ms |
896 KB |
Output is correct |
8 |
Correct |
6 ms |
980 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
6 ms |
968 KB |
Output is correct |
11 |
Correct |
6 ms |
980 KB |
Output is correct |
12 |
Correct |
3 ms |
468 KB |
Output is correct |
13 |
Correct |
406 ms |
50704 KB |
Output is correct |
14 |
Correct |
282 ms |
32460 KB |
Output is correct |
15 |
Correct |
313 ms |
34712 KB |
Output is correct |
16 |
Correct |
302 ms |
37780 KB |
Output is correct |
17 |
Correct |
347 ms |
44384 KB |
Output is correct |
18 |
Correct |
471 ms |
58824 KB |
Output is correct |
19 |
Correct |
310 ms |
39016 KB |
Output is correct |
20 |
Correct |
357 ms |
32312 KB |
Output is correct |
21 |
Correct |
449 ms |
39496 KB |
Output is correct |
22 |
Correct |
496 ms |
46920 KB |
Output is correct |
23 |
Correct |
432 ms |
48440 KB |
Output is correct |
24 |
Correct |
458 ms |
43624 KB |
Output is correct |
25 |
Correct |
472 ms |
43692 KB |
Output is correct |
26 |
Correct |
348 ms |
32644 KB |
Output is correct |
27 |
Correct |
451 ms |
41780 KB |
Output is correct |
28 |
Correct |
458 ms |
41360 KB |
Output is correct |
29 |
Correct |
578 ms |
53904 KB |
Output is correct |
30 |
Correct |
474 ms |
44028 KB |
Output is correct |
31 |
Correct |
394 ms |
38636 KB |
Output is correct |
32 |
Correct |
549 ms |
51632 KB |
Output is correct |
33 |
Correct |
438 ms |
39552 KB |
Output is correct |
34 |
Incorrect |
667 ms |
54300 KB |
Output isn't correct |
35 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
5 ms |
852 KB |
Output is correct |
3 |
Correct |
6 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
524 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
5 ms |
724 KB |
Output is correct |
7 |
Correct |
5 ms |
896 KB |
Output is correct |
8 |
Correct |
6 ms |
980 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
6 ms |
968 KB |
Output is correct |
11 |
Correct |
6 ms |
980 KB |
Output is correct |
12 |
Correct |
3 ms |
468 KB |
Output is correct |
13 |
Correct |
406 ms |
50704 KB |
Output is correct |
14 |
Correct |
282 ms |
32460 KB |
Output is correct |
15 |
Correct |
313 ms |
34712 KB |
Output is correct |
16 |
Correct |
302 ms |
37780 KB |
Output is correct |
17 |
Correct |
347 ms |
44384 KB |
Output is correct |
18 |
Correct |
471 ms |
58824 KB |
Output is correct |
19 |
Correct |
310 ms |
39016 KB |
Output is correct |
20 |
Correct |
357 ms |
32312 KB |
Output is correct |
21 |
Correct |
449 ms |
39496 KB |
Output is correct |
22 |
Correct |
496 ms |
46920 KB |
Output is correct |
23 |
Correct |
432 ms |
48440 KB |
Output is correct |
24 |
Correct |
458 ms |
43624 KB |
Output is correct |
25 |
Correct |
472 ms |
43692 KB |
Output is correct |
26 |
Correct |
348 ms |
32644 KB |
Output is correct |
27 |
Correct |
451 ms |
41780 KB |
Output is correct |
28 |
Correct |
458 ms |
41360 KB |
Output is correct |
29 |
Correct |
578 ms |
53904 KB |
Output is correct |
30 |
Correct |
474 ms |
44028 KB |
Output is correct |
31 |
Correct |
394 ms |
38636 KB |
Output is correct |
32 |
Execution timed out |
2064 ms |
47132 KB |
Time limit exceeded |
33 |
Halted |
0 ms |
0 KB |
- |