/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 10000007;
int n, k;
LL m, l[N], r[N], pos[N];
LL ans = mod * mod;
LL delivery(int N, int K, int L, int* P)
{
n = N;
k = min(K,N);
m = L;
for (int i = 0; i < n; i++)
pos[i + 1] = P[i];
pos[n + 1] = m;
for (int i = 1; i <= n; i++)
{
int id = (i - 1) / k;
l[i] = min(l[id * k], l[max(i - k, 0)]);
l[i] += abs(pos[i] - pos[0]) * 2ll;
}
reverse(pos, pos + 1 + n + 1);
for (int i = 1; i <= n; i++)
{
int id = (i - 1) / k;
r[i] = min(r[id * k], r[max(i - k, 0)]);
r[i] += abs(pos[i] - pos[0]) * 2ll;
}
reverse(pos, pos + 1 + n + 1);
for (int i = 0; i <= n; i++)
ans = min(ans, l[i] + r[n - i]);
for (int i = 0; i <= n; i++)
ans = min(ans, l[i] + r[max(0, n - i - k)] + m);
for (int i = 0; i <= n; i++)
ans = min(ans, r[i] + l[max(0, n - i - k)] + m);
return ans;
}
#ifdef death
int main()
{
int N, K, L;
int P[102];
cin >> N >> K >> L;
for (int i = 0; i < N; i++)
cin >> P[i];
cout << delivery(N, K, L, P) << endl;
return 0;
}
#endif
/*
3 2 8
1 2 5
4 3 6
0 0 4 5
2 3 7
3 4
0 1 2 3 4 5 6 0
* *
*/
Compilation message
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:31:40: warning: declaration of 'N' shadows a global declaration [-Wshadow]
LL delivery(int N, int K, int L, int* P)
^
boxes.cpp:25:11: note: shadowed declaration is here
const int N = 10000007;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
288 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
384 KB |
Output is correct |
12 |
Correct |
4 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
4 ms |
384 KB |
Output is correct |
17 |
Correct |
4 ms |
384 KB |
Output is correct |
18 |
Correct |
4 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
288 KB |
Output is correct |
20 |
Correct |
4 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
4 ms |
384 KB |
Output is correct |
26 |
Correct |
5 ms |
384 KB |
Output is correct |
27 |
Correct |
5 ms |
384 KB |
Output is correct |
28 |
Correct |
5 ms |
384 KB |
Output is correct |
29 |
Correct |
5 ms |
384 KB |
Output is correct |
30 |
Correct |
4 ms |
384 KB |
Output is correct |
31 |
Correct |
4 ms |
384 KB |
Output is correct |
32 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
384 KB |
Output is correct |
12 |
Correct |
4 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
4 ms |
384 KB |
Output is correct |
17 |
Correct |
4 ms |
384 KB |
Output is correct |
18 |
Correct |
4 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
288 KB |
Output is correct |
20 |
Correct |
4 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
4 ms |
384 KB |
Output is correct |
26 |
Correct |
5 ms |
384 KB |
Output is correct |
27 |
Correct |
5 ms |
384 KB |
Output is correct |
28 |
Correct |
5 ms |
384 KB |
Output is correct |
29 |
Correct |
5 ms |
384 KB |
Output is correct |
30 |
Correct |
4 ms |
384 KB |
Output is correct |
31 |
Correct |
4 ms |
384 KB |
Output is correct |
32 |
Correct |
5 ms |
384 KB |
Output is correct |
33 |
Correct |
74 ms |
27760 KB |
Output is correct |
34 |
Correct |
43 ms |
27768 KB |
Output is correct |
35 |
Correct |
48 ms |
27768 KB |
Output is correct |
36 |
Correct |
75 ms |
27676 KB |
Output is correct |
37 |
Correct |
74 ms |
27768 KB |
Output is correct |
38 |
Correct |
75 ms |
27772 KB |
Output is correct |
39 |
Correct |
70 ms |
27768 KB |
Output is correct |
40 |
Correct |
51 ms |
27768 KB |
Output is correct |
41 |
Correct |
75 ms |
27768 KB |
Output is correct |
42 |
Correct |
51 ms |
27768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
384 KB |
Output is correct |
12 |
Correct |
4 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
4 ms |
384 KB |
Output is correct |
17 |
Correct |
4 ms |
384 KB |
Output is correct |
18 |
Correct |
4 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
288 KB |
Output is correct |
20 |
Correct |
4 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
4 ms |
384 KB |
Output is correct |
26 |
Correct |
5 ms |
384 KB |
Output is correct |
27 |
Correct |
5 ms |
384 KB |
Output is correct |
28 |
Correct |
5 ms |
384 KB |
Output is correct |
29 |
Correct |
5 ms |
384 KB |
Output is correct |
30 |
Correct |
4 ms |
384 KB |
Output is correct |
31 |
Correct |
4 ms |
384 KB |
Output is correct |
32 |
Correct |
5 ms |
384 KB |
Output is correct |
33 |
Correct |
74 ms |
27760 KB |
Output is correct |
34 |
Correct |
43 ms |
27768 KB |
Output is correct |
35 |
Correct |
48 ms |
27768 KB |
Output is correct |
36 |
Correct |
75 ms |
27676 KB |
Output is correct |
37 |
Correct |
74 ms |
27768 KB |
Output is correct |
38 |
Correct |
75 ms |
27772 KB |
Output is correct |
39 |
Correct |
70 ms |
27768 KB |
Output is correct |
40 |
Correct |
51 ms |
27768 KB |
Output is correct |
41 |
Correct |
75 ms |
27768 KB |
Output is correct |
42 |
Correct |
51 ms |
27768 KB |
Output is correct |
43 |
Correct |
680 ms |
274316 KB |
Output is correct |
44 |
Correct |
373 ms |
289144 KB |
Output is correct |
45 |
Correct |
466 ms |
285176 KB |
Output is correct |
46 |
Correct |
696 ms |
297716 KB |
Output is correct |
47 |
Correct |
701 ms |
297716 KB |
Output is correct |
48 |
Correct |
714 ms |
297460 KB |
Output is correct |
49 |
Correct |
624 ms |
294008 KB |
Output is correct |
50 |
Correct |
443 ms |
289912 KB |
Output is correct |
51 |
Correct |
694 ms |
297844 KB |
Output is correct |
52 |
Correct |
461 ms |
313524 KB |
Output is correct |