Submission #489353

#	Time	Username	Problem	Language	Result	Execution time	Memory
489353		ssense	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	1 ms	332 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define nax 200005
#define pb push_back
#define sc second
#define fr first
//#define int unsigned long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
const int N = 100005;
ll cw[N];
ll ccw[N];

long long delivery(int n, int k, int l, int a[])
{
	sort(a, a+n);
	for(int i = 0; i < n; i++)
	{
		if(i%k == 0)
		{
			int last = 0;
			if(i != 0)
			{
				last = a[i-1];
			}
			cw[i] = last+a[i];
		}
		else
		{
			cw[i] = cw[i-1]+a[i]-a[i-1];
		}
	}
	for(int i = n-1; i >= 0; i--)
	{
		if((n-1-i)%k == 0)
		{
			int last = l;
			if(i != n-1)
			{
				last = a[i+1];
			}
			ccw[i] = l-last+l-a[i];
		}
		else
		{
			ccw[i] = ccw[i+1]+a[i+1]-a[i];
		}
	}
	long long ans = MXL;
	for(int i = 0; i <= n; i++)
	{
		if(i == 0)
		{
			ans = min(ans, ccw[0]+l-a[0]);
			continue;
		}
		if(i == n)
		{
			ans = min(ans, cw[n-1]+a[n-1]);
			continue;
		}
		ans = min(ans, cw[i]+ccw[i+1]+a[i]+l-a[i+1]);
	}
	if(k >= n)
	{
		ans = min(ans, l*1LL);
	}
	else
	{
		for(int i = k-1; i < n; i++)
		{
			if(i-k == -1)
			{
				ans = min(ans, l+ccw[i+1]+l-a[i+1]);
				continue;
			}
			if(i == n-1)
			{
				ans = min(ans, cw[i-k]+a[i-k]+l);
				continue;
			}
			ans = min(ans, cw[i-k]+ccw[i+1]+a[i]+l-a[i+1]+l);
		}
	}
	return ans;
}
/*
int main()
{
	int n, k, l;
	cin >> n >> k >> l;
	int a[n];
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	cout << delivery(n, k, l, a) << endl;
}
*/
/*
3 2 8
1 2 5
 */

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