Link

Sol

贪心策略：除了一个数组不选完外，其余的数组全部选完为最优。

那么现在怎么样来选择数组。假如是全部都是选整个数组的话，我们把数组长度看成体积，整个数组的和看成价值做背包即可。现在的问题是，我们有一个数组不能全部选满，怎么做？

采用分治的办法解决。是不是我们可以把所有数组分成两项来合并答案，当我们递归进单个数组的时候对这个数组进行背包，更新答案。否则我们可以先把每次分治的左边的数组全部选满，做一次背包。拷贝下当前的dp数组，来算那个不选满的数组出现在右边的答案。再同样处理左边即可。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 3e3 + 5;

int n, k, res;
int f[SIZE], tot[SIZE];
std::vector < int > a[SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

void dp(int x) {
    int len = tot[x];
    for (int i = k; i >= len; -- i) f[i] = std::max(f[i], f[i - len] + a[x][len]);
}

void sol(int l, int r) {
    if (l == r) {
        for (int i = 1; i <= std::min(k, tot[l]); ++ i) res = std::max(res, f[k - i] + a[l][i]);
        return;
    }
    int mid = (l + r) >> 1, tmp[SIZE];
    memset(tmp, 0, sizeof(tmp));
    for (int i = 0; i <= k; ++ i) tmp[i] = f[i];
    for (int i = l; i <= mid; ++ i) dp(i);
    sol(mid + 1, r);
    for (int i = 0; i <= k; ++ i) f[i] = tmp[i];
    for (int i = mid + 1; i <= r; ++ i) dp(i);
    sol(l, mid);
    for (int i = 0; i <= k; ++ i) f[i] = tmp[i];
} 

signed main() {
    // freopen("code.in", "r", stdin);
    n = read(), k = read();
    for (int i = 1; i <= n; ++ i) {
        tot[i] = read(), a[i].push_back(0);
        for (int j = 1, x; j <= tot[i]; ++ j) {
            x = read(), a[i].push_back(a[i][j - 1] + x);
        }
    }
    sol(1, n);
    printf("%lld\n", res);
    return 0;
}