Submission #346834

#	Time	Username	Problem	Language	Result	Execution time	Memory
346834		1bin	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	605 ms	287212 KiB

boxes

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
ll x, ans;
vector<ll> arr, A, B;

ll delivery(int N, int K, int L, int positions[]) {
	arr.resize(N + 2);
	for (int i = 1; i <= N; i++) arr[i] = positions[i - 1];
	A.resize(N + 2); B.resize(N + 2);
	for (int i = 0; i <= N; i++) {
		if (i <= K) A[i] = arr[i] * 2;
		else A[i] = arr[i] * 2 + A[i - K];
	}
	
	for (int i = N; i; i--) {
		if (i >= N + 1 - K) B[i] = (L - arr[i]) * 2;
		else B[i] = (L - arr[i]) * 2 + B[i + K];
	}
	ans = 198765432198765432;
	for (int i = 0; i <= N; i++)
		ans = min(ans, A[i] + B[i + 1]);
	for (int i = 0; i <= N; i++) {
		if(i + 1 + K <= N + 1)
			ans = min(ans, A[i] + L + B[i + 1 + K]);
	}
	return ans;
}

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