Submission #1212796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212796		jujuedv	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	365 ms	216284 KiB

boxes

#include "boxes.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

long long delivery(int N, int K, int L, int p[]) {
    vector<ll> dpL(N+1), dpR(N+1);
    for(int i = 0; i < N; ++i) {
        ll from = max(0, i-K+1);
        ll cost = min(L-p[i], p[i]) + min(L-p[from], p[from]) + abs(p[from]-p[i]);

        dpL[i+1] = dpL[from] + cost;
    }

    for(int i = N-1; i >= 0; --i) {
        ll from = min(N-1, i+K-1);
        ll cost = min(L-p[i], p[i]) + min(L-p[from], p[from]) + abs(p[from]-p[i]);

        dpR[i] = dpR[from+1] + cost;
    }
    ll res = ll(1e18);

    for(int i = 0; i <= N; ++i) {
        res = min(res, dpL[i] + dpR[i]);
    }

    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