记录编号	466131	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]荷马史诗	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.610 s
提交时间	2017-10-28 16:29:36	内存使用	7.94 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define int long long
inline int read(){
	int sum(0);char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct node{
	int w,h;
	inline bool operator<(const node &x)const{return w^x.w?w<x.w:h<x.h;}
}heap[500005];
int top;
inline void push(node x){
	heap[++top]=x;int now(top);
	while(1){
		if(now==1)break;
		if(heap[now]<heap[now>>1])swap(heap[now],heap[now>>1]),now>>=1;
		else break;
	}
}
inline node get_top(){
	node ret(heap[1]);swap(heap[1],heap[top--]);int now(1),son;
	while(1){
		if((now<<1)>top)break;
		if((now<<1|1)<=top&&heap[now<<1|1]<heap[now<<1])son=now<<1|1;
		else son=now<<1;
		if(heap[now]<heap[son])break;
		else swap(heap[now],heap[son]),now=son;
	}
	return ret;
}
int n,k,sum,mx;
signed main(){
	freopen("epic.in","r",stdin);freopen("epic.out","w",stdout);
	n=read(),k=read();
	for(int i=1;i<=n;++i){
		int x(read());
		push((node){x,0});
	}
	if((n-1)%(k-1))
		for(int i=0;i<(k-1)-(n-1)%(k-1);++i)
			push((node){0,0});
	while(top>1){
		int hi(0),s(0);
		for(int i=0;i<k;++i){
			node top(get_top());
			s+=top.w;hi=max(hi,top.h);
		}
		push((node){s,hi+1});
		sum+=s;mx=max(mx,hi+1);
	}
	printf("%lld\n%lld",sum,mx);
}