Submission #1042107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042107		allin27x	Boxes with souvenirs (IOI15_boxes)	C++17	20 / 100	1 ms	4444 KiB

boxes

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

const int MAXN = 1e7+4;

int P[MAXN];
int lpr[MAXN];
int rpr[MAXN];

int N, K, L;

int ans(int a, int b){
	int M = 0;
	for (int i=a; i<b; i++) M = max(M, P[i+1]-P[i]);
	return min(min(P[b] + min(L-P[b], P[b]), L-P[a] + min(L-P[a], P[a])), 2*L - 2*M);  
}


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];
	int r = n%k;
	for (int i=0; i<n; i++){
		if (i%k == k-1) lpr[i] += ans(i-k+1, i);
		if (i>0) lpr[i] += lpr[i-1];
	}
	for (int i=n-1; i>=0; i--){
		if (i%k == n%k) rpr[i] += ans(i, i+k-1);
		if (i<n-1) rpr[i] += rpr[i+1];
	}
	int res = 1e18;
	for (int i=0; i<n; i+=k){
		res = min(res, (i?lpr[i-1]:0) + (r?ans(i, i+r-1):0) + rpr[i]);
	}

	return res;
}

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