제출 #1301845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1301845		nicolo_010	선물상자 (IOI15_boxes)	C++20	50 / 100	2101 ms	94260 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int mxN = 1e6+5;

ll memo[mxN];

vector<int> pos;

int L, k, n;

ll solve(int i) {
	if (i >= pos.size()) return 0;
	if (memo[i] != -1) return memo[i];
	ll result=1e18;
	for (int s=1; s+i<=n; s++) {
		if (s>k) break;

		int l = pos[i];
		int r = pos[i+s-1];
		ll cost = min(2*min(r, L-l), L);
		result = min(result, cost + solve(i+s));
	}
	//cout << i << " " << j << " " << result << endl;
	memo[i] = result;
	return memo[i];
}

ll delivery(int N, int K, int l, int* a) {
	n = N;
	k = K;
	L = l;
	pos.assign(n, 0);
	for (int i=0; i<n; i++) {
		pos[i] = a[i];
	}
	memset(memo, -1, sizeof(memo));
	return solve(0);
}

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