Submission #186090

#	Time	Username	Problem	Language	Result	Execution time	Memory
186090		TAISA_	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	1129 ms	308532 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll LINF=(1LL<<60)-1LL;
ll ddiv(ll a,ll b){
	return a/b+(a%b>0);
}
long long delivery(int N, int K, int L, int p[]) {
	ll res=L*ddiv(N,K);
	vector<ll> a(K),b(K),c(N),d(N);
	for(ll j=N-1;j>=0;j--){
		b[(N-j-1)%K]+=2LL*(L-p[j]);
		d[j]=b[(N-j-1)%K];
		res=min(res,b[(N-j-1)%K]+L*ddiv(j,K));
	}
	for(ll i=0;i<N;i++){
		a[i%K]+=2LL*p[i];
		c[i]=a[i%K];
		res=min(res,a[i%K]+L*ddiv(N-i-1,K));
	}
	res=min(res,d[0]);
	for(int i=0;i<N;i++){
		if(i<N-1){
			res=min(res,c[i]+d[i+1]);
		}else{
			res=min(res,c[i]);
		}
	}
	for(int i=0;i<N;i++){
		if(i+K+1<N){
			res=min(res,c[i]+d[i+K+1]+L);
		}
	}
	for(int i=0;i<N;i++){
		if(i+2*K+1<N){
			res=min(res,c[i]+d[i+K+K+1]+2LL*L);
		}
	}
	return res;
}

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