Submission #591734

#	Time	Username	Problem	Language	Result	Execution time	Memory
591734		l_reho	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	1443 ms	347528 KiB

boxes

#include <bits/stdc++.h>
using namespace std;

long long delivery(int N, int K, int L, int p[]) {

	vector<long long> dpA(N+1, 0);
	vector<long long> dpB(N+1, 0);
	
	for(int i = 1; i <= N; i++){
		if(i >= K){
			dpA[i] = dpA[i-K]+p[i-1]*2;
		}else dpA[i] = dpA[0]+p[i-1]*2;
	}
	
	priority_queue<pair<long long, int>> pq;
	
	vector<long long> M(N+1, 0);
		
	pq.push({0, N});
	
	for(int i = N-1; i >= 0; i--){
		if(i+K > N-1)
			dpB[i] = dpB[N] + (L-p[i])*2;
		else dpB[i] = dpB[i+K] + (L-p[i])*2;
		
		
		pq.push({-dpB[i], i});
		
		while(!pq.empty() && pq.top().second > i+K)
			pq.pop();
			
		
		M[i] = -pq.top().first;
	}
	
	long long ans = LLONG_MAX;
	
	for(int i = 0; i <= N; i++)
		ans = min(ans, dpA[i] + dpB[i]);
	
	for(int i = 0; i < N; i++){
		// eliminiamo questo ciclo
		ans = min(ans, dpA[i] + M[i] + (long long)L);
		
		/*
		for(int j = 1; j <= K; j++){
			if(i+j > N) break;
			
			ans = min(ans, dpA[i] + dpB[i+j] + (long long)L);
			
		}
		*/
	}
	
	// considerando che L è una costante, bisogna solo cercare i e i+j minimi
	// posso risolverlo Nlogn

	return ans;
	
}

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