Submission #1198473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198473		PlayVoltz	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	409 ms	196184 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

int delivery(signed n, signed k, signed d, signed pos[]){
	vector<int> l(n+2, LLONG_MAX/2), r(n+2, LLONG_MAX/2);
	l[0]=r[n+1]=0;
	for (int i=1; i<=n; ++i)l[i]=pos[i-1]*2+(i-k>=1?l[i-k]:0);
	for (int i=n; i>=1; --i)r[i]=(d-pos[i-1])*2+(i+k<=n?r[i+k]:0);
	int ans=(n<=k?d:LLONG_MAX/2);
	for (int i=0; i<=n; ++i)ans=min({ans, l[i]+r[i+1], l[i]+r[min(i+k+1, (int)n+1)]+d});
	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