제출 #1301854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1301854		nicolo_010	선물상자 (IOI15_boxes)	C++20	100 / 100	394 ms	235388 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;

ll delivery(int n, int k, int l, int* a) {
	pos.assign(n, 0);
	for (int i=0; i<n; i++) {
		pos[i] = a[i];
	}
	vector<ll> L(n, 0), R(n, 0);
	for (int i=0; i<k; i++) {
		L[i] = 2*(pos[i]);
	}
	for (int i=n-1; i>=n-k; i--) {
		R[i] = 2*(l-pos[i]);
	}
	for (int i=k; i<n; i++) {
		L[i] = L[i-k] + 2*(pos[i]);
	}
	for (int i=n-k-1; i>=0; i--) {
		R[i] = R[i+k] + 2*(l-pos[i]);
	}
	ll ans=R[0];
	for (int i=0; i<n-1; i++) {
		ans = min(ans, L[i]+R[i+1]);
	}
	ans = min(ans, L[n-1]);
	for (int i=0; i<n; i++) {
		ll left = (i==0 ? 0 : L[i-1]);
		ll right = (i+k>=n ? 0 : R[i+k]);
		//cout << i << " " << left << " " << right << endl;
		ans = min(ans, left+right+l);
	}
	return ans;
}

//i+k-1-i
//k-1

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