Submission #98558

#	Time	Username	Problem	Language	Result	Execution time	Memory
98558		someone_aa	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	2033 ms	20748 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 10000100;
ll dp[maxn], n, k, l;
int arr[maxn];

long long delivery(int N, int K, int L, int p[]) {
    for(int i=0;i<N;i++) {
        arr[i+1] = p[i];
    }
    n = N; k = K; l = L;
    for(int i=1;i<=n;i++) {
        // solve for prefix of size i
        dp[i] = LLONG_MAX;
        for(ll j=i-1;j>=max(0LL, i-k);j--) {
            ll cost = dp[j] + min(l, min(2LL*arr[i], 2LL*(l-arr[j+1])));
            dp[i] = min(dp[i], cost);
        }
    }
    return dp[n];
}

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