제출 #1301853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1301853		nicolo_010	선물상자 (IOI15_boxes)	C++20	10 / 100	1 ms	584 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int mxN = 1e6+5;
vector<int> pos;

int n, k;

ll delivery(int N, int K, int L, int* a) {
	n = N;
	k = K;
	pos.assign(n, 0);
	for (int i=0; i<n; i++) {
		pos[i] = a[i];
	}
	if (k==1) {
		ll ans=0;
		for (int i=0; i<n; i++) {
			ans += min(2*min(pos[i], L-pos[i]), L);
		}
		return ans;
	}
	bool left = true, right = true;
	for (int i=0; i<n; i++) {
		if (pos[i] > L/2) left = false;
		if (pos[i] <= L/2) right = false;
	}
	if (left) {
		ll sum=0;
		ll prod=1;
		int cnt=0;
		for (int i=n-1; i>=0; i--) {
			if (cnt==0) sum += 2*pos[i];
			cnt++;
			if (cnt==k) {
				cnt=0;
				prod++;
			}
		}
		return sum;
	}
	else if (right) {
		ll sum=0;
		ll prod=1;
		int cnt=0;
		for (int i=0; i<n; i++) {
			if (cnt==0) sum += 2*(L-pos[i]);
			cnt++;
			if (cnt==k) {
				cnt=0;
				prod++;
			}
		}
		return sum;
	}
	else {
		int idx;
		ll sum=0;
		for (int i=0; i+k-1<n; i++) {
			if (pos[i] <= L/2 && pos[i+k-1] > L/2) {
				idx = i;
			}
		}
		ll suml=0;
		ll sumr=0;
		map<int, ll> mpl, mpr;
		int cnt=0;
		for (int i=idx-1; i>=0; i--) {
			mpl[i%k]+=2*pos[i];
		}
		cnt=0;
		for (int i=idx+k; i<n; i++) {
			mpr[i%k]+=2*(L-pos[i]);
		}
		ll ans=1e18;
		int l = idx-1, r = idx+k;
		int idxl = idx-1;
		int idxr = idx+k;
		l+=k;
		r+=k;
		l %= k;
		r %= k;
		for (int i=idx; i>=0; i--) {
			if (pos[i+k-1] <= L/2) break;
			ll coste = L;
			suml = mpl[l];
			sumr = mpr[r];
			//cout << idx << " " << l << " " << r << " " << idxl << " " << idxr << " " << coste << suml << " " << sumr << endl;
			ans = min(ans, suml+sumr+coste);
			if (idxl >= 0) {
				mpl[l] -= 2*pos[idxl];
				l--;
				l+=k;
				l %= k;
				idx--;
			} 
			idxr--;
			r--;
			r+= k;
			r %= k;
			mpr[r] += pos[idxr];
		}
		return ans;
	}
	return 0;
}

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