#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++){
if(pos == n - 1)break;
curr += prefp[mx[pos] + 1] - prefp[pos + 1];
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 |
908 KB |
Output is correct |
3 |
Correct |
6 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
4 ms |
724 KB |
Output is correct |
7 |
Correct |
5 ms |
856 KB |
Output is correct |
8 |
Correct |
6 ms |
1008 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
6 ms |
980 KB |
Output is correct |
11 |
Correct |
6 ms |
980 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
412 ms |
50748 KB |
Output is correct |
2 |
Correct |
280 ms |
32340 KB |
Output is correct |
3 |
Correct |
312 ms |
34860 KB |
Output is correct |
4 |
Correct |
302 ms |
37796 KB |
Output is correct |
5 |
Correct |
357 ms |
44292 KB |
Output is correct |
6 |
Correct |
495 ms |
58904 KB |
Output is correct |
7 |
Correct |
323 ms |
38960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
5 ms |
908 KB |
Output is correct |
3 |
Correct |
6 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
4 ms |
724 KB |
Output is correct |
7 |
Correct |
5 ms |
856 KB |
Output is correct |
8 |
Correct |
6 ms |
1008 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
6 ms |
980 KB |
Output is correct |
11 |
Correct |
6 ms |
980 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
412 ms |
50748 KB |
Output is correct |
14 |
Correct |
280 ms |
32340 KB |
Output is correct |
15 |
Correct |
312 ms |
34860 KB |
Output is correct |
16 |
Correct |
302 ms |
37796 KB |
Output is correct |
17 |
Correct |
357 ms |
44292 KB |
Output is correct |
18 |
Correct |
495 ms |
58904 KB |
Output is correct |
19 |
Correct |
323 ms |
38960 KB |
Output is correct |
20 |
Correct |
362 ms |
32368 KB |
Output is correct |
21 |
Correct |
420 ms |
48732 KB |
Output is correct |
22 |
Correct |
487 ms |
57624 KB |
Output is correct |
23 |
Correct |
460 ms |
56952 KB |
Output is correct |
24 |
Correct |
467 ms |
53604 KB |
Output is correct |
25 |
Correct |
489 ms |
53680 KB |
Output is correct |
26 |
Correct |
376 ms |
40168 KB |
Output is correct |
27 |
Correct |
470 ms |
51352 KB |
Output is correct |
28 |
Correct |
453 ms |
50716 KB |
Output is correct |
29 |
Correct |
599 ms |
66084 KB |
Output is correct |
30 |
Correct |
489 ms |
54080 KB |
Output is correct |
31 |
Correct |
413 ms |
47376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2080 ms |
47256 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 |
908 KB |
Output is correct |
3 |
Correct |
6 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
4 ms |
724 KB |
Output is correct |
7 |
Correct |
5 ms |
856 KB |
Output is correct |
8 |
Correct |
6 ms |
1008 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
6 ms |
980 KB |
Output is correct |
11 |
Correct |
6 ms |
980 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
7 ms |
980 KB |
Output is correct |
14 |
Correct |
7 ms |
852 KB |
Output is correct |
15 |
Incorrect |
8 ms |
852 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 |
908 KB |
Output is correct |
3 |
Correct |
6 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
4 ms |
724 KB |
Output is correct |
7 |
Correct |
5 ms |
856 KB |
Output is correct |
8 |
Correct |
6 ms |
1008 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
6 ms |
980 KB |
Output is correct |
11 |
Correct |
6 ms |
980 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
412 ms |
50748 KB |
Output is correct |
14 |
Correct |
280 ms |
32340 KB |
Output is correct |
15 |
Correct |
312 ms |
34860 KB |
Output is correct |
16 |
Correct |
302 ms |
37796 KB |
Output is correct |
17 |
Correct |
357 ms |
44292 KB |
Output is correct |
18 |
Correct |
495 ms |
58904 KB |
Output is correct |
19 |
Correct |
323 ms |
38960 KB |
Output is correct |
20 |
Correct |
362 ms |
32368 KB |
Output is correct |
21 |
Correct |
420 ms |
48732 KB |
Output is correct |
22 |
Correct |
487 ms |
57624 KB |
Output is correct |
23 |
Correct |
460 ms |
56952 KB |
Output is correct |
24 |
Correct |
467 ms |
53604 KB |
Output is correct |
25 |
Correct |
489 ms |
53680 KB |
Output is correct |
26 |
Correct |
376 ms |
40168 KB |
Output is correct |
27 |
Correct |
470 ms |
51352 KB |
Output is correct |
28 |
Correct |
453 ms |
50716 KB |
Output is correct |
29 |
Correct |
599 ms |
66084 KB |
Output is correct |
30 |
Correct |
489 ms |
54080 KB |
Output is correct |
31 |
Correct |
413 ms |
47376 KB |
Output is correct |
32 |
Correct |
595 ms |
63256 KB |
Output is correct |
33 |
Correct |
442 ms |
48540 KB |
Output is correct |
34 |
Incorrect |
701 ms |
66792 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 |
908 KB |
Output is correct |
3 |
Correct |
6 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
4 ms |
724 KB |
Output is correct |
7 |
Correct |
5 ms |
856 KB |
Output is correct |
8 |
Correct |
6 ms |
1008 KB |
Output is correct |
9 |
Correct |
4 ms |
724 KB |
Output is correct |
10 |
Correct |
6 ms |
980 KB |
Output is correct |
11 |
Correct |
6 ms |
980 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
412 ms |
50748 KB |
Output is correct |
14 |
Correct |
280 ms |
32340 KB |
Output is correct |
15 |
Correct |
312 ms |
34860 KB |
Output is correct |
16 |
Correct |
302 ms |
37796 KB |
Output is correct |
17 |
Correct |
357 ms |
44292 KB |
Output is correct |
18 |
Correct |
495 ms |
58904 KB |
Output is correct |
19 |
Correct |
323 ms |
38960 KB |
Output is correct |
20 |
Correct |
362 ms |
32368 KB |
Output is correct |
21 |
Correct |
420 ms |
48732 KB |
Output is correct |
22 |
Correct |
487 ms |
57624 KB |
Output is correct |
23 |
Correct |
460 ms |
56952 KB |
Output is correct |
24 |
Correct |
467 ms |
53604 KB |
Output is correct |
25 |
Correct |
489 ms |
53680 KB |
Output is correct |
26 |
Correct |
376 ms |
40168 KB |
Output is correct |
27 |
Correct |
470 ms |
51352 KB |
Output is correct |
28 |
Correct |
453 ms |
50716 KB |
Output is correct |
29 |
Correct |
599 ms |
66084 KB |
Output is correct |
30 |
Correct |
489 ms |
54080 KB |
Output is correct |
31 |
Correct |
413 ms |
47376 KB |
Output is correct |
32 |
Execution timed out |
2080 ms |
47256 KB |
Time limit exceeded |
33 |
Halted |
0 ms |
0 KB |
- |