Submission #287090

#	Time	Username	Problem	Language	Result	Execution time	Memory
287090		amoo_safar	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	903 ms	221804 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);
	deque< pair<int, ll> > dq;
	dp[0] = 0;
	dq.push_back({1, dp[0] + D[1] - A[1]});
	for(int i = 1; i <= n; i++){
		while(dq.front().first < i - k + 1) dq.pop_front();

		dp[i] = dq.front().second + D[i] + A[i];
		if(i == n) break;
		pair<int, ll> nw = {i + 1, dp[i] + D[i + 1] - A[i + 1]};
		while(!dq.empty() && dq.back().second >= nw.second)
			dq.pop_back();
		dq.push_back(nw);
	}
	return dp[n];
}

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