Submission #489359

#	Time	Username	Problem	Language	Result	Execution time	Memory
489359		ssense	Boxes with souvenirs (IOI15_boxes)	C++14	0 / 100	0 ms	204 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 = 1005;
ll cw[N];
ll ccw[N];

long long delivery(int n, int k, int l, int a[])
{
	int cnt = 0;
	for(int i = 0; i < n; i++)
	{
		if(a[i] == 0)
		{
			a[i] = MX+1;
			cnt++;
		}
	}
	sort(a, a+n);
	n = n-cnt;
	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)
		{
			ll option = ccw[0]+l-a[0];
			ans = min(ans, option);
			continue;
		}
		if(i == n)
		{
			ll option = cw[n-1]+a[n-1];
			ans = min(ans, option);
			continue;
		}
		ll option = cw[i]+ccw[i+1]+a[i]+l-a[i+1];
		ans = min(ans, option);
	}
	if(k >= n)
	{
		ans = min(ans, l*1LL);
	}
	else
	{
		for(int i = k-1; i < n; i++)
		{
			if(i-k == -1)
			{
				ll option = l+ccw[i+1]+l-a[i+1];
				ans = min(ans, option);
				continue;
			}
			if(i == n-1)
			{
				ll option = cw[i-k]+a[i-k]+l;
				ans = min(ans, option);
				continue;
			}
			ll option = cw[i-k]+ccw[i+1]+a[i]+l-a[i+1]+l;
			ans = min(ans, option);
		}
	}
	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
 
4 3 8
1 3 4 6
 */

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