Submission #71186

#	Time	Username	Problem	Language	Result	Execution time	Memory
71186		fallingstar	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	2 ms	376 KiB

boxes

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

using namespace std;

#define long long long

const int N = 2e7 + 2;

long fsuff[N], fpref[N];

long delivery(int n, int k, int L, int p[]) {
	int head = 0;
	while (head < n && p[head] == 0) ++head;

	long res = (long) (n - head + k - 1) / k * L;

	for (int i = n - 1; i >= head; --i)
		fsuff[i] = fsuff[i + k] + (L - p[i]) * 2;

	int r = head;
	while (r < n && fsuff[r] > fsuff[r + k] + L) r += k;

	for (int i = head; i < n; ++i)
	{
		fpref[i] = (i < k ? 0 : fpref[i - k]) + p[i] * 2;
	
		#define eval(x) (fsuff[x] + (long) (x - i - 1 + k - 1) / k * L)

		while (r > i + 1 && eval(r - 1) < eval(r)) --r;
		while (r < n && eval(r + 1) < eval(r)) ++r;

		res = min(res, fpref[i] + eval(r));
		#undef eval
	}
    return res;
}

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