Submission #292338

#	Time	Username	Problem	Language	Result	Execution time	Memory
292338		VodkaInTheJar	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	776 ms	206684 KiB

boxes

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

const int maxn = 1e7 + 3; 
const long long inf = 1e16; 

long long val1[maxn], val2[maxn];
long long best1[maxn], best2[maxn];
long long pr[maxn];
long long delivery(int n, int k, int l, int positions[])
{
	vector <int> v1, v2;
	for (int i = 0; i < n; i++)
	{
		if (positions[i] <= l / 2)
		v1.push_back(positions[i]);
		
		else
		v2.push_back(positions[i]);
	}
	
	reverse(v2.begin(), v2.end());
	
	int sz1 = (int)v1.size(), sz2 = (int)v2.size();
	for (int i = 0; i < sz1; i++)
		val1[i] = 2 * v1[i] + (i < k ? 0 : val1[i-k]);
		
	for (int i = 0; i < sz2; i++)
		val2[i] = 2 * (l - v2[i]) + (i < k ? 0 : val2[i-k]);
		
	for (int i = 0; i < k; i++)
	best1[i] = best2[i] = inf;
	
	best1[sz1 % k] = min(best1[sz1 % k], 1ll * sz1 / k * l);
	for (int i = 0; i < sz1; i++)
	{
		int left = sz1 - i - 1; 
		best1[left % k] = min(best1[left % k], val1[i] + 1ll * left / k * l);
	}
	
	best2[sz2 % k] = min(best2[sz2 % k], 1ll * sz2 / k * l);
	for (int i = 0; i < sz2; i++)
	{
		int left = sz2 - i - 1; 
		best2[left % k] = min(best2[left % k], val2[i] + 1ll * left / k * l);
	}
	
	pr[0] = best2[0];
	for (int i = 1; i < k; i++)
	pr[i] = min(pr[i-1], best2[i]);
	
	long long ans = inf; 
	for (int i = 0; i < k; i++)
	{
		if (i == 0)
		ans = min(ans, best1[i] + best2[0]);
		
		ans = min(ans, best1[i] + pr[min(k-1, k-i)] + l);
		ans = min(ans, best1[i] + pr[k-1] + 2 * l);
	}
	
	return ans; 
}

/*
int n, k, l, positions[maxn];
int main()
{
	cin >> n >> k >> l;
	for (int i = 0; i < n; i++)
	cin >> positions[i];
	
	cout << delivery(n, k, l, positions) << endl; 
}
*/

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