Submission #1178736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178736		goduadzesaba	Boxes with souvenirs (IOI15_boxes)	C++20	10 / 100	0 ms	328 KiB

boxes

#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);
}*/

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30