Submission #432964

#	Time	Username	Problem	Language	Result	Execution time	Memory
432964		vanic	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	926 ms	238924 KiB

boxes

#include "boxes.h"
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

typedef long long ll;

const int maxn=1e7+5;

ll dp1[maxn], dp2[maxn];

ll delivery(int n, int k, int l, int p[]) {
	sort(p, p+n);
	for(int i=0; i<n; i++){
		dp1[i+1]=dp1[max(i+1-k, 0)]+p[i]*2;
	}
	for(int i=n-1; i>-1; i--){
		dp2[i]=dp2[min(n, i+k)]+(l-p[i])*2;
	}
	ll mini=1e18;
	for(int i=0; i<=n; i++){
		mini=min(mini, dp1[i]+dp2[i]);
		mini=min(mini, dp1[i]+dp2[min(n, i+k)]+l);
	}
	return mini;
}

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