Submission #291698

#	Time	Username	Problem	Language	Result	Execution time	Memory
291698		Berted	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	619 ms	236664 KiB

boxes

#include "boxes.h"
#include <iostream>
#include <assert.h>
#include <utility>
#include <algorithm>
#define ll long long
#define pii pair<ll, int>
#define fst first
#define snd second
const ll INF = 1e18;

using namespace std;

ll dp[10000001];
pii dq[10000001];
int LF = 0, RG = 0;

long long delivery(int N, int K, int L, int p[]) 
{
	dp[0] = 0;
	dq[RG++] = {dp[0] + 2 * (L - p[0]), 0};
	for (int i = 1; i <= N; i++)
	{
		while (LF < RG && dq[LF].snd < i - K) {LF++;}
		
		dp[i] = INF;
		dp[i] = min(dp[i], dp[max(0, i - K)] + 2 * p[i - 1]);
		dp[i] = min(dp[i], dp[max(0, i - K)] + L);
		if (LF < RG) dp[i] = min(dp[i], dq[LF].fst);

		while (LF < RG && dp[i] + 2 * (L - p[i]) <= dq[RG - 1].fst) {RG--;}
		dq[RG++] = {dp[i] + 2 * (L - p[i]), i};
	}
	return dp[N];
}

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