| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1331240 | michael12 | 선물상자 (IOI15_boxes) | C++20 | 0 ms | 0 KiB |
// #include "boxes.h"
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define endl '\n'
using namespace std;
const int maxn = 1e6 + 5;
const int inf = 1e9 + 5;
long long delivery(int N, int K, int L, int p[]){
long long cur = 0;
vector<int> ps(N);
for(int i = 0; i < N; i++){
ps[i] = p[i];
}
vector<int> dp(N), dp1(N);
for(int i = 0; i < N; i++){
if(i >= K){
dp[i] = dp[i - K] + min(ps[i] * 2, L);
}
else{
dp[i] = min(ps[i] * 2, L);
}
}
int ans = 0;
for(int i = N - 1; i >= 0; i--){
if(i + K < N){
dp1[i] = dp1[i + K] + min(2 * (L - ps[i]), L);
}
else{
dp1[i] = min(2 * (L - ps[i]), L);
}
}
ans = min(dp[N - 1], dp1[0]);
for(int i = 0; i < N - 1; i++){
ans = min(ans, dp[i] + dp[i + 1]);
}
return ans;
}
signed main(){
int n, k, l;
cin >> n >> k >> l;
int a[n];
for(int i = 0; i < n; i++){
cin >> a[i];
}
cout << delivery(n, k, l, a);
}