Submission #1242809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242809		Mousa_Aboubaker	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	348 ms	196256 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;

long long delivery(int N, int K, int L, int p[])
{
    auto dis = [&](int l, int r) -> int
    {
        int res = min(abs(l - r), L - abs(l - r));
        return res;
    };

    vector<long long> dp1(N);
    for(int i = 0; i < K; i++)
        dp1[i] = p[i] * 2;
    for(int i = K; i < N; i++)
        dp1[i] = dp1[i - K] + p[i] * 2;
    vector<long long> dp2(N);
    for(int i = N - 1; i >= N - K; i--)
        dp2[i] = (L - p[i]) * 2;
    for(int i = N - K - 1; i >= 0; i--)
        dp2[i] = dp2[i + K] + (L - p[i]) * 2;
    long long res = 9e18;
    for(int i = 0; i + K - 1 < N; i++)
    {
        if(dis(0, p[i]) == p[i] and dis(0, p[i + K - 1]) == L - p[i + K - 1])
        {
            long long d1 = (i ? dp1[i - 1] : 0);
            long long d2 = (i + K - 1 != N - 1 ? dp2[i + K] : 0);
            res = min(res, d1 + d2 + L);
        }
    }
    for(int i = 0; i + 1 < N; i++)
        res = min(res, dp1[i] + dp2[i + 1]);
    res = min(res, dp1[N - 1]);
    res = min(res, dp2[0]);
    return res;
}

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