제출 #1242303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242303		tkm_algorithms	선물상자 (IOI15_boxes)	C++20	10 / 100	0 ms	328 KiB

boxes

/**
*    In the name of Allah
*    We are nothing and you're everything
*    Ya Muhammad!
**/
#include <bits/stdc++.h>
#include "boxes.h"
 
using namespace std;
using ll = long long;
using ull = uint64_t;
 
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int long long

const char nl = '\n';

long long delivery(int n, int k, int L, int p[]) {
	ll res = 0;
	vector<ll> l;
	for (int i = 0; i < n; ++i) {
		if (p[i]>(L+1)/2)break;
		if (i+1 <= k)l.push_back(p[i]*2);
		else l.push_back(l[sz(l)-k-1]+p[i]*2);
		res = l.back();
	}
	
	ll back = 0;
	vector<ll> r;
	for (int i = n-1; i >= 0; --i) {
		if (p[i] <= (L+1)/2)break;
		if (n-i <= k)r.push_back((L-p[i])*2);
		else r.push_back(r[sz(r)-k-1]+(L-p[i])*2);
		back = r.back();
	}
	
	res += back;
	
	for (int i = 0; i < sz(l); ++i) {
		for (int j = sz(r)-1; j >= 0; --j) {	
			if (sz(l)-i+sz(r)-j > k)continue;
			res = min(res, (i>0?l[i-1]:0ll)+L+(j-1>=0?r[j-1]:0ll));
		}
	}
    return res;
}

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