Submission #1060573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060573		damjandavkov	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	395 ms	270752 KiB

boxes

#include "boxes.h"
#include <vector>
using namespace std;
typedef long long ll;
ll delivery(int N, int K, int L, int p[])
{
    vector<ll> ls = {0}, rs = {0};
    int i, k = K - 1, n = N - 1, h, l = (L << 1);
    for (i = 0; i < N; i++)
        p[i] <<= 1;
    for (i = 0; i < N; i++)
    {
        if (p[i] > L)
            break;
        ls.push_back(p[i] + ls[max(0, i - k)]);
    }
    h = i;
    for (i = 0; i < N; i++)
    {
        if (p[n - i] <= L)
            break;
        rs.push_back(l - p[n - i] + rs[max(0, i - k)]);
    }
    ll m = ls[h] + rs[N - h] - L;
    N -= K;
    for (i = max(0, h - K); i <= min(N, h); i++)
        m = min(m, ls[i] + rs[N - i]);
    m -= L;
    N -= K;
    for (i = max(0, h - (K << 1)); i <= min(N, h); i++)
        m = min(m, ls[i] + rs[N - i]);
    return m + (L << 1);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30