Submission #1301831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301831		nicolo_010	선물상자 (IOI15_boxes)	C++20	20 / 100	25 ms	24224 KiB

boxes

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

const int mxN = 1005;

ll memo[mxN][mxN][3];

int L;
int n;
int k;

vector<int> pos;

ll solve(int l, int cnt, int t) {
	int r = (l+n-1)-cnt;
	//cout << l << " " << r << " " << cnt << endl;
	if (cnt==n) return 0;
	if (memo[l][cnt][t] != -1) return memo[l][cnt][t];
	ll result = 1e18;
	int idx;
	if (cnt%k==0) {
		idx=0;
	}
	else {
		if (t==0) {
			idx=0;
		}
		else if (t==1) {
			idx = pos[l-1];
		}
		else {
			idx = pos[r+1];
		}
	}
	//Caso voy a l
	ll extra = (((cnt+1)%k==0 || (cnt+1)==n) ? min(pos[l], abs(L-pos[l])) : 0);
	ll costl;
	if (idx <= pos[l]) costl = pos[l]-idx;
	else costl = idx+pos[l];
	costl += extra;
	result = min(result, costl+solve(l+1, cnt+1, 1));

	//Caso voy desde r
	extra = (((cnt+1)%k==0 || (cnt+1)==n) ? min(pos[r], abs(L-pos[r])) : 0);
	ll costr;
	if (idx >= pos[r]) costr = idx-pos[r];
	else costr = idx+L-pos[r];
	costr += extra;
	result = min(result, costr+solve(l, cnt+1, 2));

	memo[l][cnt][t] = result;
	return result;
}

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, 0, 0);
}

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