| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1291199 | Ludissey | Boxes with souvenirs (IOI15_boxes) | C11 | 0 ms | 0 KiB |
#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
int n,K,L;
long long delivery(signed _n, signed _k, signed _l, signed p[]) {
n=_n;
K=_k;
L=_l;
vector<int> a(n);
for (int i = 0; i < n; i++) a[i]=p[i];
sort(all(a));
vector<int> prefl(n);
vector<int> prefr(n);
vector<int> dp(n,1e17);
for (int i = 0; i < n; i++)
{
prefl[i]=a[i]*2;
prefr[n-i-1]=(L-a[n-i-1])*2;
if(i>=K) prefl[i]+=prefl[i-K], prefr[n-i-1]+=prefr[n-i-1+K];
}
int mn=min(min(prefl[n-1],prefr[0]), ((n+K-1)/K)*L);
for (int i = 0; i < n; i++)
{
int prf=0;
if(i>=K) prf=dp[i-K];
dp[i]=min(dp[i], min(prefl[i],L+prf));
if(i>0) mn=min(mn,dp[i-1]+prefr[i]);
}
return mn;
}
