#include "boxes.h"
#include <iostream>
using namespace std;
long long ll(int a)
{
return (long long)(a);
}
//#teams, capacity, #sections, position of each team
long long delivery(int N, int K, int L, int positions[])
{
long long dp_inc[N]; //minimum time needed to cover all 0, 1, ... i and end up at positions[i]
dp_inc[0] = ll(positions[0]);
for(int i = 1; i < K; i++)
{
dp_inc[i] = ll(positions[i]);
}
for(int i = K; i < N; i++)
{
dp_inc[i] = dp_inc[i - K] + ll(positions[i - K]) + ll(positions[i]);
}
// for(int i = 0; i < N; i++) cout << dp_inc[i] << ' ';
// cout << '\n';
long long dp_dec[N];
dp_dec[N-1] = ll(L) - ll(positions[N-1]);
for(int i = N-2; i > N-K-1; i--)
{
dp_dec[i] = ll(L) - ll(positions[i]);
}
for(int i = N-K-1; i >= 0; i--)
{
dp_dec[i] = dp_dec[i + K] + (ll(L) - ll(positions[i + K])) + (ll(L) - ll(positions[i]));
}
//for(int i = 0; i < N; i++) cout << dp_dec[i] << ' ';
//cout << '\n';
long long res = ll(1000 * 1000 * 1000) * ll(1000 * 1000 * 1000);
for(int i = 0; i < N-1; i++)
res = min(res, dp_inc[i] + ll(min(positions[i], L - positions[i])) + dp_dec[i+1] + ll(min(positions[i+1], L - positions[i+1])));
res = min(res, dp_inc[N-1] + ll(min(positions[N-1], L - positions[N-1])));
res = min(res, dp_dec[0] + ll(min(positions[0], L - positions[0])));
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
364 KB |
Output is correct |
8 |
Correct |
0 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
0 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
0 ms |
364 KB |
Output is correct |
19 |
Correct |
0 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
0 ms |
364 KB |
Output is correct |
22 |
Correct |
0 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
0 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
0 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
0 ms |
364 KB |
Output is correct |
19 |
Correct |
0 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
0 ms |
364 KB |
Output is correct |
22 |
Correct |
0 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
0 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
60 ms |
29548 KB |
Output is correct |
34 |
Correct |
25 ms |
21868 KB |
Output is correct |
35 |
Correct |
27 ms |
22380 KB |
Output is correct |
36 |
Correct |
61 ms |
29676 KB |
Output is correct |
37 |
Correct |
59 ms |
29676 KB |
Output is correct |
38 |
Correct |
59 ms |
29676 KB |
Output is correct |
39 |
Correct |
55 ms |
28268 KB |
Output is correct |
40 |
Correct |
32 ms |
23532 KB |
Output is correct |
41 |
Correct |
59 ms |
29676 KB |
Output is correct |
42 |
Correct |
33 ms |
23788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
0 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
0 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
0 ms |
364 KB |
Output is correct |
19 |
Correct |
0 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
0 ms |
364 KB |
Output is correct |
22 |
Correct |
0 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
0 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
60 ms |
29548 KB |
Output is correct |
34 |
Correct |
25 ms |
21868 KB |
Output is correct |
35 |
Correct |
27 ms |
22380 KB |
Output is correct |
36 |
Correct |
61 ms |
29676 KB |
Output is correct |
37 |
Correct |
59 ms |
29676 KB |
Output is correct |
38 |
Correct |
59 ms |
29676 KB |
Output is correct |
39 |
Correct |
55 ms |
28268 KB |
Output is correct |
40 |
Correct |
32 ms |
23532 KB |
Output is correct |
41 |
Correct |
59 ms |
29676 KB |
Output is correct |
42 |
Correct |
33 ms |
23788 KB |
Output is correct |
43 |
Correct |
563 ms |
248188 KB |
Output is correct |
44 |
Correct |
243 ms |
215532 KB |
Output is correct |
45 |
Correct |
273 ms |
223468 KB |
Output is correct |
46 |
Correct |
583 ms |
293868 KB |
Output is correct |
47 |
Correct |
599 ms |
293996 KB |
Output is correct |
48 |
Correct |
567 ms |
266220 KB |
Output is correct |
49 |
Correct |
513 ms |
258796 KB |
Output is correct |
50 |
Correct |
317 ms |
232428 KB |
Output is correct |
51 |
Correct |
581 ms |
294124 KB |
Output is correct |
52 |
Correct |
329 ms |
235116 KB |
Output is correct |