Submission #752639

#	Time	Username	Problem	Language	Result	Execution time	Memory
752639		adrilen	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	464 ms	200708 KiB

boxes

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30