# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
639385 | Benmath | Boxes with souvenirs (IOI15_boxes) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "boxes.h"
using namespace std;
long long delivery(int N, int K, int L, int p[]) {
long long int dp1[N];
long long int dp2[N];
dp1[0]=p[0];
int t1=-1;
for(int i=0;i<N;i++){
if(p[i]!=0){
t1=i;
break;
}
}
if(t1==-1){
return 0;
}
for(int i=1;i<N;i++){
if(i>=K){
long long int r=min(p[i-K],L-p[i-K]);
r=r+p[i;
dp1[i]=dp1[i-K]+r;
}else{
long long int r=p[i]-p[i-1];
dp1[i]=dp1[i-1]+r;
}
}
dp2[N-1]=L-p[N-1];
for(int i=N-2;i>=0;i--){
int j=N-1-i;
if(j>=K){
long long int r=min(p[i+K],L-p[i+K]);
r=r+L-p[i];
dp2[i]=dp2[i+K]+r;
}else{
long long int r=p[i+1]-p[i];
dp2[i]=dp2[i+1]+r;
}
}
long long int so1=min(p[N-1],L-p[N-1]);
so1=so1+dp1[N-1];
long long int so2=min(p[0],L-p[0]);
so2=so2+dp2[0];
long long int ans=min(so1,so2);
for(int i=0;i<(N-1);i++){
long long int ro1=min(p[i],L-p[i]);
ro1=ro1+dp1[i];
long long int ro2=min(p[i+1],L-p[i+1]);
ro2=ro2+dp2[i+1];
long long int ro=ro1+ro2;
ans=min(ans,ro);
}
return ans;
}
/*
int main(){
int n,k,l;
cin>>n>>k>>l;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<delivery(n,k,l,arr);
}
*/