Submission #1284659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284659		kustov_vadim_533	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	285 ms	117824 KiB

boxes

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

long long delivery(int N,int K,int L,int positions[]){
	vector<ll> dp(N + 1, 1e18);
	dp[0] = 0;
	for (int i = 0; i < N; ++i){
		dp[i + 1] = min(dp[i + 1], positions[i] * 2ll + dp[max(0, i - K + 1)]);
		dp[i + 1] = min(dp[i + 1], L + dp[max(0, i - K + 1)]);
		dp[i + 1] = min(dp[i + 1], 2ll * (L - positions[max(0, i - K + 1)]) + dp[max(0, i - K + 1)]);
	}

	ll ans = dp[N];
	for (int i = 1; i <= K && i <= N; ++i){
		ans = min(ans, 2ll * (L - positions[N - i]) + dp[N - i]);
	}

	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