Submission #645018

#	Time	Username	Problem	Language	Result	Execution time	Memory
645018		as111	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	551 ms	278328 KiB

boxes

#include "boxes.h"

#include <set>

#define MAXN 10000000

using namespace std;

long long dp1[MAXN + 5]; // clockwise, 1 based
long long dp2[MAXN + 5]; // counterclockwise
long long delivery(int N, int K, int L, int p[]) {
	dp1[0] = 0;
	for (int i = 1; i <= N; i++) { // to the left
		int prev = max(0, i - K);
		dp1[i] = dp1[prev] + min(L - p[i - 1], p[i - 1]); // prev here refers to team before the K
		if (prev == 0) {
			dp1[i] += p[i - 1];
		}
		else {
			dp1[i] += p[i - 1] - p[prev] + min(L - p[prev], p[prev]); // prev here refers to part of the K
		}
		
	}
	dp2[N+1] = 0;
	for (int i = N; i >=0; i--) { // to the right
		int prev = min(N + 1, i + K);
		dp2[i] = dp2[prev] + min(L - p[i - 1], p[i - 1]);
		if (prev == N + 1) {
			dp2[i] += L - p[i - 1];
		}
		else {
			dp2[i] += p[prev - 2] - p[i - 1] + min(L - p[prev - 2], p[prev - 2]);
		}
	}
	long long ans = 10e16;
	for (int i = 0; i <= N; i++) {
		ans = min(ans, dp1[i] + dp2[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