记录编号	268339	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]荷马史诗	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.408 s
提交时间	2016-06-12 14:12:47	内存使用	4.90 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int maxn = 100050;

inline LL get_num() {
	char tmp = getchar();
	LL res = 0;
	while(tmp < '0'  or  tmp > '9')  tmp = getchar();
	while(tmp <= '9' and tmp >= '0') {
		res = res * 10 + tmp - '0';
		tmp = getchar();
	}
	return res;
} 

template <class T> class heap{
private:
	T a[maxn << 2];
	int en;
public:
	inline heap() { en=0; }
	
	inline int size() { return en; }
	
	inline T top() { return a[1]; } 
	
	inline bool empty() { return en == 0; }
	
	inline void insert(T num) {
		a[++en] = num;
		int now = en;
		while(now != 1 && num < a[now >> 1]){
			a[now] = a[now >> 1];
			a[now >> 1] = num;
			now = (now >> 1);
		}
	}
	
	inline void pop() {
		a[1]=a[en];
		int now = 1;
		T tmp = a[en--];
		while( (now << 1) <= en && min(a[now << 1], a[(now << 1) | 1]) < tmp) {
			if(a[now << 1] < a[(now << 1) | 1]) {
				a[now] = a[now << 1];
				a[now << 1] = tmp;
				now = (now << 1);
			} else {
				a[now] = a[(now << 1) | 1];
				a[(now << 1) | 1] = tmp;
				now = ((now << 1) | 1);
			}
		}
	}
};

struct node {
	LL v;
	int de;
	node() {}
	node(LL v_, int de_) { v = v_, de = de_; }
	
	bool operator < (const node &b) const {
		return v == b.v ? de < b.de : v < b.v;
	} 
};

heap <node> h;
int n, k;

inline void read() {
	n = get_num();
	k = get_num();
	
	LL tmp;
	for(int i = 1; i <= n; i++) {
		tmp = get_num();
		h.insert(node(tmp, 0));
	}
	
	if((n - 1) % (k - 1) == 0) return;
	for(int i = n; (i - 1) % (k - 1); i++) {
		h.insert(node(0, 0));
	}
}

inline void solve() {
	LL ans = 0;
	while(h.size() != 1) {
		LL now = 0;
		int de = 0;
		for(int i = 1; i <= k; i++) {
			now += h.top().v;
			de = max(h.top().de, de);
			h.pop();
		}
		ans += now;
		h.insert(node(now, de + 1));
	}
	printf("%lld\n%d", ans, h.top().de);
} 

int main() {
	freopen("epic.in",  "r", stdin);
	freopen("epic.out", "w", stdout);


	read();
	solve();
	return 0;
}