Submission #1017415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017415		parsadox2	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	1 ms	2396 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"

using namespace std;

const int N = 1e7 + 2;
int n , k , len , bord;
long long L[N] , R[N];

long long delivery(int nn, int kk, int ll, int p[]) {
	n = nn;
	k = kk;
	len = ll;
	bord = -1;
	long long ans = 1e18;
	for(int i = 0 ; i < n ; i++)
	{
		L[i] = 2 * p[i];
		if(i >= k)
			L[i] += L[i - k];
		if(2 * p[i] >= len && bord == -1)
			bord = i;
		ans = min(ans , L[i] + 1LL * len * ((n - i + k) / k));
	}
	for(int i = n - 1 ; i >= 0 ; i--)
	{
		R[i] = 2 * (len - p[i]);
		if(i + k < n)
			R[i] += R[i + k];
		ans = min(ans , R[i] + 1LL * len * ((i + k - 1) / k));
	}
	for(int l = 0 ; l < bord ; l++)
	{
		long long res = 0;
		res += L[l];
		int tmp = (bord - l - 1 + k - 1) / k;
		res += 1LL * tmp * len;
		if(l + tmp * k + 1 < n)
			res += R[l + tmp * k + 1];
		ans = min(ans , res);
	}
	return ans;
}

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