oj.uz

Submission #752639

# Submission time Handle Problem Language Result Execution time Memory
752639 2023-06-03T10:55:50 Z adrilen Boxes with souvenirs (IOI15_boxes) C++17
100 / 100
 464 ms 200708 KB 
#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;

/*
Roughly three choices:
- Go left and deliver B presents and return on left
- Go right and deliver B presents and return on right
- Go in a circle and deliver as many presents as possible


Idea:
Have a prefix time taken to give first i from left
Have a prefix time taken to give first i from right

A circle takes L time

for o in [0..n/k]:
    find optimal value if we have o circles



*/

constexpr int maxn = 1e7 + 5;

ll left_side[maxn] = { 0 }, right_side[maxn] = { 0 };


long long delivery(int N, int K, int L, int p[]) {
    int n = N, k = K, l = L;

    // Calculate if going left
    for (int y = 0; y < n; y+= k)
    {
        for (int i = 1; i <= k; i++)
        {
            if (i + y > n) break;
            // cout << p[i + y - 1] << "\n";   
            left_side[y + i] = left_side[max(0, i + y - k)] + p[i + y - 1] + min(p[i + y - 1], l - p[i + y - 1]); 
        }
    }
    
    // Calculate if going right
    for (int y = 0; y < n; y+= k)
    {
        for (int i = 1; i <= k; i++)
        {
            if (i + y > n) break;
            // cout << p[n - (i + y)] << "\n";
            right_side[i + y] = right_side[max(0, i + y - k)] + (l - p[n - (i + y)]) + min(p[n - (i + y)], l - p[n - (i + y)]); 
        }
    }

    // for (int i = 0; i <= n; i++) cout << left_side[i] << " ";
    // cout << "\n";
    // for (int i = 0; i <= n; i++) cout << right_side[i] << " ";
    // cout << "\n";

    ll output = (1ll << 62);
    for (int i = 0; i <= n; i++)
    {
        output = min(output, left_side[i] + right_side[n - i]);
    }

    // cerr << output << endl;
    
    return output;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 316 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 324 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 320 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 324 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 320 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 51 ms 24436 KB Output is correct
34 Correct 19 ms 21768 KB Output is correct
35 Correct 23 ms 22220 KB Output is correct
36 Correct 54 ms 24440 KB Output is correct
37 Correct 50 ms 24424 KB Output is correct
38 Correct 54 ms 24472 KB Output is correct
39 Correct 44 ms 24392 KB Output is correct
40 Correct 26 ms 23444 KB Output is correct
41 Correct 53 ms 24372 KB Output is correct
42 Correct 33 ms 23728 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 324 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 320 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 51 ms 24436 KB Output is correct
34 Correct 19 ms 21768 KB Output is correct
35 Correct 23 ms 22220 KB Output is correct
36 Correct 54 ms 24440 KB Output is correct
37 Correct 50 ms 24424 KB Output is correct
38 Correct 54 ms 24472 KB Output is correct
39 Correct 44 ms 24392 KB Output is correct
40 Correct 26 ms 23444 KB Output is correct
41 Correct 53 ms 24372 KB Output is correct
42 Correct 33 ms 23728 KB Output is correct
43 Correct 464 ms 196716 KB Output is correct
44 Correct 185 ms 200708 KB Output is correct
45 Correct 201 ms 196092 KB Output is correct
46 Correct 464 ms 196900 KB Output is correct
47 Correct 451 ms 196808 KB Output is correct
48 Correct 450 ms 196820 KB Output is correct
49 Correct 401 ms 196660 KB Output is correct
50 Correct 229 ms 196036 KB Output is correct
51 Correct 453 ms 196800 KB Output is correct
52 Correct 237 ms 196112 KB Output is correct