Submission #394431

#	Time	Username	Problem	Language	Result	Execution time	Memory
394431		rainboy	Boxes with souvenirs (IOI15_boxes)	C11	100 / 100	621 ms	293752 KiB

boxes

#include "boxes.h"

#define N	10000000

long long min(long long a, long long b) { return a < b ? a : b; }

long long delivery(int n, int k, int l, int *pp) {
	static long long dp[N], dq[N];
	int i;
	long long ans;

	for (i = 0; i < n; i++)
		dp[i] = (i >= k ? dp[i - k] : 0) + min(pp[i] * 2, l);
	for (i = n - 1; i >= 0; i--)
		dq[i] = (i + k < n ? dq[i + k] : 0) + min((l - pp[i]) * 2, l);
	ans = min(dp[n - 1], dq[0]);
	for (i = 0; i + 1 < n; i++)
		ans = min(ans, dp[i] + dq[i + 1]);
	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