Submission #783306

#	Time	Username	Problem	Language	Result	Execution time	Memory
783306		shezitt	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 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 4
	if(N <= 1000){
		ll ans = 4e18;
		
		// todo derecha 1111111
		ll res = 0;
		ll cur = K;
		ll prev = L;
		for(int i=N-1; i>=0; --i){
			if(cur == 0){ // necesito recargar
				res += min(L - prev, prev);
				prev = L;
				cur = K;
			}
			assert(prev >= p[i]);
			res += prev - p[i];
			prev = p[i];
			cur--;
		}
		ans = min(ans, res);
		
		// busco
		for(int i=1; i<2; ++i){
			// todo left en [0...i]
			res = 0;
			prev = 0;
			cur = K;
			for(int j=0; j<=i; ++j){
				if(cur == 0){
					res += min(prev, L - prev);
					prev = 0;
					cur = K;
				}
				res += p[j] - prev;
				prev = p[j];
				cur--;
			}
			res += min(prev, L - prev);
			
			prev = L;
			cur = K;
			for(int j=N-1; j>i; --j){
				if(cur == 0){
					res += min(prev, L - prev);
					prev = L;
					cur = K;
				}
				res += prev - p[j];
				prev = p[j];
				cur--;
			}
			res += min(prev, L - prev);
			
			ans = min(ans, res);
			
		}
		return ans;
		
	}
	
	return -1;
}

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