Submission #1301834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301834		nicolo_010	Boxes with souvenirs (IOI15_boxes)	C++20	15 / 100	2095 ms	580 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;

vector<int> pos;

int l, k, n;

ll solve(vector<int> &p) {
	int idx=0;
	int cnt=0;
	ll ans=0;
	for (int i=0; i<n; i++) {
		int a = p[i];
		int cost;
		if (idx <= pos[a]) cost = pos[a]-idx;
		else cost = idx+pos[a];
		if (idx >= pos[a]) cost = min(cost, idx-pos[a]);
		else cost = min(cost, idx+l-pos[a]);
		//cout << i << " " << idx << " " << a << " " << pos[a] << " " << cost << endl;
		cnt++;
		ans += cost;
		idx = pos[a];
		if (cnt==k) {
			cnt=0;
			ans += min(idx, l-idx);
			idx = 0;
		}
	}
	return ans+min(idx, l-idx);
}

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];
	}
	ll ans=1e18;
	vector<int> p(n);
	for (int i=0; i<n; i++) p[i] = i;
	ans = solve(p);
	//cout << endl;
	while (next_permutation(p.begin(), p.end())) {
		ans = min(ans, solve(p));
	}
	return ans;
}

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