Submission #1015615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015615		Muhammet	Boxes with souvenirs (IOI15_boxes)	C++17	20 / 100	1 ms	480 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
 
#define N 10005
#define ll long long
 
using namespace std;

ll p[N], s[N];

ll delivery(int n, int k1, int l1, int a[]) {
	sort(a,a+n);
	ll x = l1, k = k1;
	for(int i = 0; i < n; i++){
		p[i+1] = a[i] + p[max(i-k+1,0ll)];
	}
	for(int i = n-1; i >= 0; i--){
		s[i+1] = (x-a[i]) + s[min(i+k+1,(ll)(n+1))];
	}
	ll ans = LLONG_MAX;
	int ind = 0;
	for(int i = 0; i <= n; i++){
		if(2*(p[i] + s[i+1]) < ans) ind = i;
		ans = min(ans,2*(p[i] + s[i+1]));
	}
	int l = ind, r = ind+1;
	ll y = ans, cnt = 0;
	while(l > 0 or r < n+1){
		if((l == 0) or (s[r]-s[r+1] > p[l]-p[l-1])){
			y -= 2*(s[r]-s[r+1]);
			r++;
		}
		else {
			y -= 2*(p[l]-p[l-1]);
			l--;
		}
		cnt++;
		ll z = cnt;
		z += (k-1);
		z /= k;
		z *= x;
		ans = min(ans, y + z);
	}
	return ans;
}

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