记录编号	61898	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]诗人小G	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.627 s
提交时间	2013-06-17 19:27:33	内存使用	3.46 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<deque>
#include<iomanip>
#include<cstring>
#include<stack>
#include<fstream>
using namespace std;
typedef long long ll;
typedef long double ld;
ifstream fin("noi09_poet.in");
ofstream fout("noi09_poet.out");
const ll SIZEN=100001;
const ld LIM=1e18;
ld S[SIZEN]={0};
ld f[SIZEN]={0};
ll N,L,C,P;
string word[SIZEN];
bool el[SIZEN]={0};//"转折点"
ld labs(ld x){
	return x>0?x:-x;
}
ld pow(ld x){//x^P
	ld ans=1;
	ll i;
	for(i=1;i<=P;i++) ans*=x;
	return labs(ans);
}
ld fig(ll x,ll i){//在状态x下的决策i
	return f[i]+pow(S[x]-S[i]-C);
}
ll find(ll s,ll e,ll x,ll y){//在区间[s,e]上使得决策y优于决策x的最小值
	if(s==e){
		if(fig(s,y)<=fig(s,x)) return s;
		else return s+1;
	}
	ll mid=(s+e)>>1;
	if(fig(mid,x)>=fig(mid,y)) return find(s,mid,x,y);
	else return find(mid+1,e,x,y);
}
int jc[SIZEN]={0};//每个点的决策
class TRI{
public:
	ll pos;//决策值
	ll s,e;//起点和终点
};
class MNQ{
public:
	deque<TRI> lis;
	void clear(void){
		lis.clear();
	}
	void clf(ll x){//把x之前(不含)的决策全部删除
		while(lis.size()&&lis.front().e<x) lis.pop_front();
	}
	void update(ll x){//用决策x-1更新区间并且更新x的决策,如果大于1e18就false
		clf(x);
		lis[0].s=x;
		TRI temp=lis.front();
		int nows;
		while(lis.size()&&fig(lis.back().s,x-1)<=fig(lis.back().s,lis.back().pos)){
			nows=lis.back().s;
			lis.pop_back();
		}
		if(lis.size()&&fig(lis.back().e,x-1)<=fig(lis.back().e,lis.back().pos)){
			if(fig(lis.back().e,x-1)<=fig(lis.back().e,lis.back().pos)){
				int now=find(lis.back().s,lis.back().e,lis.back().pos,x-1);
				lis.back().e=now-1;
				nows=now;
			}
		}
		if(lis.size()==0||lis.back().e<N) lis.push_back((TRI){x-1,nows,N});
		clf(x);
		jc[x]=lis[0].pos;
		f[x]=fig(x,jc[x]);
	}
}Q;
void process(void){
	ll i;
	Q.lis.push_back((TRI){0,1,N});
	for(i=1;i<=N;i++) Q.update(i);
	if(f[N]>LIM) goto END;
	fout<<(ll)f[N]<<endl;
	int x;
	x=N;
	while(x){
		x=jc[x];
		if(x) el[x]=true;
	}
	for(i=1;i<=N;i++){
		fout<<word[i];
		fout<<(el[i]?"\n":" ");
	}
	fout<<endl<<"--------------------"<<endl;
	return;
	END:;
	fout<<"Too hard to arrange";
	fout<<endl<<"--------------------"<<endl;
	return;
}
void init(void){
	fin>>N>>L>>P;
	C=L+1;
	string str;
	ll i;
	for(i=1;i<=N;i++){
		fin>>str;
		word[i]=str;
		S[i]=str.size();
		S[i]+=S[i-1];
	}
	for(i=1;i<=N;i++) S[i]+=i;
	f[0]=0;
	Q.clear();
	memset(el,0,sizeof(el));
}
int main(){
	int T;
	fin>>T;
	while(T){
		init();
		process();
		T--;
	}
	fin.close();
	fout.close();
	return 0;
}