| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1178735 | 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;
long long delivery(int N, int K, int L, int p[]) {
long long n=N,k=K,l=L;
long long a[n];
for (int i=0; i<n; i++) a[i]=p[i];
long long 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*a[i]);
//cout<<i<<" "<<dp[i]<<"\n";
}
for (int i=N-1; i>=0; i--){
if (i+k<N) ds[i]=dp[i+k];
else ds[i]=0;
ds[i]+=min(l,2*(l-a[i]));
}
long long 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";
}
ans=min(ans,min(L+ds[k],dp[n-k-1]+L));
//cout<<dp[0]<<"\n";
for (int i=0; i+k+1<n; i++){
ans=min(ans,dp[i]+L+ds[i+k+1]);
//cout<<ans<<"\n";
}
return ans;
}
signed main(){
int sm[3]={1,2,5};
cout<<delivery(3,2,8,sm);
}