Submission #783296

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

boxes

#include <bits/stdc++.h>
#include <boxes.h>
using namespace std;
 
#define sz(x) (int) x.size()
#define dbg(x) cout << #x << ": " << x << endl;
 
using ll = long long;
 
long long delivery(int N, int K, int L, int p[]){
	sort(p, p+N);
	
	// SUBTASK 1
	if(K == 1){
		ll ans = 0;
		for(int i=0; i<N; ++i){
			ans += min(p[i], L - p[i]) * 2;
		}
		return ans;	
	}
	
	// SUBTASK 2
	if(K == N){
		ll ans = 2e9+5;
		
		// opcion 1 - desde izquierda voy y regreso hasta el final
		ans = p[N-1] * 2;
		
		// opcion 2 - desde derecha voy y regreso hasta el comienzo
		ans = min(ans, (L - p[0])*2ll);
		
		// opcion 3 - vuelta completa
		ans = min(ans, 1ll*L);
		
		// opcion 4 - voy por la izquierda hasta cierto punto, vuelvo y voy desde la derecha hasta donde me faltaba
		if(N > 1){ 
			for(int i=0; i+1<N; ++i){
				ll x = p[i];
				ll y = p[i+1];
				ans = min(ans, 2*x + 2*(L - y));
			}
		}
		return ans;
	}
	
	// SUBTASK 3
	if(N <= 20){
		ll ans = 4e18;
		for(int mask=0; mask<(1<<N); ++mask){
			// 0 -> from left
			// 1 -> from right
			
			ll res = 0;
			
			vector<int> left, right;
			for(int i=0; i<N; ++i){
				if((1<<i) & mask){
					right.push_back(p[i]);
				} else {
					left.push_back(p[i]);
				}
			}
			
			// left
			ll cur = K;
			ll prev = 0;
			for(int pos : left){
				if(cur == 0){  // entonces recargo
					res += min(prev, L - prev);
					prev = 0;
					cur = K;
				}
				res += pos - prev;
				prev = pos;
				cur--;
			}
			res += min(prev, L - prev);
			
			// right
			cur = K;
			prev = L;
			for(int i=sz(right)-1; i>=0; --i){
				int pos = right[i];
				if(cur == 0){ // tengo que recargar
					res += min(prev, L - prev);
					prev = L;
					cur = K;
				}
				res += pos - prev;
				prev = pos;
				cur--;
			}
			res += min(prev, L - prev);
			
			ans = min(ans, res);
			
		}
		
		return ans;
	}
	
	return -1;
}

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