#include<bits/stdc++.h>
using namespace std;
#include "boxes.h"
#define lint long long
#define mx 10000007
#define mp make_pair
#define st first
#define nd second
pair<lint,int> Q[mx],QQ[mx];
lint i,dp,t,l,r,ll,rr;
lint delivery(int n, int k, int L, int *p){
Q[r++] = mp(0,-1);
QQ[rr++] = mp(min(L,2*(L-p[0])),-1);
for(i=0;i<n;i++){
if(Q[l].nd == i-k-1) l++;
if(QQ[ll].nd == i-k-1) ll++;
dp = Q[l].st + min(p[i]*2 , L);
dp = min(dp , QQ[ll].st);
if(i == n-1) return dp;
for(; r > l && Q[r-1].st > dp ;) r--;
t = dp + min(L , 2*(L-p[i+1]));
for(; rr > ll && QQ[rr-1].st > t ;) rr--;
Q[r++] = mp(dp,i);
QQ[rr++] = mp(t,i);
}
return dp;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
312 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 |
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 |
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 |
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 |
252 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 |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
312 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 |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 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 |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
252 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 |
348 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
348 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 |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
312 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 |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 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 |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
252 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 |
348 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
348 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 |
62 ms |
35068 KB |
Output is correct |
34 |
Correct |
36 ms |
35472 KB |
Output is correct |
35 |
Correct |
39 ms |
35576 KB |
Output is correct |
36 |
Correct |
60 ms |
35508 KB |
Output is correct |
37 |
Correct |
64 ms |
35500 KB |
Output is correct |
38 |
Correct |
63 ms |
35556 KB |
Output is correct |
39 |
Correct |
55 ms |
27828 KB |
Output is correct |
40 |
Correct |
39 ms |
33172 KB |
Output is correct |
41 |
Correct |
57 ms |
19904 KB |
Output is correct |
42 |
Correct |
41 ms |
33784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
312 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 |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 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 |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
252 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 |
348 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
348 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 |
62 ms |
35068 KB |
Output is correct |
34 |
Correct |
36 ms |
35472 KB |
Output is correct |
35 |
Correct |
39 ms |
35576 KB |
Output is correct |
36 |
Correct |
60 ms |
35508 KB |
Output is correct |
37 |
Correct |
64 ms |
35500 KB |
Output is correct |
38 |
Correct |
63 ms |
35556 KB |
Output is correct |
39 |
Correct |
55 ms |
27828 KB |
Output is correct |
40 |
Correct |
39 ms |
33172 KB |
Output is correct |
41 |
Correct |
57 ms |
19904 KB |
Output is correct |
42 |
Correct |
41 ms |
33784 KB |
Output is correct |
43 |
Correct |
646 ms |
319808 KB |
Output is correct |
44 |
Correct |
386 ms |
352532 KB |
Output is correct |
45 |
Correct |
401 ms |
352608 KB |
Output is correct |
46 |
Correct |
617 ms |
352584 KB |
Output is correct |
47 |
Correct |
638 ms |
348560 KB |
Output is correct |
48 |
Correct |
629 ms |
352520 KB |
Output is correct |
49 |
Correct |
555 ms |
274332 KB |
Output is correct |
50 |
Correct |
417 ms |
274276 KB |
Output is correct |
51 |
Correct |
535 ms |
196100 KB |
Output is correct |
52 |
Correct |
351 ms |
205432 KB |
Output is correct |