Submission #1202077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202077		alind	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	345 ms	196172 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

long long delivery(int N, int K, int L, int p[]) {
	vector<ll> pref(N), suf(N);
	for (int i = 0, j = N - 1; ~j && i < N; i++, j--) {
		pref[i] = 2ll * p[i] + (i < K ? 0ll : pref[i - K]);
		suf[j] = 2ll * (L - p[j]) + (i < K ? 0ll : suf[j + K]);
	}
	ll mn = 1ll<<62;
//	if (K >= N) mn = min({pref[N-1], suf[0], (ll)L});
//	for (auto x : pref) cerr << x << ' '; cerr << '\n';
//	for (auto x : suf) cerr << x << ' '; cerr << '\n';
	for (int i = -1; i < N; i++) mn = min(mn, (~i ? pref[i] : 0ll) + (i < N - 1 ? suf[i+1] : 0ll));
	for (int i = 0; i + K <= N; i++) mn = min(mn, L + (i ? pref[i-1] : 0ll) + (i + K < N ? suf[i + K] : 0ll));
//	cerr << mn << '\n';
	return mn;
}

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