Submission #1301844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301844		nicolo_010	Boxes with souvenirs (IOI15_boxes)	C++20	50 / 100	810 ms	16168 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];

vector<int> pos;

int L, k, n;

ll solve(int i, int j) {
	if (i >= pos.size()) return 0;
	if (memo[i][j] != -1) return memo[i][j];
	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, i));
	}
	//cout << i << " " << j << " " << result << endl;
	memo[i][j] = result;
	return memo[i][j];
}

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: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30