Submission #1270441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270441		cmiuc	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	350 ms	196640 KiB

boxes

#include <iostream>
#include <vector>
#include <algorithm>
#include "boxes.h"

using namespace std;
long long pre[10000007], suf[10000007];

long long delivery(int n, int k, int l, int p[]){
	k = min(k, n);

	for (int i=n-1;i>=0;i--){
		if (i + k >= n)
			suf[i] = (l - p[i]) * 2;
		else
			suf[i] = suf[i + k] + (l - p[i]) * 2; 
	}
	long long Ans = min(suf[0], l + suf[k]);

	for (int i=0;i<n;i++){
		if (i < k)
			pre[i] = p[i] * 2;
		else
			pre[i] = pre[i - k] + p[i] * 2;

		if (i + k < n)
			Ans = min(Ans, pre[i] + min(suf[i+1], suf[i + k + 1] + l));
		else
			Ans = min(Ans, pre[i] + min(suf[i + 1], 0LL + l));
	}
	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