# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1178725 | goduadzesaba | Boxes with souvenirs (IOI15_boxes) | C++20 | 0 ms | 0 KiB |
#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=1e7+5,mod=1e9+7,inf=1e18;
long long delivery(int N, int K, int L, int p[]) {
int dp[N],ds[N];
for (int i=0; i<N; i++){
if (i-K>=0) dp[i]=dp[i-K];
else dp[i]=0;
dp[i]+=min(L,2*p[i]);
}
for (int i=N-1; i>=0; i--){
if (i+K<N) ds[i]=dp[i+K];
else ds[i]=0;
dp[i]+=min(L,2*(L-p[i]));
}
int ans=min(dp[N-1],ds[0]);
//cout<<ans<<"\n";
for (int i=0; i<N-1; i++){
ans=min(ans,dp[i]+ds[i+1]);
//cout<<ans<<"\n";
}
return ans;
}
/*signed main(){
int sm[3]={1,2,5};
cout<<delivery(3,2,8,sm);
}
*/