# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
771316 | 2023-07-02T20:10:30 Z | caganyanmaz | Boxes with souvenirs (IOI15_boxes) | C++17 | 551 ms | 293896 KB |
#include <bits/stdc++.h> #define pb push_back #define DEBUGGING #define f first #define s second #define int int64_t #ifdef DEBUGGING #define debug(x) cout << (#x) << ": " << (x) << "\n"; #else #define debug(x) 42 #endif using namespace std; constexpr static int MXSIZE = 1e7 + 2; int left_dp[MXSIZE]; int right_dp[MXSIZE]; vector<int> left_val; vector<int> right_val; int mid = 0; bool inleft(int pos, int L) { if (L&1) return pos <= (L/2); else return pos < (L/2); } int delivery(int32_t N, int32_t K, int32_t L, int32_t p[]) { for (int i = 0; i < N; i++) if (inleft(p[i], L)) left_val.pb(p[i]); else if (p[i] > (L / 2)) right_val.pb(p[i]); else mid++; reverse(right_val.begin(), right_val.end()); for (int i = 1; i <= left_val.size(); i++) { if (i - K >= 0) left_dp[i] = left_dp[i-K]; left_dp[i] += left_val[i-1] * 2; } for (int i = 1; i <= right_val.size(); i++) { if (i - K >= 0) right_dp[i] = right_dp[i-K]; right_dp[i] += (L - right_val[i-1]) * 2; } int res = left_dp[left_val.size()] + right_dp[right_val.size()] + (mid/K) * L; if ((mid%K) != 0) res += L; if (K==1) return res; for (int j = 1; j <= 4; j++) { int lo = K * j - (mid % K); for (int i = 0; i <= lo; i++) if (left_val.size() >= i && right_val.size() >= lo-i) res = min(res, left_dp[left_val.size()-i] + right_dp[right_val.size()-lo+i] + ((mid+lo)/K) * L); } return res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 0 ms | 212 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 0 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 0 ms | 340 KB | Output is correct |
13 | Correct | 0 ms | 340 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 0 ms | 212 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 0 ms | 212 KB | Output is correct |
21 | Correct | 0 ms | 212 KB | Output is correct |
22 | Correct | 0 ms | 212 KB | Output is correct |
23 | Correct | 0 ms | 340 KB | Output is correct |
24 | Correct | 0 ms | 340 KB | Output is correct |
25 | Correct | 1 ms | 340 KB | Output is correct |
26 | Correct | 0 ms | 340 KB | Output is correct |
27 | Correct | 0 ms | 340 KB | Output is correct |
28 | Correct | 1 ms | 340 KB | Output is correct |
29 | Correct | 0 ms | 340 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Correct | 0 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 0 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 0 ms | 340 KB | Output is correct |
13 | Correct | 0 ms | 340 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 0 ms | 212 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 0 ms | 212 KB | Output is correct |
21 | Correct | 0 ms | 212 KB | Output is correct |
22 | Correct | 0 ms | 212 KB | Output is correct |
23 | Correct | 0 ms | 340 KB | Output is correct |
24 | Correct | 0 ms | 340 KB | Output is correct |
25 | Correct | 1 ms | 340 KB | Output is correct |
26 | Correct | 0 ms | 340 KB | Output is correct |
27 | Correct | 0 ms | 340 KB | Output is correct |
28 | Correct | 1 ms | 340 KB | Output is correct |
29 | Correct | 0 ms | 340 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Correct | 0 ms | 340 KB | Output is correct |
33 | Correct | 52 ms | 29628 KB | Output is correct |
34 | Correct | 21 ms | 25976 KB | Output is correct |
35 | Correct | 21 ms | 21596 KB | Output is correct |
36 | Correct | 46 ms | 29800 KB | Output is correct |
37 | Correct | 46 ms | 29712 KB | Output is correct |
38 | Correct | 51 ms | 31648 KB | Output is correct |
39 | Correct | 41 ms | 28212 KB | Output is correct |
40 | Correct | 28 ms | 23872 KB | Output is correct |
41 | Correct | 46 ms | 29748 KB | Output is correct |
42 | Correct | 25 ms | 23808 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 0 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 0 ms | 340 KB | Output is correct |
13 | Correct | 0 ms | 340 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 212 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 0 ms | 212 KB | Output is correct |
18 | Correct | 0 ms | 212 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 0 ms | 212 KB | Output is correct |
21 | Correct | 0 ms | 212 KB | Output is correct |
22 | Correct | 0 ms | 212 KB | Output is correct |
23 | Correct | 0 ms | 340 KB | Output is correct |
24 | Correct | 0 ms | 340 KB | Output is correct |
25 | Correct | 1 ms | 340 KB | Output is correct |
26 | Correct | 0 ms | 340 KB | Output is correct |
27 | Correct | 0 ms | 340 KB | Output is correct |
28 | Correct | 1 ms | 340 KB | Output is correct |
29 | Correct | 0 ms | 340 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Correct | 0 ms | 340 KB | Output is correct |
33 | Correct | 52 ms | 29628 KB | Output is correct |
34 | Correct | 21 ms | 25976 KB | Output is correct |
35 | Correct | 21 ms | 21596 KB | Output is correct |
36 | Correct | 46 ms | 29800 KB | Output is correct |
37 | Correct | 46 ms | 29712 KB | Output is correct |
38 | Correct | 51 ms | 31648 KB | Output is correct |
39 | Correct | 41 ms | 28212 KB | Output is correct |
40 | Correct | 28 ms | 23872 KB | Output is correct |
41 | Correct | 46 ms | 29748 KB | Output is correct |
42 | Correct | 25 ms | 23808 KB | Output is correct |
43 | Correct | 549 ms | 292756 KB | Output is correct |
44 | Correct | 228 ms | 215660 KB | Output is correct |
45 | Correct | 277 ms | 220364 KB | Output is correct |
46 | Correct | 522 ms | 293872 KB | Output is correct |
47 | Correct | 518 ms | 293896 KB | Output is correct |
48 | Correct | 520 ms | 293724 KB | Output is correct |
49 | Correct | 523 ms | 278616 KB | Output is correct |
50 | Correct | 331 ms | 232404 KB | Output is correct |
51 | Correct | 551 ms | 293160 KB | Output is correct |
52 | Correct | 308 ms | 235104 KB | Output is correct |