Submission #426085

#	Time	Username	Problem	Language	Result	Execution time	Memory
426085		dreezy	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	64 ms	12012 KiB

boxes

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

long long delivery(int N, int K, int LL, int pp[]) {
	
	//vector<ll> p(N);
	
	ll L = LL;
	ll p[N];
	for(int i =0; i<N; i++) p[i] = pp[i];
	//for(int i = 0; i<n; i++) p[i] = pp[i];
	ll ans = 1e18;
	ll mid = L/2;
	int midind = N;
	int lmidind = 0;
	for(int i =0; i<N; i++){
		if(p[i] > mid){
			midind = i;
			break;
		} 
	}
	
	for(int i =N-1; i>=0; i--){
		if(p[i] < mid){
			lmidind = i;
			break;
		} 
	}
	//cout << midind<<endl;
	int best = -1;
	for(int first = max(0, lmidind - K-10); first<= min(N-1,midind+K +10); first++){
		ll curans = 0;
		//cout << first<<":: "<<endl;
		for(int rng = first; rng < N + first; rng += K){
			int start = rng;
			
			int end = start + K -1;
			int mstart = start % N;
			int mend = end % N;
			if(end - N >= first){
				end = first - 1 + N;
				mend = end % N;
			}
			//cout << start<<"->"<<end<<", "<<mstart<<"->"<<mend<<endl;
			if(end < N){
							
				//cout <<start<<", "<<end<< ": "<< p[start]<<", "<<p[end]<<endl;
				if(end< midind){//if they are alll in first half
					curans += 2 * p[end];
				}
				//all in second half
				else if(start >= midind){
					curans += 2 * ( L - p[start]);
				}
				else{
					//cout <<"hi"<<endl;
					curans += min(L, 2*p[midind - 1] + 2 * (L-p[midind] ));
				}
			}
			else{
				if( start < N){
					if(start < midind){
						curans += L;
					}
					else if(mend >= midind){
						curans += L;
					}
					else{
					//cout <<"bye"<<endl;
						curans += min(L , 2 * p[mend] + 2 * (L-p[start]) );
					}
				}
				else{
					if(mend< midind){//if they are alll in first half
					curans += 2 * p[mend];
					}
					//all in second half
					else if(mstart >= midind){
						curans += 2 * ( L - p[mstart]);
					}
					else{
					//cout <<"bye"<<endl;
						curans += min(L, 2*p[midind - 1] + 2 * (L-p[midind])   );
					}
					
				}
				
			}
				// do circle	
				
			//cout << rng<<": "<<curans<<endl;
		}
		//cout <<":: "<<curans<<endl<<endl;
		ans = min(curans, ans);
		
		if(ans == curans)
			best = first;
		//cout << curans<<", ";
	}
	//cout <<endl;
	//cout << best<<endl;
    return ans;
}
/************/

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:32:6: warning: variable 'best' set but not used [-Wunused-but-set-variable]
   32 |  int best = -1;
      |      ^~~~

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