记录编号	587062	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]诗人小G	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.177 s
提交时间	2024-03-11 16:53:40	内存使用	9.35 MiB

#include <bits/stdc++.h>
using namespace std;
//二分队列-决策单调性优化dp 
#define ll long long
#define ld long double
const int N = 1e5+10;
const ll inf = 1e17;
int t,n,p,l,r,la[N];
ld f[N];
ll L,s[N];
char c[N][40];
struct made{
    int p,l,r;
}q[N];
ld power(ld x,int y){
    ld ans = 1;
    while(y){
        if(y & 1)ans *= x;
        x *= x,y >>= 1; 
    }return ans;
}
ll ab(ll x){return x < 0 ? -x : x;}
ld W(int l,int r){return power(ab(s[r]-s[l]-L),p);}
ld val(int l,int r){return f[l] + W(l,r);}
int work(int i,int L,int R){
    while(L < R){
        int mid = L + R >> 1;
        if(val(i,mid) <= val(q[r].p,mid))R = mid;
        else L = mid + 1;
    }
    return L;
}
void prin(int x){
    if(la[x] == x)return;
    prin(la[x]);
    for(int i = la[x]+1;i <= x;i++)printf("%s",c[i]),printf(i==x?"\n":" ");
}
void solve(){
    scanf("%d%lld%d",&n,&L,&p);L++;
    for(int i = 1;i <= n;i++)scanf("%s",c[i]),s[i] = s[i-1] + strlen(c[i]) + 1;
    l = r = 1,q[1] = {0,1,n};
    for(int i = 1;i <= n;i++){
        while(l < r && q[l].r < i)l++;q[l].l = i;
        int j = q[l].p;la[i] = j;
        f[i] = f[j] + W(j,i);
        while(l < r && val(i,q[r].l) <= val(q[r].p,q[r].l))r--;
        j = work(i,q[r].l,q[r].r+1);
        if(j <= n)q[r].r = j-1,q[++r] = {i,j,n};
    }
    if(f[n] > 1e18)printf("Too hard to arrange\n");
	else printf("%lld\n",(ll)f[n]),prin(n);
	printf("--------------------\n");
}
int main(){
	freopen("noi09_poet.in","r",stdin);
    freopen("noi09_poet.out","w",stdout);
    scanf("%d",&t);
    while(t--)solve();
 
	return 0;
 
}