Submission #1181381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181381		boclobanchat	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	346 ms	196164 KiB

boxes

#include"boxes.h"
#include<bits/stdc++.h>
using namespace std;
const long long INF=1e18;
long long delivery(int N,int K,int L,int p[])
{
	vector<long long> dpl(N),dpr(N);
	for(int i=0;i<N;i++)
	{
		dpl[i]=p[i]*2;
		if(i>=K) dpl[i]+=dpl[i-K];
	}
	for(int i=N-1;i>=0;i--)
	{
		dpr[i]=(L-p[i])*2;
		if(i+K<N) dpr[i]+=dpr[i+K];
	}
	long long ans=min(dpl[N-1],dpr[0]);
	for(int i=0;i+1<N;i++) ans=min(ans,dpl[i]+dpr[i+1]);
	for(int i=0;i+K-1<N;i++)
	{
		long long sum=L;
		if(i) sum+=dpl[i-1];
		if(i+K<N) sum+=dpr[i+K];
		ans=min(ans,sum);
	}
    return ans;
}

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