Submission #1259149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259149		JuanJL	Boxes with souvenirs (IOI15_boxes)	C++20	35 / 100	1 ms	328 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i< b;i++)
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;


long long delivery(int N, int K, int L, int p[]) {
	ll left = 0;
	ll lleft = 0;
	ll right = 0;
	ll lright= 0;
	
	
	map<ll,ll> m;
	forn(i,0,N) if(p[i]!=0)m[p[i]]++;
	
	vector<pair<ll,ll>> v; 
	v.pb({0,0});
	for(auto i:m) v.pb(i);
	sort(ALL(v));
	
	
	forn(i,0,SZ(v)){
		if(v[i].fst<=L/2) right+=v[i].snd,lright=i;
		else left+=v[i].snd;
	}
	v.pb({L,0});
	
	//cout<<left<<" "<<right<<'\n';
	
	lleft=lright+1;
	
	//cout<<lleft<<" "<<lright<<'\n';
	
	ll res = 0;
	ll k=K;
	
	while(right>=k){
		k=K;
		right-=k;
		res+=v[lright].fst*2;
		
		for(int  i = (int)lright; i>=0; i--){
			
			ll aux =min(v[i].snd,k);
			v[i].snd-=aux;
			k-=aux;
			
			if(k==0 && (v[i].snd>0||i==0)){
				lright=i;
				break;
			}
		}	
		k=K;	
	}//cout<<res<<'\n';
	
	
	k=K;
	while(left>=k){
		k = K;
		left-=k;
		res+=(L-v[lleft].fst)*2;
		
		for(int  i = (int)lleft; i<SZ(v); i++){
			
			ll aux =min(v[i].snd,k);
			v[i].snd-=aux;
			k-=aux;
			
			if(k==0 && (v[i].snd>0||i==(SZ(v)-1))){
				lleft=i;
				break;
			}
		}		
		k=K;
	}
	
	//cout<<res<<'\n';
	
	ll presL = 0;
	ll aux = (L-v[lleft].fst)*2;
	presL=aux + v[lright].fst*2;
	ll newpresL = L; 
	k=K; k-=left;
	if(k<right){ 
		ll raux = 0;
		for(int i = (int)lright; i>=0; i--){
			raux+=v[i].snd;
			if(raux>k){
				newpresL+=v[i].fst*2;
				break;
			}
		}
	}
	
	presL=min(presL,newpresL);
	
	
	ll presR = 0;
	aux = (v[lright].fst)*2;
	presR=aux + (L-v[lleft].fst)*2;
	ll newpresR = L; 
	k=K; k-=right;
	if(k<left){ 
		ll raux = 0;
		for(int i = (int)lleft; i<SZ(v); i++){
			raux+=v[i].snd;
			if(raux>k){
				newpresR+=v[i].fst*2;
				break;
			}
		}
	}
	
	presR=min(presR,newpresR);
	/*cout<<res<<'\n';
	cout<<presL<<" "<<presR<<'\n';*/
	return res+min(presL,presR);
	
    return 0;
}

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