Submission #110024

#	Time	Username	Problem	Language	Result	Execution time	Memory
110024		CaroLinda	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	3 ms	384 KiB

boxes

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define ll long long
#define ff first
#define ss second

const int MAXN = 1e7 + 5;
const int inf = 1e9 + 10 ;

using namespace std ;

//Declaracoes
int N , K , L ;
int pos[MAXN] ;
ll dp1[MAXN] , dp2[MAXN] ;

void print()
{
	lp(i,0,N) cout<<dp1[i]<<" ";
	cout<<endl ;
	lp(i,0,N) cout<<dp2[i]<<" ";
	cout<<endl;
}

//Funcao principal
ll delivery(int n , int k , int l , int positions[] )
{
	//Globalizacao
	N = n ; K = k ; L = l ;
	lp(i,0,n) pos[i] = positions[i] ;
	
	lp(i,0,n)
		if( pos[i] == 0 ) pos[i] = inf , N-- ;
		
	sort( pos , pos + n ) ;
	n = N ;
	
	lp(i,0,n)
	{
		dp1[i] = pos[i] * 2 ;
		if( i - k >= 0 ) dp1[i] += dp1[i-k] ; 
	}
	
	for( int i = n-1 ; i >= 0 ; i-- )
	{
		dp2[i] = ( L - pos[i]) * 2 ;
		if( i + k < n ) dp2[i] += dp2[i+k] ;
	}
	
	ll best =  1LL * inf * MAXN ;
	
	lp(i,0,n)
		best = min( best , dp1[i] + dp2[i+1] ) ;
	
	lp(i,0,n)
	{
		ll x = 0;
		if( i + k < n ) x = dp2[i+k] ;
		ll y = 0 ;
		if( i-1 >= 0 ) y = dp1[i-1] ;
		best = min( best , y + x + L ) ;
	} 
	
	return best ;
}

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