Submission #67843

#	Time	Username	Problem	Language	Result	Execution time	Memory
67843		gnoor	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	457 ms	157068 KiB

boxes

#include "boxes.h"

#include <algorithm>

using namespace std;

int posl[10000100];
int posr[10000100];
int cntl;
int cntr;

long long dpl[10000100];
long long dpr[10000100];

long long delivery(int N, int K, int L, int p[]) {
	int m=L/2;
	for (int i=0;i<N;i++) {
		if (p[i]<=m) {
			posl[cntl++]=p[i];
		} else {
			posr[cntr++]=L-p[i];
		}
	}
	reverse(posr,posr+cntr);
	for (int i=0;i<min(cntl,K);i++) {
		dpl[i]=posl[i]*2;
	}
	for (int i=K;i<cntl;i++) {
		dpl[i]=dpl[i-K]+posl[i]*2;
	}
	for (int i=0;i<min(cntr,K);i++) {
		dpr[i]=posr[i]*2;
	}
	for (int i=K;i<cntr;i++) {
		dpr[i]=dpr[i-K]+posr[i]*2;
	}
	long long ans=1e16;
	for (int i=0;i<=min(cntl,K);i++) {
		ans=min(ans,((cntl-i-1<0)?0:dpl[cntl-i-1])+((cntr-(K-i)-1<0)?0:dpr[cntr-(K-i)-1])+L);	
	}
	ans=min(ans,dpl[cntl-1]+dpr[cntr-1]);
	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