Submission #154098

#	Time	Username	Problem	Language	Result	Execution time	Memory
154098		dennisstar	Boxes with souvenirs (IOI15_boxes)	C++11	0 / 100	3 ms	376 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll s1[10000010], s2[10000010];
long long delivery(int N, int K, int L, int p[]) {
	int i, j;
	K=min(N,K);
	for (i=0; i<K; i++) { for (j=i; j<N; j+=K) { if(p[j]<=L/2) s1[i]+=2*(ll)p[j]; else s1[i]+=L; } }
	for (i=N-1; i>=N-K; i--) { for (j=i; j>=0; j-=K) { if (p[j]<=L/2) s2[i%K]+=L; else s2[i%K]+=2*(ll)(L-p[j]); } }
	ll ans=(1ll<<62), s;
	for (i=0; i<K; i++) {
		s=s2[(i+1)%K]+(p[i]<=L/2?p[i]*2:L);
		ans=min(s, ans);
		for (j=i+K; i<N; i+=K) {
			s+=(ll)(p[j]<=L/2?p[j]*2:L);
			s-=(ll)(p[j-K+1]<=L/2?L:(L-p[j-K+1])*2);
			ans=min(s,ans);
		}
	}
	for (i=N-1; i>=N-K; i--) {
		s=s1[(i+K-1)%K]+(p[i]<=L/2?L:2*(L-p[i]));
		ans=min(s, ans);
		for (j=i-K; j>=0; j-=K) {
			s+=(ll)(p[j]<=L/2?L:2*(L-p[j]));
			s-=(ll)(p[j+K-1]<=L/2?p[j+K-1]*2:L);
			ans=min(s,ans);
		}
	}
	return ans;
}

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