Submission #287083

#	Time	Username	Problem	Language	Result	Execution time	Memory
287083		amoo_safar	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	2062 ms	28696 KiB

boxes

#include "boxes.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll Inf = 1e18;

ll delivery(int n, int k, int L, int p[]) {
	vector<int> A(n + 1), D(n + 1);
	for(int i = 1; i <= n; i++) A[i] = p[i - 1];
	sort(A.begin(), A.end());
	for(int i = 1; i <= n; i++) D[i] = min(A[i], L - A[i]);

	vector<ll> dp(n + 1, Inf);
	dp[0] = 0;
	for(int i = 1; i <= n; i++){
		for(int j = max(1, i - k + 1); j <= i; j++){
			dp[i] = min(dp[i], D[i] + D[j] + (A[i] - A[j]) + dp[j - 1]);
		}
	}
	return dp[n];
}

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