Submission #431683

#	Time	Username	Problem	Language	Result	Execution time	Memory
431683		frodakcin	Boxes with souvenirs (IOI15_boxes)	C++11	100 / 100	628 ms	243476 KiB

boxes

#include "boxes.h"
#include <vector>

template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}

using ll = long long;
const ll INF = 0x3f3f3f3f3f3f3f3f;

long long delivery(int N, int K, int L, int p[]) {
	std::vector<ll> gl(N+1), gr(N+1);
	for(int i=0;i<N;++i)
	{
		gl[i+1]=p[i]*2;
		if(i>=K) gl[i+1]+=gl[i+1-K];
	}
	for(int i=0;i<N;++i)
	{
		gr[i+1]=(L-p[N-1-i])*2;
		if(i>=K) gr[i+1]+=gr[i+1-K];
	}
	ll ans=INF;
	// no cross:
	for(int i=0;i<=N;++i)
		ckmin(ans, gl[i]+gr[N-i]);
	//cross:
	if(K>=N) ckmin(ans, (ll)L);
	else
		for(int i=0;i<=N-K;++i)
			ckmin(ans, gl[i]+gr[N-K-i]+L);
	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