题目
给定 (n) 组话，第 (i) 组话包含 (k_i) 句话，其中按照长度从小到大排序后的第 (j) 句话长度为 (j)，贡献为 (a_{i,j})。
现在可以从每组话中选且仅选一句话。求当方案中话的长度之和分别为 (t,tin[n,sum k]) 时最大的贡献之和。
对于 (100\%) 的数据，满足 (1le nle 10^5,1le k_ile 5,0le a_{i,j}le 10^9)。
分析
容易观察出一个 DP 来：设 (f_{i,j}) 为考虑前 (i) 组话后，总长度为 (j) 的最大贡献之和：
这个转移做的就是 (max) 卷积。如果 (a) 保证凸性，那么这个转移反手一个分治 Minkowski 和就结束了。
但是显然这个 (a) 根本不包含任何凸性，所以我们得再思考一下。
首先，将所有话的长度减一，这样所有话的长度一定落在 ([0,4]) 里面。
有趣的是，这样的数构成的可重集，即包含的数均落在 ([0,4]) 内部的可重集，如果它们的和为 24，那么一定存在某种分拆方案，给出两个可重集，和均为 12。这个可以使用搜索来验证。
那么考虑 (f_{i,j}) 到 (f_{i,j+24})（如果两者均有意义），对于这和为 24 的可重集，我们可以将它们分拆为两个和为 12 的可重集。贪心地想，我们肯定会将贡献较大的一个可重集优先给 (f_{i,j+12}-f_{i,j})，再将较小的一个给到 (f_{i,j+24}-f_{i,j+12})。这样我们得到的不等式是：
注意到，这里 (j,j+12,j+24) 一定对 (K=12) 同余。因此，我们实际上发现了，对 (K) 同余的 DP 值一定是凸的。
那么这就好办了。虽然两个 DP 数组合并的时候，我们不能直接套 Minkowski 和，但是我们可以将每组凸壳都拿出来两两合并。这样我们需要进行 (K^2) 次合并，每次复杂度为 (O(frac{n}{K}))，单次合并的复杂度即为 (O(nK))。结合分治算法我们得到了 (O(nKlog n)) 的算法。
小结：
- 虽然图形本身不一定凸，但是我们可以将图形拆分成若干凸壳来两两合并，这个方法其实是通用的；
- 关注一下这里提到的可重集拆分的结论（是不是还有类似的？）；当然，这种推导凸性的方法也可以关注一下。
代码
#include <cstdio>
#include <vector>
#include <iostream>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
typedef long long LL;
const int MAXN = 1e5 + 5;
template<typename _T>
void read( _T &x )/*{{{*/
{
x = 0; char s = getchar(); bool f = false;
while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
if( f ) x = - x;
}/*}}}*/
template<typename _T>
void write( _T x )/*{{{*/
{
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + '0' );
}/*}}}*/
struct Poly/*{{{*/
{
std :: vector<LL> vec;
Poly(): vec() {}
Poly( int N ): vec( N ) {}
inline unsigned size() const { return vec.size(); }
LL operator [] ( const int idx ) const { return vec[idx]; }
inline void push_back( const LL v ) { vec.push_back( v ); }
friend Poly operator * ( const Poly &a, const Poly &b );
};/*}}}*/
int A[MAXN][10], len[MAXN];
int N;
inline void Upt( LL &x, const LL v ) { x = std :: max( x, v ); }
Poly operator * ( const Poly &a, const Poly &b )/*{{{*/
{
static LL tmp[MAXN << 2], A[MAXN << 2], B[MAXN << 2];
Poly ret( a.size() + b.size() - 1 );
int n = a.size(), m = b.size(), p, q, k = 0;
rep( r1, 0, 11 ) rep( r2, 0, 11 )
{
p = q = k = 0;
for( int i = r1 ; i < n ; i += 12 ) A[p ++] = a[i];
for( int i = r2 ; i < m ; i += 12 ) B[q ++] = b[i];
if( p == 0 || q == 0 ) continue;
per( i, p - 1, 1 ) A[i] -= A[i - 1];
per( i, q - 1, 1 ) B[i] -= B[i - 1];
for( int i = 1, j = 1 ; i < p || j < q ; )
if( i < p && ( j >= q || A[i] >= B[j] ) )
tmp[++ k] = A[i ++];
else tmp[++ k] = B[j ++];
tmp[0] = A[0] + B[0];
rep( i, 1, k ) tmp[i] += tmp[i - 1];
rep( i, 0, k ) Upt( ret.vec[i * 12 + r1 + r2], tmp[i] );
}
return ret;
}/*}}}*/
Poly Merge( const int l, const int r )/*{{{*/
{
if( l == r )
{
Poly ret( 0 );
rep( i, 0, len[l] - 1 )
ret.push_back( A[l][i] );
return ret;
}
int mid = ( l + r ) >> 1;
return Merge( l, mid ) *
Merge( mid + 1, r );
}/*}}}*/
int main()
{
read( N );
rep( i, 1, N )
{
read( len[i] );
rep( j, 0, len[i] - 1 ) read( A[i][j] );
}
Poly ans( Merge( 1, N ) );
rep( i, 0, ( int ) ans.size() - 1 )
write( ans[i] ), putchar( i == ( int ) ans.size() - 1 ? '
' : ' ' );
return 0;
}