# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1193601 | ElayV13 | 선물상자 (IOI15_boxes) | C++20 | 0 ms | 0 KiB |
//#include "boxes.h"
#include "bits/stdc++.h"
using namespace std;
const long long INF = 1e18;
const int N = 1005;
long long dp[N];
long long cost(int N , int f , int l){
return 2 * min(N - f , l);
}
long long delivery(int n , int k , int l , int p[])
{
for(int i = 1;i <= n;i++) dp[i] = INF;
dp[1] = cost(l , p[0] , p[0]);
for(int i = 2;i <= n - 1;i++)
{
int _i = i - 1;
for(int j = i - 1;j >= 1;j--)
{
int cnt = (i - j);
if(cnt > k) continue;
long long last = p[_i];
long long first = p[j];
dp[i] = min(dp[i] , dp[j] + cost(l , first , last));
}
if(i <= k)
dp[i] = min(dp[i] , cost(l , p[0] , p[i - 1]));
}
long long res = INF;
for(int i = 1;i <= n - 1;i++)
{
if(n - i <= k)
{
res = min(res , dp[i] + cost(l , p[i] , p[n - 1]));
}
}
return res;
}
signed main()
{
int n , k , l;
cin >> n >> k >> l;
int p[n];
for(int i = 0;i < n;i++) cin >> p[i];
cout << delivery(n , k , l , p) << endl;
}