Submission #1042129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042129		allin27x	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	453 ms	372020 KiB

boxes

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 1e7+4;

int P[MAXN];
int lans[MAXN];
int rans[MAXN];

int N, K, L;

int delivery(signed n, signed k, signed l, signed p[]){
	N=n;K=k;L=l;for (int i=0; i<n; i++) P[i] = p[i];
	
	for (int i=0; i<n; i++){
		lans[i] += P[i] + min(P[i], L-P[i]);
		if (i >= k) lans[i] += lans[i-k];
	}
	for (int i=n-1; i>=0; i--){
		rans[i] += L-P[i] + min(L-P[i], P[i]);
		if (i<n-k) rans[i] += rans[i+k];
	}
	int ans = min(lans[n-1], rans[0]);
	for (int i=1; i<n; i++){
		ans = min(ans, lans[i-1] + rans[i]);
	}
	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