#include <algorithm>
#include "boxes.h"
using namespace std;
typedef long long llong;
const int maxN = 10000001;
int n;
llong dppref_[maxN], dpsuff_[maxN];
llong mn[maxN];
inline llong dppref(int i) { return (i < 0) ? 0 : dppref_[i]; }
inline llong dpsuff(int i) { return (i >= n) ? 0 : dpsuff_[i]; }
long long delivery(int n_, int k, int len, int pos[])
{
n = n_;
for (int i = 0; i < n; ++i)
dppref_[i] = 2LL * pos[i] + dppref(i - k);
for (int i = n - 1; i >= 0; --i)
dpsuff_[i] = 2LL * (len - pos[i]) + dpsuff(i + k);
llong ans = dpsuff(0);
const llong inf = 50000000000000000LL;
fill(mn, mn + maxN, inf);
for (int i = n - 1; i >= 0; --i)
{
ans = min(ans, dppref(i) + dpsuff(i + 1));
ans = min(ans, mn[i % k] + dppref(i - 1) - (i / k) * (llong)len);
++i;
mn[i % k] = min(mn[i % k], (i / k) * (llong)len + dpsuff(i));
--i;
}
/*for (int i = 0; i < n; ++i)
{
ans = min(ans, dppref(i) + dpsuff(i + 1));
for (int j = i + 2; j <= n; ++j)
{
if (i % k != j % k)
continue;
llong curans = j / k - i / k;
curans *= len;
curans += dppref(i - 1) + dpsuff(j);
ans = min(ans, curans);
}
}*/
return ans;
}
/*
3 2 8
1 2 5
10
*/
/*
3 2 100
10 47 60
120
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
78584 KB |
Output is correct |
2 |
Correct |
43 ms |
78584 KB |
Output is correct |
3 |
Correct |
42 ms |
78584 KB |
Output is correct |
4 |
Correct |
42 ms |
78592 KB |
Output is correct |
5 |
Correct |
43 ms |
78584 KB |
Output is correct |
6 |
Correct |
42 ms |
78584 KB |
Output is correct |
7 |
Correct |
49 ms |
78584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
78584 KB |
Output is correct |
2 |
Correct |
41 ms |
78584 KB |
Output is correct |
3 |
Correct |
42 ms |
78584 KB |
Output is correct |
4 |
Correct |
43 ms |
78584 KB |
Output is correct |
5 |
Correct |
43 ms |
78592 KB |
Output is correct |
6 |
Correct |
43 ms |
78584 KB |
Output is correct |
7 |
Correct |
43 ms |
78584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
78584 KB |
Output is correct |
2 |
Correct |
42 ms |
78584 KB |
Output is correct |
3 |
Correct |
43 ms |
78584 KB |
Output is correct |
4 |
Correct |
43 ms |
78592 KB |
Output is correct |
5 |
Correct |
44 ms |
78588 KB |
Output is correct |
6 |
Correct |
48 ms |
78712 KB |
Output is correct |
7 |
Correct |
42 ms |
78584 KB |
Output is correct |
8 |
Correct |
42 ms |
78592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
78584 KB |
Output is correct |
2 |
Correct |
43 ms |
78584 KB |
Output is correct |
3 |
Correct |
42 ms |
78584 KB |
Output is correct |
4 |
Correct |
42 ms |
78592 KB |
Output is correct |
5 |
Correct |
43 ms |
78584 KB |
Output is correct |
6 |
Correct |
42 ms |
78584 KB |
Output is correct |
7 |
Correct |
49 ms |
78584 KB |
Output is correct |
8 |
Correct |
45 ms |
78584 KB |
Output is correct |
9 |
Correct |
41 ms |
78584 KB |
Output is correct |
10 |
Correct |
42 ms |
78584 KB |
Output is correct |
11 |
Correct |
43 ms |
78584 KB |
Output is correct |
12 |
Correct |
43 ms |
78592 KB |
Output is correct |
13 |
Correct |
43 ms |
78584 KB |
Output is correct |
14 |
Correct |
43 ms |
78584 KB |
Output is correct |
15 |
Correct |
43 ms |
78584 KB |
Output is correct |
16 |
Correct |
42 ms |
78584 KB |
Output is correct |
17 |
Correct |
43 ms |
78584 KB |
Output is correct |
18 |
Correct |
43 ms |
78592 KB |
Output is correct |
19 |
Correct |
44 ms |
78588 KB |
Output is correct |
20 |
Correct |
48 ms |
78712 KB |
Output is correct |
21 |
Correct |
42 ms |
78584 KB |
Output is correct |
22 |
Correct |
42 ms |
78592 KB |
Output is correct |
23 |
Correct |
42 ms |
78584 KB |
Output is correct |
24 |
Correct |
42 ms |
78584 KB |
Output is correct |
25 |
Correct |
42 ms |
78584 KB |
Output is correct |
26 |
Correct |
42 ms |
78584 KB |
Output is correct |
27 |
Correct |
42 ms |
78584 KB |
Output is correct |
28 |
Correct |
42 ms |
78584 KB |
Output is correct |
29 |
Correct |
43 ms |
78592 KB |
Output is correct |
30 |
Correct |
43 ms |
78584 KB |
Output is correct |
31 |
Correct |
42 ms |
78592 KB |
Output is correct |
32 |
Correct |
42 ms |
78592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
78584 KB |
Output is correct |
2 |
Correct |
43 ms |
78584 KB |
Output is correct |
3 |
Correct |
42 ms |
78584 KB |
Output is correct |
4 |
Correct |
42 ms |
78592 KB |
Output is correct |
5 |
Correct |
43 ms |
78584 KB |
Output is correct |
6 |
Correct |
42 ms |
78584 KB |
Output is correct |
7 |
Correct |
49 ms |
78584 KB |
Output is correct |
8 |
Correct |
45 ms |
78584 KB |
Output is correct |
9 |
Correct |
41 ms |
78584 KB |
Output is correct |
10 |
Correct |
42 ms |
78584 KB |
Output is correct |
11 |
Correct |
43 ms |
78584 KB |
Output is correct |
12 |
Correct |
43 ms |
78592 KB |
Output is correct |
13 |
Correct |
43 ms |
78584 KB |
Output is correct |
14 |
Correct |
43 ms |
78584 KB |
Output is correct |
15 |
Correct |
43 ms |
78584 KB |
Output is correct |
16 |
Correct |
42 ms |
78584 KB |
Output is correct |
17 |
Correct |
43 ms |
78584 KB |
Output is correct |
18 |
Correct |
43 ms |
78592 KB |
Output is correct |
19 |
Correct |
44 ms |
78588 KB |
Output is correct |
20 |
Correct |
48 ms |
78712 KB |
Output is correct |
21 |
Correct |
42 ms |
78584 KB |
Output is correct |
22 |
Correct |
42 ms |
78592 KB |
Output is correct |
23 |
Correct |
42 ms |
78584 KB |
Output is correct |
24 |
Correct |
42 ms |
78584 KB |
Output is correct |
25 |
Correct |
42 ms |
78584 KB |
Output is correct |
26 |
Correct |
42 ms |
78584 KB |
Output is correct |
27 |
Correct |
42 ms |
78584 KB |
Output is correct |
28 |
Correct |
42 ms |
78584 KB |
Output is correct |
29 |
Correct |
43 ms |
78592 KB |
Output is correct |
30 |
Correct |
43 ms |
78584 KB |
Output is correct |
31 |
Correct |
42 ms |
78592 KB |
Output is correct |
32 |
Correct |
42 ms |
78592 KB |
Output is correct |
33 |
Correct |
112 ms |
107872 KB |
Output is correct |
34 |
Correct |
75 ms |
100216 KB |
Output is correct |
35 |
Correct |
79 ms |
100600 KB |
Output is correct |
36 |
Correct |
111 ms |
107900 KB |
Output is correct |
37 |
Correct |
118 ms |
108152 KB |
Output is correct |
38 |
Correct |
111 ms |
108024 KB |
Output is correct |
39 |
Correct |
103 ms |
106360 KB |
Output is correct |
40 |
Correct |
80 ms |
101752 KB |
Output is correct |
41 |
Correct |
108 ms |
107896 KB |
Output is correct |
42 |
Correct |
81 ms |
102264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
78584 KB |
Output is correct |
2 |
Correct |
43 ms |
78584 KB |
Output is correct |
3 |
Correct |
42 ms |
78584 KB |
Output is correct |
4 |
Correct |
42 ms |
78592 KB |
Output is correct |
5 |
Correct |
43 ms |
78584 KB |
Output is correct |
6 |
Correct |
42 ms |
78584 KB |
Output is correct |
7 |
Correct |
49 ms |
78584 KB |
Output is correct |
8 |
Correct |
45 ms |
78584 KB |
Output is correct |
9 |
Correct |
41 ms |
78584 KB |
Output is correct |
10 |
Correct |
42 ms |
78584 KB |
Output is correct |
11 |
Correct |
43 ms |
78584 KB |
Output is correct |
12 |
Correct |
43 ms |
78592 KB |
Output is correct |
13 |
Correct |
43 ms |
78584 KB |
Output is correct |
14 |
Correct |
43 ms |
78584 KB |
Output is correct |
15 |
Correct |
43 ms |
78584 KB |
Output is correct |
16 |
Correct |
42 ms |
78584 KB |
Output is correct |
17 |
Correct |
43 ms |
78584 KB |
Output is correct |
18 |
Correct |
43 ms |
78592 KB |
Output is correct |
19 |
Correct |
44 ms |
78588 KB |
Output is correct |
20 |
Correct |
48 ms |
78712 KB |
Output is correct |
21 |
Correct |
42 ms |
78584 KB |
Output is correct |
22 |
Correct |
42 ms |
78592 KB |
Output is correct |
23 |
Correct |
42 ms |
78584 KB |
Output is correct |
24 |
Correct |
42 ms |
78584 KB |
Output is correct |
25 |
Correct |
42 ms |
78584 KB |
Output is correct |
26 |
Correct |
42 ms |
78584 KB |
Output is correct |
27 |
Correct |
42 ms |
78584 KB |
Output is correct |
28 |
Correct |
42 ms |
78584 KB |
Output is correct |
29 |
Correct |
43 ms |
78592 KB |
Output is correct |
30 |
Correct |
43 ms |
78584 KB |
Output is correct |
31 |
Correct |
42 ms |
78592 KB |
Output is correct |
32 |
Correct |
42 ms |
78592 KB |
Output is correct |
33 |
Correct |
112 ms |
107872 KB |
Output is correct |
34 |
Correct |
75 ms |
100216 KB |
Output is correct |
35 |
Correct |
79 ms |
100600 KB |
Output is correct |
36 |
Correct |
111 ms |
107900 KB |
Output is correct |
37 |
Correct |
118 ms |
108152 KB |
Output is correct |
38 |
Correct |
111 ms |
108024 KB |
Output is correct |
39 |
Correct |
103 ms |
106360 KB |
Output is correct |
40 |
Correct |
80 ms |
101752 KB |
Output is correct |
41 |
Correct |
108 ms |
107896 KB |
Output is correct |
42 |
Correct |
81 ms |
102264 KB |
Output is correct |
43 |
Correct |
667 ms |
304096 KB |
Output is correct |
44 |
Correct |
361 ms |
293752 KB |
Output is correct |
45 |
Correct |
448 ms |
301560 KB |
Output is correct |
46 |
Correct |
681 ms |
322992 KB |
Output is correct |
47 |
Correct |
685 ms |
323040 KB |
Output is correct |
48 |
Correct |
710 ms |
323576 KB |
Output is correct |
49 |
Correct |
613 ms |
313916 KB |
Output is correct |
50 |
Correct |
412 ms |
289768 KB |
Output is correct |
51 |
Correct |
688 ms |
322728 KB |
Output is correct |
52 |
Correct |
433 ms |
290776 KB |
Output is correct |