Submission #63325

#	Time	Username	Problem	Language	Result	Execution time	Memory
63325		hamzqq9	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	507 ms	196072 KiB

boxes

#include<bits/stdc++.h>
#include "boxes.h"
using namespace std;
#define MAX 10000002
#define ll long long
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 100000000000000000

ll sumL[MAX],sumR[MAX];

ll get_cost(int pos1,int pos2,int L) {

	return min(1ll*L,min(2ll*pos2,2ll*(L-pos1)));

}

long long delivery(int N, int K, int L, int P[]) {

	ll ans=inf;

	int start=0;

	while(P[start]==0) start++;

	for(int i=N-1;i>=start;i--) {

		if(i+K<N) sumR[i]=sumR[i+K]+get_cost(P[i],P[i+K-1],L);
		else sumR[i]=get_cost(P[i],P[N-1],L);

	}

	for(int i=start;i<N;i++) {

		if(i-K>=start) sumL[i]=sumL[i-K]+get_cost(P[i-K+1],P[i],L);
		else sumL[i]=get_cost(P[start],P[i],L);

	}

	for(int i=start;i<=N;i++) {

		umin(ans,sumR[i]+(i-1>=0?sumL[i-1]:0));

	}

	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