제출 #371016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
371016		peijar	선물상자 (IOI15_boxes)	C++17	100 / 100	1326 ms	450464 KiB

boxes

#include "boxes.h"

#include <bits/stdc++.h>
#define SZ(v) ((int)(v).size())
using namespace std;

using ll = long long;

ll delivery(int N, int K, int L, int p[]) 
{	
	ll sol(1e18);
	
	vector<ll> increasing(N), decreasing(N);
	for (int i(0); i < N; ++i)
		increasing[i] = decreasing[i] = p[i];
	sort(increasing.begin(), increasing.end());
	sort(decreasing.rbegin(), decreasing.rend());

	vector<ll> getInc(N), getDec(N);
	for (int i(0); i < N; ++i)
	{
		getInc[i] = 2 * increasing[i];
		getDec[i] = 2 * (L - decreasing[i]);
		if (i >= K)
		{
			getInc[i] += getInc[i-K];
			getDec[i] += getDec[i-K];
		}
	}

	for (int takeInc(0); takeInc <= N; ++takeInc)
	{
		ll cost(0);
		if (takeInc)
			cost += getInc[takeInc-1];
		if (takeInc < N)
			cost += getDec[N - takeInc-1];	
		sol = min(sol, cost);
	}
	
	for (int takeInc(0); takeInc < N; ++takeInc)
	{
		ll cost(0);
		if (takeInc)
			cost += getInc[takeInc-1];
		cost += L;
		if (takeInc + K < N)
			cost += getDec[N - takeInc - K - 1];
		sol = min(sol, cost);
	}

	return sol;
}

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