#include "boxes.h"
#include "bits/stdc++.h"
using namespace std;
const long long MXN = 1000005;
long long n, k, l, pos[MXN], rpos[MXN];
long long dpleft[MXN];
long long dpright[MXN];
long long delivery(int N, int K, int L, int p[]) {
for (int i=0; i<MXN; i++) {
dpleft[i] = -1;
dpright[i] = -1;
}
n = N;
k = K;
l = L;
for (int i=0; i<n; i++) {
pos[i] = p[i];
rpos[i] = L - p[i];
}
long long best = LLONG_MAX;
for (int i=0; i<n; i++) {
dpleft[i] = pos[i] * 2;
if (i - k >= 0) dpleft[i] += dpleft[i-k];
}
for (int i=n-1; i>=0; i--) {
dpright[i] = rpos[i] * 2;
if (i + k < n) dpright[i] += dpright[i+k];
}
// for (int i=0; i<n; i++) cout << dpleft[i] << ' '; cout << endl;
// for (int i=0; i<n; i++) cout << dpright[i] << ' '; cout << endl;
best = min(best, dpleft[n-1]);
best = min(best, dpright[0]);
for (int i=0; i<n-1; i++) {
best = min(best, dpleft[i] + dpright[i+1]);
}
for (int i=0; i<n-1; i++) {
// skip i..i+k-1 using the circle
long long unt = l;
if (i >= 1) unt += dpleft[i-1];
if (i + k < n) unt += dpright[i+k];
best = min(best, unt);
}
return best;
}
Compilation message
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:27:14: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
for (int i=n-1; i>=0; i--) {
~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
16000 KB |
Output is correct |
2 |
Correct |
12 ms |
16000 KB |
Output is correct |
3 |
Correct |
12 ms |
16000 KB |
Output is correct |
4 |
Correct |
12 ms |
16000 KB |
Output is correct |
5 |
Correct |
13 ms |
16000 KB |
Output is correct |
6 |
Correct |
12 ms |
16000 KB |
Output is correct |
7 |
Correct |
13 ms |
16000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
16000 KB |
Output is correct |
2 |
Correct |
12 ms |
16000 KB |
Output is correct |
3 |
Correct |
12 ms |
16000 KB |
Output is correct |
4 |
Correct |
12 ms |
16000 KB |
Output is correct |
5 |
Correct |
12 ms |
16000 KB |
Output is correct |
6 |
Correct |
12 ms |
16000 KB |
Output is correct |
7 |
Correct |
12 ms |
16000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
16000 KB |
Output is correct |
2 |
Correct |
12 ms |
16000 KB |
Output is correct |
3 |
Correct |
12 ms |
16000 KB |
Output is correct |
4 |
Correct |
14 ms |
16000 KB |
Output is correct |
5 |
Correct |
12 ms |
16000 KB |
Output is correct |
6 |
Correct |
13 ms |
16000 KB |
Output is correct |
7 |
Correct |
12 ms |
16000 KB |
Output is correct |
8 |
Correct |
12 ms |
16000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
16000 KB |
Output is correct |
2 |
Correct |
12 ms |
16000 KB |
Output is correct |
3 |
Correct |
12 ms |
16000 KB |
Output is correct |
4 |
Correct |
12 ms |
16000 KB |
Output is correct |
5 |
Correct |
13 ms |
16000 KB |
Output is correct |
6 |
Correct |
12 ms |
16000 KB |
Output is correct |
7 |
Correct |
13 ms |
16000 KB |
Output is correct |
8 |
Correct |
13 ms |
16000 KB |
Output is correct |
9 |
Correct |
12 ms |
16000 KB |
Output is correct |
10 |
Correct |
12 ms |
16000 KB |
Output is correct |
11 |
Correct |
12 ms |
16000 KB |
Output is correct |
12 |
Correct |
12 ms |
16000 KB |
Output is correct |
13 |
Correct |
12 ms |
16000 KB |
Output is correct |
14 |
Correct |
12 ms |
16000 KB |
Output is correct |
15 |
Correct |
12 ms |
16000 KB |
Output is correct |
16 |
Correct |
12 ms |
16000 KB |
Output is correct |
17 |
Correct |
12 ms |
16000 KB |
Output is correct |
18 |
Correct |
14 ms |
16000 KB |
Output is correct |
19 |
Correct |
12 ms |
16000 KB |
Output is correct |
20 |
Correct |
13 ms |
16000 KB |
Output is correct |
21 |
Correct |
12 ms |
16000 KB |
Output is correct |
22 |
Correct |
12 ms |
16000 KB |
Output is correct |
23 |
Correct |
13 ms |
16000 KB |
Output is correct |
24 |
Correct |
13 ms |
16000 KB |
Output is correct |
25 |
Correct |
13 ms |
16128 KB |
Output is correct |
26 |
Correct |
14 ms |
16000 KB |
Output is correct |
27 |
Correct |
13 ms |
16000 KB |
Output is correct |
28 |
Correct |
13 ms |
16000 KB |
Output is correct |
29 |
Correct |
12 ms |
16000 KB |
Output is correct |
30 |
Correct |
12 ms |
16000 KB |
Output is correct |
31 |
Correct |
12 ms |
16000 KB |
Output is correct |
32 |
Correct |
12 ms |
16000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
16000 KB |
Output is correct |
2 |
Correct |
12 ms |
16000 KB |
Output is correct |
3 |
Correct |
12 ms |
16000 KB |
Output is correct |
4 |
Correct |
12 ms |
16000 KB |
Output is correct |
5 |
Correct |
13 ms |
16000 KB |
Output is correct |
6 |
Correct |
12 ms |
16000 KB |
Output is correct |
7 |
Correct |
13 ms |
16000 KB |
Output is correct |
8 |
Correct |
13 ms |
16000 KB |
Output is correct |
9 |
Correct |
12 ms |
16000 KB |
Output is correct |
10 |
Correct |
12 ms |
16000 KB |
Output is correct |
11 |
Correct |
12 ms |
16000 KB |
Output is correct |
12 |
Correct |
12 ms |
16000 KB |
Output is correct |
13 |
Correct |
12 ms |
16000 KB |
Output is correct |
14 |
Correct |
12 ms |
16000 KB |
Output is correct |
15 |
Correct |
12 ms |
16000 KB |
Output is correct |
16 |
Correct |
12 ms |
16000 KB |
Output is correct |
17 |
Correct |
12 ms |
16000 KB |
Output is correct |
18 |
Correct |
14 ms |
16000 KB |
Output is correct |
19 |
Correct |
12 ms |
16000 KB |
Output is correct |
20 |
Correct |
13 ms |
16000 KB |
Output is correct |
21 |
Correct |
12 ms |
16000 KB |
Output is correct |
22 |
Correct |
12 ms |
16000 KB |
Output is correct |
23 |
Correct |
13 ms |
16000 KB |
Output is correct |
24 |
Correct |
13 ms |
16000 KB |
Output is correct |
25 |
Correct |
13 ms |
16128 KB |
Output is correct |
26 |
Correct |
14 ms |
16000 KB |
Output is correct |
27 |
Correct |
13 ms |
16000 KB |
Output is correct |
28 |
Correct |
13 ms |
16000 KB |
Output is correct |
29 |
Correct |
12 ms |
16000 KB |
Output is correct |
30 |
Correct |
12 ms |
16000 KB |
Output is correct |
31 |
Correct |
12 ms |
16000 KB |
Output is correct |
32 |
Correct |
12 ms |
16000 KB |
Output is correct |
33 |
Correct |
94 ms |
45176 KB |
Output is correct |
34 |
Correct |
37 ms |
37504 KB |
Output is correct |
35 |
Correct |
39 ms |
38016 KB |
Output is correct |
36 |
Correct |
72 ms |
45432 KB |
Output is correct |
37 |
Correct |
70 ms |
45304 KB |
Output is correct |
38 |
Correct |
106 ms |
45356 KB |
Output is correct |
39 |
Correct |
65 ms |
43768 KB |
Output is correct |
40 |
Correct |
43 ms |
39160 KB |
Output is correct |
41 |
Correct |
69 ms |
45304 KB |
Output is correct |
42 |
Correct |
43 ms |
39544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
16000 KB |
Output is correct |
2 |
Correct |
12 ms |
16000 KB |
Output is correct |
3 |
Correct |
12 ms |
16000 KB |
Output is correct |
4 |
Correct |
12 ms |
16000 KB |
Output is correct |
5 |
Correct |
13 ms |
16000 KB |
Output is correct |
6 |
Correct |
12 ms |
16000 KB |
Output is correct |
7 |
Correct |
13 ms |
16000 KB |
Output is correct |
8 |
Correct |
13 ms |
16000 KB |
Output is correct |
9 |
Correct |
12 ms |
16000 KB |
Output is correct |
10 |
Correct |
12 ms |
16000 KB |
Output is correct |
11 |
Correct |
12 ms |
16000 KB |
Output is correct |
12 |
Correct |
12 ms |
16000 KB |
Output is correct |
13 |
Correct |
12 ms |
16000 KB |
Output is correct |
14 |
Correct |
12 ms |
16000 KB |
Output is correct |
15 |
Correct |
12 ms |
16000 KB |
Output is correct |
16 |
Correct |
12 ms |
16000 KB |
Output is correct |
17 |
Correct |
12 ms |
16000 KB |
Output is correct |
18 |
Correct |
14 ms |
16000 KB |
Output is correct |
19 |
Correct |
12 ms |
16000 KB |
Output is correct |
20 |
Correct |
13 ms |
16000 KB |
Output is correct |
21 |
Correct |
12 ms |
16000 KB |
Output is correct |
22 |
Correct |
12 ms |
16000 KB |
Output is correct |
23 |
Correct |
13 ms |
16000 KB |
Output is correct |
24 |
Correct |
13 ms |
16000 KB |
Output is correct |
25 |
Correct |
13 ms |
16128 KB |
Output is correct |
26 |
Correct |
14 ms |
16000 KB |
Output is correct |
27 |
Correct |
13 ms |
16000 KB |
Output is correct |
28 |
Correct |
13 ms |
16000 KB |
Output is correct |
29 |
Correct |
12 ms |
16000 KB |
Output is correct |
30 |
Correct |
12 ms |
16000 KB |
Output is correct |
31 |
Correct |
12 ms |
16000 KB |
Output is correct |
32 |
Correct |
12 ms |
16000 KB |
Output is correct |
33 |
Correct |
94 ms |
45176 KB |
Output is correct |
34 |
Correct |
37 ms |
37504 KB |
Output is correct |
35 |
Correct |
39 ms |
38016 KB |
Output is correct |
36 |
Correct |
72 ms |
45432 KB |
Output is correct |
37 |
Correct |
70 ms |
45304 KB |
Output is correct |
38 |
Correct |
106 ms |
45356 KB |
Output is correct |
39 |
Correct |
65 ms |
43768 KB |
Output is correct |
40 |
Correct |
43 ms |
39160 KB |
Output is correct |
41 |
Correct |
69 ms |
45304 KB |
Output is correct |
42 |
Correct |
43 ms |
39544 KB |
Output is correct |
43 |
Runtime error |
555 ms |
240200 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
44 |
Halted |
0 ms |
0 KB |
- |