Submission #69908

#	Time	Username	Problem	Language	Result	Execution time	Memory
69908		MatheusLealV	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	551 ms	235296 KiB

boxes

#include <bits/stdc++.h>
#define N 10000002
using namespace std;
typedef long long ll;

int n, k, l, pos[N];

ll L[N], R[N], ans = 200000000000000000;

ll delivery(int N_, int K_, int L_, int positions[])
{
	n = N_, k = K_, l = L_;

	for(int i = 1; i <= n; i++) pos[i] = positions[i - 1];

	for(int i = 1; i <= n; i++)
	{
		if(i <= k) L[i] = 2LL*(ll)pos[i];

		else L[i] = L[i - k] + 2LL*(ll)pos[i];
	}

	for(int i = n; i >= 1; i--)
	{
		if(n - i + 1 <= k) R[i] = 2LL*((ll)l - (ll)pos[i]);

		else R[i] = R[i + k] + 2LL*((ll)l -(ll) pos[i]);
	}

	ll d1 = min(pos[1], l - pos[1]), dn = min(pos[n], l - pos[n]);

	ans = min((ll)R[1] - ((ll)l - (ll)pos[1]) + (ll)d1, (ll)L[n] - (ll)pos[n] + dn);

	for(int i = 1; i < n; i++)
	{
		ll di = min(pos[i], l - pos[i]);

		ll dii = min(pos[i + 1], l - pos[i + 1]);

		ll A = (ll)L[i] - (ll)pos[i] + (ll)di;

		ll B =(ll) R[i + 1] - ((ll)l - (ll)pos[i + 1]) + dii;

		ans = min(ans, A + B);
	}

	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