Submission #209370

#	Time	Username	Problem	Language	Result	Execution time	Memory
209370		autumn_eel	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	621 ms	231336 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

const ll INF=0x3f3f3f3f3f3f3f3f;

ll s1[10000100],s2[10000100];

long long delivery(int N, int K, int L, int p[]) {
	for(int i=1;i<=N;i++){//[0,i)
		int j=max(0,i-K);//[j,i)
		ll cost=min(p[i-1],L-p[i-1])+min(p[j],L-p[j])+abs(p[i-1]-p[j]);
		s1[i]=s1[j]+cost;
	}
	for(int i=N-1;i>=0;i--){//[i,N)
		int j=min(N,i+K);//[i,j)
		ll cost=min(p[i],L-p[i])+min(p[j-1],L-p[j-1])+abs(p[i]-p[j-1]);
		s2[i]=s2[j]+cost;
	}
	ll Min=INF;
	for(int i=0;i<=N;i++){
		Min=min(Min,s1[i]+s2[i]);
	}
	return Min;
}

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