# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
979609 | 2024-05-11T08:27:36 Z | kilkuwu | Boxes with souvenirs (IOI15_boxes) | C++17 | 379 ms | 215868 KB |
#include "boxes.h" #include <bits/stdc++.h> #ifdef LOCAL #include "template/debug.hpp" #else #define dbg(...) ; #define timer(...) ; #endif long long delivery(int N, int K, int L, int p[]) { int split = std::upper_bound(p, p + N, L / 2) - p; std::vector<long long> dp(N); for (int i = N - 1; i >= split; i--) { if (i + K < N) { dp[i] = dp[i + K] + (L - p[i]) * 2; } else { dp[i] = (L - p[i]) * 2; } } for (int i = 0; i < split; i++) { if (i - K >= 0) { dp[i] = dp[i - K] + p[i] * 2; } else { dp[i] = p[i] * 2; } } long long ans = split > 0 ? dp[split - 1] : 0; ans += (split < N) ? dp[split] : 0; long long round = 1e18; for (int i = split; i < N && i - K + 1 < split; i++) { long long cand = L; // go the entire thing cand += i + 1 < N ? dp[i + 1] : 0; cand += i - K >= 0 ? dp[i - K] : 0; round = std::min(round, cand); } return std::min(ans, round); } #ifdef LOCAL int main() { int N, K, L, i; std::cin >> N >> K >> L; int *p = (int*)malloc(sizeof(int) * (unsigned int)N); for (i = 0; i < N; i++) { std::cin >> p[i]; } std::cout << delivery(N, K, L, p) << "\n"; return 0; } #endif
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 344 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 424 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 344 KB | Output is correct |
4 | Correct | 1 ms | 344 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 344 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 424 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 344 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 344 KB | Output is correct |
18 | Correct | 1 ms | 344 KB | Output is correct |
19 | Correct | 1 ms | 348 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 0 ms | 348 KB | Output is correct |
22 | Correct | 1 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 1 ms | 440 KB | Output is correct |
30 | Correct | 0 ms | 348 KB | Output is correct |
31 | Correct | 0 ms | 348 KB | Output is correct |
32 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 344 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 424 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 344 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 344 KB | Output is correct |
18 | Correct | 1 ms | 344 KB | Output is correct |
19 | Correct | 1 ms | 348 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 0 ms | 348 KB | Output is correct |
22 | Correct | 1 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 1 ms | 440 KB | Output is correct |
30 | Correct | 0 ms | 348 KB | Output is correct |
31 | Correct | 0 ms | 348 KB | Output is correct |
32 | Correct | 0 ms | 348 KB | Output is correct |
33 | Correct | 39 ms | 21768 KB | Output is correct |
34 | Correct | 11 ms | 14164 KB | Output is correct |
35 | Correct | 12 ms | 14416 KB | Output is correct |
36 | Correct | 37 ms | 21924 KB | Output is correct |
37 | Correct | 38 ms | 21944 KB | Output is correct |
38 | Correct | 36 ms | 21840 KB | Output is correct |
39 | Correct | 34 ms | 20452 KB | Output is correct |
40 | Correct | 18 ms | 15708 KB | Output is correct |
41 | Correct | 37 ms | 21820 KB | Output is correct |
42 | Correct | 17 ms | 15956 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 344 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 424 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 1 ms | 344 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 0 ms | 348 KB | Output is correct |
11 | Correct | 0 ms | 348 KB | Output is correct |
12 | Correct | 0 ms | 348 KB | Output is correct |
13 | Correct | 0 ms | 348 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 344 KB | Output is correct |
18 | Correct | 1 ms | 344 KB | Output is correct |
19 | Correct | 1 ms | 348 KB | Output is correct |
20 | Correct | 0 ms | 348 KB | Output is correct |
21 | Correct | 0 ms | 348 KB | Output is correct |
22 | Correct | 1 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 0 ms | 348 KB | Output is correct |
25 | Correct | 0 ms | 348 KB | Output is correct |
26 | Correct | 0 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 1 ms | 440 KB | Output is correct |
30 | Correct | 0 ms | 348 KB | Output is correct |
31 | Correct | 0 ms | 348 KB | Output is correct |
32 | Correct | 0 ms | 348 KB | Output is correct |
33 | Correct | 39 ms | 21768 KB | Output is correct |
34 | Correct | 11 ms | 14164 KB | Output is correct |
35 | Correct | 12 ms | 14416 KB | Output is correct |
36 | Correct | 37 ms | 21924 KB | Output is correct |
37 | Correct | 38 ms | 21944 KB | Output is correct |
38 | Correct | 36 ms | 21840 KB | Output is correct |
39 | Correct | 34 ms | 20452 KB | Output is correct |
40 | Correct | 18 ms | 15708 KB | Output is correct |
41 | Correct | 37 ms | 21820 KB | Output is correct |
42 | Correct | 17 ms | 15956 KB | Output is correct |
43 | Correct | 376 ms | 214500 KB | Output is correct |
44 | Correct | 94 ms | 137264 KB | Output is correct |
45 | Correct | 121 ms | 145016 KB | Output is correct |
46 | Correct | 379 ms | 215676 KB | Output is correct |
47 | Correct | 371 ms | 215636 KB | Output is correct |
48 | Correct | 373 ms | 215664 KB | Output is correct |
49 | Correct | 327 ms | 200328 KB | Output is correct |
50 | Correct | 156 ms | 154232 KB | Output is correct |
51 | Correct | 377 ms | 215868 KB | Output is correct |
52 | Correct | 163 ms | 156856 KB | Output is correct |