Submission #1245998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245998		Nurislam	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	495 ms	320312 KiB

boxes

#ifndef boxes_h
#define boxes_h

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

long long delivery(int n, int k, int l, int P[]) {
	vector<ll> p;
	for(int i = 0; i < n; i ++ ) p.push_back(P[i]);
	
	vector<ll> pr(n+1, 0), sf(n+1, 0);
	
	for(int i = 0; i < n; i ++ )  {
		if(i < k) pr[i] = p[i];
		if(i >= k) pr[i] += pr[i-k] + p[i-k] + p[i];
	};
	
	for(int i = n-1; i >= 0; i -- ) {
		if(i + k >= n)sf[i] = l-p[i];
		if(i + k < n)sf[i] += sf[i+k] + l-p[i+k] + l-p[i];
	};
	
	ll ans = pr[n-1] + min(l-p[n-1], p[n-1]);
	ans = min(ans, sf[0] + min(l-p[0], p[0]));
	
	for(int i = 1; i < n; i ++ ) {
		ans = min(ans, pr[i-1] + sf[i] + min(p[i], l-p[i]) + min(p[i-1], l-p[i-1]));
	};
	
	return ans;
};

#endif

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