#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
ll n, k, w[N];
ll ans1, ans2;
struct node {
	ll dep, val;
	friend bool operator < (node h1, node h2) {
		if(h1.val != h2.val) return h1.val > h2.val;
		else return h1.dep > h2.dep;
	}
}; 
priority_queue<node> q;
void build() {
	if(k > 2) {
		ll tmp = k - 1 - (n - 1) % (k - 1);
		for(int i=1; i<=tmp; ++i) q.push({1, 0});
	}
	while(q.size() > k - 1) {
		ll sum = 0, mdep = 0;
		for(int i=1; i<=k; ++i) {
			node cur = q.top();
			q.pop();
			mdep = max(mdep, cur.dep);
			sum += cur.val;
		}
		q.push({mdep + 1, sum});
		ans1 += sum;
		ans2 = max(ans2, mdep);
	}
}
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for(int i=1; i<=n; ++i) cin >> w[i], q.push({1, w[i]});
	build();
	cout << ans1 << '\n' << ans2;
	return 0;
}

1 條評論

  • 1

資訊

ID
939
時間
1000ms
記憶體
256MiB
難度
9
标签
(無)
遞交數
123
已通過
11
上傳者