#include <bits/stdc++.h>
#include <boxes.h>
using namespace std;
typedef long long ll;
struct st{
ll w; int i;
st(){}
st(ll W, int I) : w(W), i(I) {}
};
ll delivery(int n, int k, int l, int p[]){
vector<int> t(n), d1(n+1), d2(n+1);
for(int i = 0; i < n; ++i) t[i] = p[i];
d1[0] = t[0], d2[n] = l-t[n-1];
for(int i = 1; i < n; ++i) d1[i] = t[i]-t[i-1];
for(int i = n-1; i; --i) d2[i] = d1[i] + d2[i+1];
for(int i = 1; i < n; ++i) d1[i] += d1[i-1];
for(int i = 0; i < n; ++i) d2[i] = d2[i+1];
vector<ll> dp1(n), dp2(n);
deque<st> dq; dq.emplace_back(0, -1);
for(int i = 0; i < n; ++i){
if(!dq.empty() && i-dq.front().i > k) dq.pop_front();
dp1[i] = dq.front().w+ll(d1[i]+min(d1[i], l-d1[i]));
while(!dq.empty() && dq.back().w >= dp1[i]) dq.pop_back();
dq.emplace_back(dp1[i], i);
} while(!dq.empty()) dq.pop_back();
dq.emplace_back(0, n);
for(int i = n-1; ~i; --i){
if(!dq.empty() && dq.front().i-i > k) dq.pop_front();
dp2[i] = dq.front().w+ll(d2[i]+min(d2[i], l-d2[i]));
while(!dq.empty() && dq.back().w >= dp2[i]) dq.pop_back();
dq.emplace_back(dp2[i], i);
} ll wynik = min(dp1[n-1], dp2[0]);
for(int i = 0; i < n-1; ++i) wynik = min(wynik, dp1[i]+dp2[i+1]);
return wynik;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
308 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
300 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
300 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
308 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
308 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
308 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
300 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
308 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
0 ms |
312 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
0 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
300 KB |
Output is correct |
31 |
Correct |
0 ms |
340 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
300 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
308 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
308 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
308 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
300 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
308 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
0 ms |
312 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
0 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
300 KB |
Output is correct |
31 |
Correct |
0 ms |
340 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
64 ms |
41272 KB |
Output is correct |
34 |
Correct |
38 ms |
33572 KB |
Output is correct |
35 |
Correct |
39 ms |
33980 KB |
Output is correct |
36 |
Correct |
66 ms |
41376 KB |
Output is correct |
37 |
Correct |
65 ms |
41336 KB |
Output is correct |
38 |
Correct |
70 ms |
41316 KB |
Output is correct |
39 |
Correct |
58 ms |
39812 KB |
Output is correct |
40 |
Correct |
47 ms |
35220 KB |
Output is correct |
41 |
Correct |
71 ms |
41408 KB |
Output is correct |
42 |
Correct |
45 ms |
35456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
300 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
308 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
308 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
308 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
300 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
308 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
0 ms |
312 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
0 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
300 KB |
Output is correct |
31 |
Correct |
0 ms |
340 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
64 ms |
41272 KB |
Output is correct |
34 |
Correct |
38 ms |
33572 KB |
Output is correct |
35 |
Correct |
39 ms |
33980 KB |
Output is correct |
36 |
Correct |
66 ms |
41376 KB |
Output is correct |
37 |
Correct |
65 ms |
41336 KB |
Output is correct |
38 |
Correct |
70 ms |
41316 KB |
Output is correct |
39 |
Correct |
58 ms |
39812 KB |
Output is correct |
40 |
Correct |
47 ms |
35220 KB |
Output is correct |
41 |
Correct |
71 ms |
41408 KB |
Output is correct |
42 |
Correct |
45 ms |
35456 KB |
Output is correct |
43 |
Correct |
649 ms |
426504 KB |
Output is correct |
44 |
Correct |
363 ms |
332924 KB |
Output is correct |
45 |
Correct |
386 ms |
340684 KB |
Output is correct |
46 |
Correct |
654 ms |
411040 KB |
Output is correct |
47 |
Correct |
662 ms |
411056 KB |
Output is correct |
48 |
Correct |
670 ms |
410964 KB |
Output is correct |
49 |
Correct |
683 ms |
406952 KB |
Output is correct |
50 |
Correct |
432 ms |
349876 KB |
Output is correct |
51 |
Correct |
696 ms |
415732 KB |
Output is correct |
52 |
Correct |
446 ms |
352460 KB |
Output is correct |