Submission #139439

#	Time	Username	Problem	Language	Result	Execution time	Memory
139439		bogdan10bos	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	864 ms	235256 KiB

boxes

/// ?
#include <bits/stdc++.h>
#include "boxes.h"

using namespace std;

typedef long long LL;

LL delivery(int N, int K, int L, int p[])
{

	sort(p, p + N);
	int cnt0 = 0;
	for(int i = 0; i < N; i++)
		if(p[i] == 0)
			cnt0++;

	if(cnt0)
	{
		for(int i = cnt0; i < N; i++)
			p[i - cnt0] = p[i];
		N -= cnt0;
	}

	vector<LL> pfx(N + 5), sfx(N + 5);
	for(int i = 0; i < N; i++)
	{
		pfx[i] = min(2LL * p[i], 1LL * L);
		if(i >= K)	pfx[i] += pfx[i - K];
	}

	for(int i = N - 1; i >= 0; i--)
	{
		sfx[i] = min(2LL * (L - p[i]), 1LL * L);
		if(i + K < N)	sfx[i] += sfx[i + K];
	}

	LL ans = sfx[0];
	for(int i = 0; i < N; i++)
		ans = min(ans, pfx[i] + sfx[i + 1]);
    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