kkk曾经在某地说过，【题目待添加】的意思是题目被和谐了。。。
by ceba_robot @ 2016-07-21 15:46:55
```cpp
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
typedef long long int64;
const int maxN = 100010, maxL = 60010;
const int64 INF = 0x3f3f3f3f3f3f3f3fLL;
const int64 LIM = int64(1e18);
struct Stack
{
int L, R, pos; Stack() {}
Stack(int L, int R, int pos): L(L), R(R), pos(pos) {}
} sta[maxN]; double F[maxN];
char poem[maxN][40]; int g[maxN], T, n, top, p;
int64 sum[maxN], f[maxN], len;
void printI64(int64 x)
{
static const int64 MOD = 1000000000;
if (x / MOD) printf("%d%09d", int(x / MOD), int(x % MOD));
else printf("%d", int(x));
return;
}
inline int64 pow(int64 a, int n)
{
int64 ans = 1, tmp = a;
for (; n; n >>= 1, tmp *= tmp) if (n & 1)
{
if (double(ans) * double(tmp) > LIM) return INF;
ans *= tmp;
}
return ans;
}
inline double pow(double a, int n)
{
double ans = 1, tmp = a;
for (; n; n >>= 1, tmp *= tmp) if (n & 1) ans *= tmp;
return ans;
}
void print(int i)
{
if (g[i]) print(g[i]);
for (int k = g[i] + 1; k < i; ++k) printf("%s ", poem[k]);
printf("%s\n", poem[i]);
}
inline int64 getf(int i, int j)
{
int64 tmp = pow(std::abs(i - j - 1 + sum[i] - sum[j] - len), p);
return (double)tmp + f[j] > LIM ? INF : tmp + f[j];
}
inline double getF(int i, int j)
{return pow((double)std::abs(i - j - 1 + sum[i] - sum[j] - len), p) + F[j];}
inline void update(int i)
{
while (i < sta[top].L && getF(sta[top].L, i)
< getF(sta[top].L, sta[top].pos))
sta[top - 1].R = sta[top].R, --top;
int L = sta[top].L, R = sta[top].R, p = R;
if (i >= L) L = i + 1;
while (L < R)
{
int Mid = (L + R) >> 1;
if (getF(Mid, i) < getF(Mid, sta[top].pos)) p = R = Mid;
else L = Mid + 1;
}
if (p < sta[top].R)
sta[top + 1] = Stack(p, sta[top].R, i), sta[top++].R = p;
return;
}
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d%d", &n, &len, &p);
for (int i = 1; i < n + 1; ++i)
scanf("%s", poem[i]), sum[i] = sum[i - 1] + strlen(poem[i]);
sta[top = 1] = Stack(1, n + 1, 0);
for (int i = 1, j = 1; i < n + 1; ++i)
{
if (i >= sta[j].R) ++j;
F[i] = getF(i, g[i] = sta[j].pos);
update(i);
}
if (F[n] > LIM) printf("Too hard to arrange\n");
else
{
for (int i = 1; i < n + 1; ++i) f[i] = getf(i, g[i]);
printI64(f[n]); printf("\n"); print(n);
}
printf("--------------------\n");
}
return 0;
} 我过了20分
```
by 3505515693qq @ 2017-01-17 10:25:57