제출 #1301848

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1301848		nicolo_010	선물상자 (IOI15_boxes)	C++20	10 / 100	8 ms	15944 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][2];

vector<int> pos;

int L, k, n;

ll solve(int i, int t) {
	if (i >= pos.size()) return 0;
	if (memo[i][t] != -1) return memo[i][t];
	ll result=1e18;
	int md = n%k;
	//Va a quedar un bloque de tamaño md;

	//Caso bloque de k
	if (i+k <= n) {
		int s = k;
		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, t));
	}

	//Caso bloque de md
	if (t==0 && i+md <= n) {
		int s = md;
		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, 1));
	}
	memo[i][t] = result;
	return memo[i][t];
}

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

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