题目大意
给定 $N$ 个 $6$ 面色子，价值为 $C_i$，每一面的概率均为 $\dfrac 16$，且有不同的权值 $A_{i,j}$。
从中选 $K$ 个色子，使得期望权值和的平方减去所选色子价值和最大。
Solution
考虑一个色子的概率生成函数
$$
f(z)=\frac 16\sum_{i=1}^6z^{A_i}
$$
则所有色子的概率生成函数为
$$
F(z)=\prod_{i=1}^K f(z)=\sum_iP(X=i)z^i
$$
考虑其平方的概率生成函数
$$
G(z)=\sum_iP(X=i)z^{i^2}
$$
对其求导得
$$
G’(z)=\sum_iP(X=i)i^2z^{i^2-1}=(zF’(z))’=F’(z)+zF’’(z)
$$
则期望
$$
\begin{aligned}
E(X^2)&=G’(1)=F’(1)+F’’(1)\\
&=\sum_{i=1}^Kf_i’(1)+2\sum_{i=1}^{K-1}\sum_{i=j+1}^{K}f’i(1)f’j(1)+\sum{i=1}^K f’’i(1)\\
&=\frac{1}{36}\left(\sum{i=1}^K\sum{j=1}^6 A_j\right)^2+\frac{1}{36}\sum_{i=1}^K\left(6A_j^2-\left(\sum_{j=1}^6 A_j\right)^2\right)
\end{aligned}
$$
故题目转化为给定 $N$ 个平面向量 $(x_i,y_i)$，从其中选 $K$ 个使得 $\left(\sum x_i\right)^2+\sum y_i$ 最大。
定理 令答案集合为 $S$，则 $\exists c\in \mathbb R,\forall i\in S,j\not\in S,cx_i+y_i\ge cx_j+y_j$。
证明
引理 1
对于给定的点集 $T$，$x^2+y$ 最大的点一定在 $T$ 构成的凸包 $P$ 上。引理 1 证明
考虑线段 $y=kx+b$ 上的一点 $(x,y)$，$x^2+y=x^2+kx+b$ 构成一个开口向上的抛物线，在线段端点处取到最值。
对于凸包内一点 $v\not\in P,\exists u\in P,s.t.$ 经过 $u,v$ 的直线交凸包于 $p$。如图所示，根据以上的结论，对于 $f(v)=x^2+y$，必然有 $f(E)< f(F)< f(C),f(D)$
引理 2 $\exists c\in \mathbb R,cx_i+y_i$ 最大 $\iff(x_i,y_i)$ 在凸包上。
引理 2 证明
考虑直线 $cx+y+b=0$，即 $c$ 决定了直线了斜率，在直线上下移动时只有在凸包处取到最值。
考虑 $K$ 个向量组成的 $\dbinom{N}{K}$ 个向量和，选择一个向量使 $x^2+y$ 最大，根据引理 1、2，即可得证。
这个性质等价于答案点集在一条直线的同一侧，将所有向量两两相减得到的 $O(N^2)$ 条直线的斜率即为我们需要枚举的 $c$ 值，极角排序不难解决，时间复杂度 $O(N^2\log N)$。