Submission #591706

#	Time	Username	Problem	Language	Result	Execution time	Memory
591706		l_reho	Boxes with souvenirs (IOI15_boxes)	C++14	50 / 100	2033 ms	29420 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;
	}
	
	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;
	}
	
	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++){
		for(int j = 1; j <= K; j++){
			if(i+j > N) break;
			ans = min(ans, dpA[i] + dpB[i+j] + (long long)L);
			
		}
	}
	

	return ans;
	
}

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