Submission #1011719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011719		pawned	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	1 ms	348 KiB

boxes

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

ll delivery(int n, int kg, int lg, int p[]) {
	ll N = n; ll K = kg; ll L = lg;
	// length is L, have N teams, distribute K at a time
	ll cut = L / 2;
	vi leftv;	// [0, cut]
	vi rightv;	// [cut + 1, L - 1];
	sort(p, p + N);
	for (int i = 0; i < N; i++) {
		if (p[i] <= cut)
			leftv.pb(p[i]);
		else
			rightv.pb(L - p[i]);
	}
	sort(leftv.begin(), leftv.end());
	sort(rightv.begin(), rightv.end());
/*	cout<<"leftv: ";
	for (ll x : leftv)
		cout<<x<<" ";
	cout<<endl;
	cout<<"rightv: ";
	for (ll x : rightv)
		cout<<x<<" ";
	cout<<endl;*/
	int X = (int)(leftv.size());
	int Y = (int)(rightv.size());
	vi pfs1(X + 1, 0);	// sum of all alternating by K, end at i - 1
	vi pfs2(Y + 1, 0);
	for (int i = 1; i <= X; i++) {
		if (i - 1 < K)
			pfs1[i] = leftv[i - 1];
		else
			pfs1[i] = pfs1[i - K] + leftv[i - 1];
	}
	for (int i = 1; i <= X; i++) {
		if (i - 1 < K)
			pfs2[i] = rightv[i - 1];
		else
			pfs2[i] = pfs2[i - K] + rightv[i - 1];
	}
	ll mincost = pfs1[X] + pfs1[Y];
	for (int i = 1; i < K; i++) {	// count remove in left
		if (X < i || Y < (K - i))
			continue;
		ll cost = L + 2 * (pfs1[X - i] + pfs2[Y - (K - i)]);
		mincost = min(mincost, cost);
	}
	return mincost;
}

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