Submission #860728

#	Time	Username	Problem	Language	Result	Execution time	Memory
860728		happypotato	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	639 ms	349788 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
int n, k, l;
vector<int> v;
vector<int> asc, desc;
long long delivery(int32_t N, int32_t K, int32_t L, int32_t p[]) {
	l = L; v.clear(); v.pb(-1);
	for (int i = 0; i < N; i++) if (p[i] > 0) v.pb(p[i]);
	sort(v.begin(), v.end());
	n = (int)(v.size()) - 1; k = min((int)(K), n);
	asc.resize(n + 2); desc.resize(n + 2);
 
	// ascending: min(l, a[rb] * 2) -> only care about rb
	asc[0] = 0; asc[n + 1] = 1e18;
	for (int i = 1; i <= n; i++) {
		asc[i] = (i <= k ? 0LL : asc[i - k]) + v[i] + min(l - v[i], v[i]);
	}
 
	// descending: min(l, (l - a[lb]) * 2) -> only care about lb
	desc[n + 1] = 0; desc[0] = 1e18;
	for (int i = n; i >= 1; i--) {
		desc[i] = (i > n - k ? 0LL : desc[i + k]) + (l - v[i]) + min(l - v[i], v[i]);
	}
 
	int ans = 1e18;
	for (int i = 0; i <= n; i++) {
		ans = min(ans, asc[i] + desc[i + 1]);
	}
 
	return ans;
}
#undef int

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