Submission #186009

#	Time	Username	Problem	Language	Result	Execution time	Memory
186009		TAISA_	Boxes with souvenirs (IOI15_boxes)	C++14	50 / 100	44 ms	13860 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);
	if(N>1000){
		return 0;
	}
	vector<ll> sum(K);
	for(ll j=N-1;j>=0;j--){
		sum[(N-j-1)%K]+=2LL*(L-p[j]);
		res=min(res,sum[(N-j-1)%K]+L*ddiv(j,K));
	}
	sum.assign(K,0);
	for(ll i=0;i<N;i++){
		sum[i%K]+=2LL*p[i];
		res=min(res,sum[i%K]+L*ddiv(N-i-1,K));
		vector<ll> sum2(K);
		for(ll j=N-1;j>=i+1;j--){
			sum2[(N-j-1)%K]+=2LL*(L-p[j]);
			res=min(res,sum[i%K]+sum2[(N-j-1)%K]+L*ddiv(j-i-1,K));
		}
	}
	return res;
}

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