Submission #1242371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242371		tkm_algorithms	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	352 ms	174756 KiB

boxes

/**
*    In the name of Allah
*    We are nothing and you're everything
*    Ya Muhammad!
**/
#include <bits/stdc++.h>
#include "boxes.h"
 
using namespace std;
using ll = long long;
using ull = uint64_t;
 
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int long long

const char nl = '\n';

long long delivery(int n, int k, int L, int p[]) {
	ll res = 0;
	vector<ll> l;
	for (int i = 0; i < n; ++i) {
		if (p[i]>L/2)break;
		if (i+1 <= k)l.push_back(p[i]*2);
		else l.push_back(l[sz(l)-k]+p[i]*2);
		res = l.back();
	}
	
	ll back = 0;
	vector<ll> r;
	for (int i = n-1; i >= 0; --i) {
		if (p[i] <= L/2)break;
		if (n-i <= k)r.push_back((L-p[i])*2);
		else r.push_back(r[sz(r)-k]+(L-p[i])*2);
		back = r.back();
	}
	
	res += back;
	
	int start = 0;
	while (start < sz(l)) {
		int len1 = sz(l)-start;
		if (len1>=k){start++;continue;}
		if (sz(r)<=k-len1)
			res = min(res, (start>0?l[start-1]:0ll)+L);
		else {
			res = min(res, (start>0?l[start-1]:0ll)+L+r[sz(r)-k+len1-1]);
		}
		start += 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