Submission #133034

#	Time	Username	Problem	Language	Result	Execution time	Memory
133034		Mahdi_Jfri	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	728 ms	274404 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e7 + 20;

ll dp[maxn] , pd[maxn];

int a[maxn] , deq[maxn] , s , t;

long long delivery(int n, int k, int L, int p[])
{
	for(int i = 1; i <= n; i++)
		a[i] = p[i - 1];

	s = t = 0;
	deq[t++] = 0;
	for(int i = 1; i <= n; i++)
	{
		dp[i] = dp[deq[s]] + a[i] + min(a[i] , L - a[i]);
		while(t != s && dp[deq[t - 1]] >= dp[i])
			t--;
		deq[t++] = i;

		if(deq[s] <= i - k)
			s++;

	}
	
	s = t = 0;
	deq[t++] = n + 1;
	for(int i = n; i >= 1; i--)
	{
		pd[i] = pd[deq[s]] + L - a[i] + min(a[i] , L - a[i]);
		while(t != s && pd[deq[t - 1]] >= pd[i])
			t--;
		deq[t++] = i;

		if(deq[s] >= i + k)
			s++;
	}

	ll res = 1e18;
	for(int i = 0; i <= n; i++)
		res = min(res , dp[i] + pd[i + 1]);

	return res;
}

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