boxes.cpp

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

using namespace std;

const int MAXN = 5<<22;

long long pref[MAXN], suff[MAXN];

long long delivery(int n, int k, int l, int p[])
{
	int i;
	
	for (i = 0; i < k; ++i)
		pref[i + 1] = 2 * p[i];
	for (i = k; i < n; ++i)
		pref[i + 1] = pref[i + 1 - k] + 2 * p[i];
	for (i = n - 1; i >= n - k; --i)
		suff[i] = min(l, 2 * (l - p[i]));
	for (i = n - k - 1; i >= 0; --i)
		suff[i] = suff[i + k] + min(l, 2 * (l - p[i]));
	
	long long sol = 1ll<<60;
	
	for (i = 0; i <= n; ++i)
	{
		if (pref[i] + suff[i] < sol)
			sol = pref[i] + suff[i];
	}
	
	return sol;
}