제출 #782650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
782650		Sohsoh84	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	6 ms	384 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define sep			' '
#define debug(x)		cerr << #x << ": " << x << endl;

const ll MAXN = 1e7 + 10;

ll ps[MAXN], ss[MAXN], rem[MAXN], dp2[MAXN], n, k, l, f[MAXN];

inline ll req(ll x) {
	if (x <= 0) return 0;
	return (x + k - 1) / k;
}

inline void solve(ll* dp1) {
	for (int i = 0; i <= l; i++)
		dp1[i] = dp2[i] = rem[i] = 0;

	dp1[0] = 0;
	rem[0] = k;
	for (int i = 1; i < l; i++) {
		dp1[i] = dp1[i - 1] + 2 * i * req(f[i]);
		dp2[i] = dp1[i] + (f[i] == 0 ? i : -i);
		rem[i] = (f[i] == 0 ? k : f[i] % k);

		ll tdp = dp2[i - 1] + 1, trem = rem[i - 1];
		if (f[i] <= trem)
			trem -= f[i];
		else {
			ll x = f[i] - trem;
			tdp += 2 * i * req(x) - i;
			trem = x % k;
		}

		if (pll(tdp, trem) <= pll(dp2[i], rem[i])) {
			dp2[i] = tdp;
			rem[i] = trem;
		}

		dp1[i] = min(dp1[i], dp2[i] + i);
	}
}

ll delivery(int N, int K, int L, int p[]) {
	n = N, k = K, l = L;
	for (int i = 0; i < n; i++)
		f[p[i]]++;

	solve(ps);
	reverse(f + 1, f + l);
	solve(ss);

	ll ans = min(ps[l - 1], ss[l - 1]);
	for (int i = 1; i < l - 1; i++)
		ans = min(ans, ps[i] + ss[l - 1 - i]);
	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