Submission #1278715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278715		IBory	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	394 ms	274828 KiB

boxes

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int MAX = 10000007;
ll P[MAX], L[MAX], R[MAX];

ll delivery(int N, int K, int M, int* _P) {
	for (int i = 1; i <= N; ++i) L[i] = P[i] = _P[i - 1];

	for (int i = 1; i <= N; ++i) if (K <= i) L[i] += L[i - K];
	P[N + 1] = M;
	for (int i = N + 1; i > 0; --i) {
		R[i] = M - P[i];
		if (i + K <= N + 1) R[i] += R[i + K];
	}

	ll ret = 1e18;
	for (int i = 0; i <= N; ++i) ret = min(ret, 2 * (L[i] + R[i + 1]));
	for (int i = 1; i + K <= N + 1; ++i) {
		ret = min(ret, M + (L[i - 1] + R[i + K]) * 2);
	}

	return ret;
}

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