记录编号	406680	评测结果	PPPPPPPPPPPPPPPPPPPP
题目名称	[NOI 2015]荷马史诗	最终得分	40
用户昵称	Imone NOI2018Au	是否通过	未通过
代码语言	C++	运行时间	0.481 s
提交时间	2017-05-19 16:57:04	内存使用	0.31 MiB

#include <cstring>
#include <cstdio>
#include <queue>
#define MAXN 100010
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

int N, K;

struct node {
	ll priv;
	int dep;
	inline bool operator<(const node& rhs) const {
		return (priv == rhs.priv) ? (dep > rhs.dep) : (priv > rhs.priv);
	}
};

priority_queue<node> Q;
ll AnsL = 0;

int main() {
	freopen("epic.in", "rt", stdin);
	freopen("epic.out", "wt", stdout);

	int i; ll t;
	scanf("%d%d", &N, &K);
	for(i=1;i<=N;i++) {
		scanf("%lld", &t); Q.push({t, 0});
	}
	if((N % (K-1)) != 1) {
		int p = (K - N % (K-1)) % (K-1);
		for(i=0;i<p;i++) Q.push({0, -INF});
	} 
	while(Q.size() > 1) {
		node comb = {0, 0};
		for(i=0;i<K;i++) {
			node cur = Q.top(); Q.pop();
			comb.dep = max(comb.dep, cur.dep+1);
			comb.priv += cur.priv;
		}
		AnsL += comb.priv;
		Q.push(comb);
	}
	node final = Q.top();
	printf("%lld\n%lld", AnsL, final.dep);
}