Submission #588424

#	Time	Username	Problem	Language	Result	Execution time	Memory
588424		Temmie	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	725 ms	94656 KiB

boxes

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

long long dist(long long place, int L) {
	return std::min(place, (long long) L - place);
}

struct Range {
	int l, r;
	long long get(int L, int pos[]) {
		long long res = dist(pos[l], L) + dist(pos[r], L);
		int pl = pos[l];
		int pr = pos[r];
		if (pl > pr) {
			std::swap(pl, pr);
		}
		res += pr - pl;
		return res;
	}
};

long long delivery(int n, int k, int L, int pos[]) {
	std::sort(pos, pos + n);
	long long ans = 1LL << 60;
	for (int sl = k; sl > 0; sl--) {
		long long now = 0;
		int l = sl;
		std::vector <std::pair <int, int>> here;
		{
			here.emplace_back(0, l - 1);
			Range range = { 0, l - 1 };
			now += range.get(L, pos);
		}
		while (l < n) {
			int r = std::min(l + k - 1, n - 1);
			here.emplace_back(l, r);
			Range range = { l, r };
			now += range.get(L, pos);
			l += k;
		}
		ans = std::min(ans, now);
	}
	return ans;
}

//int main() {
	//int a[3] = { 1, 2, 5 };
	//std::cout << delivery(3, 2, 8, a) << std::endl;
//}

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