Submission #519290

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

boxes

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

typedef long long ll;

int start;
ll ans, pf[1000005], sf[1000005];

ll delivery(int N, int K, int L, int p[]) {
	start = N;
	for (int i = 0; i < N; i++)
		pf[i] = (i - K >= 0 ? pf[i - K] : 0ll) + 2ll * (ll)p[i];
	for (int i = N - 1; i >= 0; i--)
		sf[i] = (i + K < N ? sf[i + K] : 0ll) + 2ll * (ll)(L - p[i]);
	for (int i = 0; i < N; i++) {
		if ((ll)L + (i > 0 ? pf[i - 1] : 0ll) < (ll)pf[min(N - 1, i + K - 1)]) {
			start = i;
			break;
		}
	}
	ans = LLONG_MAX;
	for (int i = 0; i <= N; i++) ans = min(ans, (ll)(i ? pf[i - 1] : 0) + (ll)sf[i]);
	for (int i = start; i <= N; i += K)
		ans = min(ans, (start > 0 ? pf[start - 1] : 0ll) + sf[i] + (ll)(i - start) / (ll)K * (ll)L);
	return ans;
}

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