Submission #517025

#	Time	Username	Problem	Language	Result	Execution time	Memory
517025		pavement	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	1 ms	296 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll pref[100005], suff[100005], pp[100005];

ll delivery(int N, int K, int L, int p[]) {
	for (int i = 0; i < N; i++) {
		if (i % K == 0) pref[i] = (i ? (ll)pref[i - 1] : 0ll) + 2ll * p[i];
		else pref[i] = (ll)pref[i - 1] - 2ll * p[i - 1] + 2ll * p[i];
	}
	for (int i = N - 1; i >= 0; i--) {
		if ((N - i - 1) % K == 0) suff[i] = (i + 1 < N ? (ll)suff[i + 1] : 0ll) + 2ll * (L - p[i]);
		else suff[i] = (ll)suff[i + 1] - 2ll * (L - p[i + 1]) + 2ll * (L - p[i]);
	}
	ll ret = pref[N - 1];
	for (int i = 0; i < N; i++) pp[i] = (ll)(i ? pp[i - 1] : 0) + p[i];
	for (int i = N - 1, pt = N; i >= 0; i--) {
		while (i < pt && (pp[pt - 2] - pp[i - 1] + K - 1) / K * N + suff[pt - 1] <= (pp[pt - 1] - pp[i - 1] + K - 1) / K * N + suff[pt]) pt--;
		ret = min(ret, pref[i - 1] + (pp[pt - 1] - pp[i - 1] + K - 1) / K * N + suff[pt]);
	}
	return ret;
}

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