Submission #595525

#	Time	Username	Problem	Language	Result	Execution time	Memory
595525		Apiram	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	518 ms	216652 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
long long delivery(int N, int K, int L, int p[]) {
	 if (K == 1){
		 long long ans = 0;
		for (int i = 0;i<N;++i){
			ans +=min(p[i],L - p[i]) * 2;
		}
		return ans;
	 }
	 else if (K == N){
		long long ans = min({L,(L - p[0]) * 2,p[N - 1] * 2});
		for (int i = 0;i<N - 1;++i){
			ans = min(ans,(long long)p[i] * 2 + (L - p[i + 1]) * 2);
		}
		return ans;
	 }
	 else{
		 const long long mxn = 1e18;
		 long long ans = mxn;
		 vector<long long>l(N + 1,mxn),r(N + 1,mxn);
		 l[0] = 0;
		 r[0] = 0;
		 for (int i = 1;i<=N;++i){
			int temp = max(i - K,0);
			l[i] = l[temp] + (p[i - 1]) * 2;
			r[i] = r[temp] + (L - p[N - i]) * 2; 	
		 }
		 for (int i = 0;i<=N;++i){
			ans = min(ans,l[i] + r[N - i]);
			if (N - i - K>=0){
				ans = min(ans,l[i] + r[N - i - K] + L);
			}
		 }
		 return ans;
	 //first compute the total distance we have to travel to satisfy the teams
	 }
    return 0;
}

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