Submission #786515

#	Time	Username	Problem	Language	Result	Execution time	Memory
786515		esomer	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	507 ms	247496 KiB

boxes

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

using namespace std;

typedef long long ll;

ll delivery(int n, int k, int L, int* positions){
	vector<ll> prefix(n, 0);
	vector<ll> suffix(n, 0);
	//~ multiset<ll> s;
	for(int i = 0; i < n; i++){
		ll mn = 1e18;
		if(i - k < 0) mn = 0;
		else mn = prefix[i-k];
		//~ else mn = *s.begin();
		ll cost = positions[i] + min(L - positions[i], positions[i]);
		prefix[i] = mn + cost;
		//~ s.insert(prefix[i]);
		//~ if(i - k >= 0) s.erase(s.find(prefix[i-k]));
	}
	//~ s.clear();
	for(int i = n-1; i >= 0; i--){
		ll mn = 1e18;
		if(i + k >= n) mn = 0;
		else mn = suffix[i+k];
		//~ else mn = *s.begin();
		ll cost = L - positions[i] + min(L - positions[i], positions[i]);
		suffix[i] = mn + cost;
		//~ s.insert(suffix[i]);
		//~ if(i + k < n) s.erase(s.find(suffix[i+k]));
	}
	ll ans = min(suffix[0], prefix[n-1]);
	for(int i = 0; i < n-1; i++){
		ans = min(ans, prefix[i] + suffix[i+1]);
	}
	return ans;
}

//~ int main() {
    //~ int N, K, L, i;
	//~ cin >> N >> K >> L;

    //~ vector<int> p(N);

    //~ for (i = 0; i < N; i++) {
        //~ cin >> p[i];
    //~ }
    
    //~ fprintf(stdout, "%lld\n", delivery(N, K, L, p));
    //~ return 0;
//~ }

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