记录编号	344349	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]诗人小G	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.646 s
提交时间	2016-11-10 08:09:03	内存使用	7.06 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long double f64;
const int maxn=100010;
f64 w(int,int);
f64 qpow(f64,int);
void print(int);
int T,n,m,k,a[maxn]={0},s[maxn]={0},g[maxn],q[maxn],l[maxn],r[maxn],head,tail;
f64 f[maxn];
char c[maxn][35];
int main(){
#define MINE
#ifdef MINE
	freopen("noi09_poet.in","r",stdin);
	freopen("noi09_poet.out","w",stdout);
#endif
	scanf("%d",&T);
	while(T--){
		memset(g,0,sizeof(g));
		memset(f,0,sizeof(f));
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=n;i++){
			scanf("%s",c[i]);
			a[i]=strlen(c[i])+1;
			s[i]=s[i-1]+a[i];
		}
		head=tail=1;
		q[tail]=0;
		l[tail]=1;
		r[tail]=n;
		for(int i=1;i<=n;i++){
			while(r[head]<i)head++;
			g[i]=q[head];
			f[i]=f[g[i]]+w(g[i],i);
			if(f[i]+w(i,n)>f[q[tail]]+w(q[tail],n))continue;
			int left=r[tail]+1;
			while(head<=tail&&f[i]+w(i,l[tail])<=f[q[tail]]+w(q[tail],l[tail])){
				left=l[tail];
				tail--;
			}
			if(head<=tail){
				int L=l[tail],R=n;
				while(L<=R){
					int M=(L+R)>>1;
					if(f[i]+w(i,M)<=f[q[tail]]+w(q[tail],M))R=M-1;
					else L=M+1;
				}
				left=L;
			}
			r[tail]=left-1;
			q[++tail]=i;
			l[tail]=left;
			r[tail]=n;
		}
		if(f[n]-(f64)1e-5>(f64)1e18)printf("Too hard to arrange\n");
		else{
			printf("%lld\n",(long long)f[n]);
			print(n);
		}
		printf("--------------------\n");
	}
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
f64 w(int j,int i){
	return qpow(abs(s[i]-s[j]-1-m),k);
} 
f64 qpow(f64 a,int b){
	f64 ans=(f64)1.0;
	for(;b;b>>=1,a*=a)if(b&1)ans*=a;
	return ans;
}
void print(int i){
	if(!i)return;
	print(g[i]);
	for(int j=g[i]+1;j<i;j++)printf("%s ",c[j]);
	printf("%s\n",c[i]);
}