Submission #381806

#	Time	Username	Problem	Language	Result	Execution time	Memory
381806		idontreallyknow	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	581 ms	294124 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[]) {
    if (L == 1) return 0;
	vector<ll> left(N+5), right(N+5);
	int l = -K+1;
	for (int q = 1; q <= N; q++) {
		left[q] = 2*p[q-1];
		if (l > 0) left[q] += left[l];
		l++;
	}
	int r = N+K;
	for (int q = N; q > 0; q--) {
		right[q] = 2*(L-p[q-1]);
		if (r <= N) right[q] += right[r];
		r--;
	}
	ll ans = LLONG_MAX;
	for (int q = 0; q <= N; q++) {
		ans = min(ans, left[q]+right[q+1]);
	}
	for (int q = 1; q < N; q++) {
		int ri = min(q+K,N+1);
		ans = min(ans, left[q-1]+L+right[ri]);
	}
	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