Submission #768538

#	Time	Username	Problem	Language	Result	Execution time	Memory
768538		borisAngelov	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	556 ms	332964 KiB

boxes

#include "boxes.h"

#include <iostream>
#include <vector>

using namespace std;

const int maxn = 10000005;

int n, k, l;

int positions[maxn];

long long dp_left[maxn];
long long dp_right[maxn];

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

    for (int i = 1; i <= n; ++i)
    {
        positions[i] = p[i - 1];
    }

    dp_left[0] = 0;
    dp_right[n + 1] = 0;

    for (int i = 1; i <= n; ++i)
    {
        if (i <= k)
        {
            dp_left[i] = 2 * positions[i];
        }
        else
        {
            dp_left[i] = dp_left[i - k] + 2 * positions[i];
        }
    }

    for (int i = n; i >= 1; --i)
    {
        if (n - i + 1 <= k)
        {
            dp_right[i] = 2 * (l - positions[i]);
        }
        else
        {
            dp_right[i] = dp_right[i + k] + 2 * (l - positions[i]);
        }
    }

    long long ans = (1LL << 62);

    if (n <= k)
    {
        ans = l;
    }

    for (int i = 0; i <= n; ++i)
    {
        ans = min(ans, dp_left[i] + dp_right[i + 1]);
    }

    for (int i = 0; i <= n; ++i)
    {
        if (i + k + 1 > n + 1)
        {
            break;
        }

        ans = min(ans, dp_left[i] + l + dp_right[i + k + 1]);
    }

    return ans;
}

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