#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
#define F first
#define S second
long long dpL[10000001] , dpR[10000001];
long long delivery(int N, int K, int L, int p[]) {
#define int long long
int ans = (int) 1e18;
int k = K;
int n = N;
int l = L;
for(int i = 0 ; i < N ;i ++){
dpL[i] = 2*p[i];
if(i >= K) dpL[i] = dpL[i-k] + 2*p[i]; // pick the last block and then solve for [0 , i-k]
}
for(int j = N - 1 ; j >= 0 ; j--){
int u = j + K ;
dpR[j] = 2*(L - p[j]);
if(u <= n - 1) dpR[j] = dpR[u] + 2*(L - p[j]);
}
#define pii pair<long long, long long>
deque<pii> dq;
int left = 1;
for(int i = 0 ; i < N - 1; i ++){
while(dq.size() && dq.front().second <= i) dq.pop_front();
left = max(left, i + 1);
while(left < N && k >= (left - i - 1)){
while(dq.size() && dq.back().first >= dpR[left]) dq.pop_back();
dq.push_back(pii(dpR[left] , left));
left++;
}
ans = min(ans , dpL[i] + dpR[i+1]);
ans = min(ans , dpL[i] + dq.front().F + L);
}
for(int i = 0 ; i < N ; i ++){
int X = n - i - 1;
if(X <= k){
ans = min(ans , dpL[i] + L);
}
int Y = i;
if(Y <= k) ans = min(ans , dpR[i] + L);
}
ans = min(ans , dpL[N - 1]);
ans = min(ans , dpR[0]);
if(K == N){
ans = min(ans ,l);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
404 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
252 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
404 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
252 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
256 KB |
Output is correct |
18 |
Correct |
2 ms |
256 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
256 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
380 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
404 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
252 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
256 KB |
Output is correct |
18 |
Correct |
2 ms |
256 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
256 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
380 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
57 ms |
19836 KB |
Output is correct |
34 |
Correct |
39 ms |
19960 KB |
Output is correct |
35 |
Correct |
47 ms |
19988 KB |
Output is correct |
36 |
Correct |
60 ms |
19880 KB |
Output is correct |
37 |
Correct |
61 ms |
19968 KB |
Output is correct |
38 |
Correct |
60 ms |
19948 KB |
Output is correct |
39 |
Correct |
57 ms |
19884 KB |
Output is correct |
40 |
Correct |
50 ms |
19836 KB |
Output is correct |
41 |
Correct |
73 ms |
19832 KB |
Output is correct |
42 |
Correct |
46 ms |
19832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
404 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
252 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
256 KB |
Output is correct |
18 |
Correct |
2 ms |
256 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
256 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
380 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
57 ms |
19836 KB |
Output is correct |
34 |
Correct |
39 ms |
19960 KB |
Output is correct |
35 |
Correct |
47 ms |
19988 KB |
Output is correct |
36 |
Correct |
60 ms |
19880 KB |
Output is correct |
37 |
Correct |
61 ms |
19968 KB |
Output is correct |
38 |
Correct |
60 ms |
19948 KB |
Output is correct |
39 |
Correct |
57 ms |
19884 KB |
Output is correct |
40 |
Correct |
50 ms |
19836 KB |
Output is correct |
41 |
Correct |
73 ms |
19832 KB |
Output is correct |
42 |
Correct |
46 ms |
19832 KB |
Output is correct |
43 |
Correct |
575 ms |
196068 KB |
Output is correct |
44 |
Correct |
322 ms |
196064 KB |
Output is correct |
45 |
Correct |
351 ms |
195960 KB |
Output is correct |
46 |
Correct |
586 ms |
195960 KB |
Output is correct |
47 |
Correct |
588 ms |
196068 KB |
Output is correct |
48 |
Correct |
579 ms |
195960 KB |
Output is correct |
49 |
Correct |
536 ms |
196068 KB |
Output is correct |
50 |
Correct |
394 ms |
196012 KB |
Output is correct |
51 |
Correct |
600 ms |
196112 KB |
Output is correct |
52 |
Correct |
402 ms |
196068 KB |
Output is correct |