Sum
Contest: VK Cup 2019-2020 - Final Round (Engine)
Difficulty rating: 2800
Tags: divide and conquer, greedy

You are given $$$n$$$ non-decreasing arrays of non-negative numbers.

Vasya repeats the following operation $$$k$$$ times:

- Selects a non-empty array.
- Puts the first element of the selected array in his pocket.
- Removes the first element from the selected array.

Vasya wants to maximize the sum of the elements in his pocket.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 3\,000$$$): the number of arrays and operations.

Each of the next $$$n$$$ lines contain an array. The first integer in each line is $$$t_i$$$ ($$$1 \le t_i \le 10^6$$$): the size of the $$$i$$$-th array. The following $$$t_i$$$ integers $$$a_{i, j}$$$ ($$$0 \le a_{i, 1} \le \ldots \le a_{i, t_i} \le 10^8$$$) are the elements of the $$$i$$$-th array.

It is guaranteed that $$$k \le \sum\limits_{i=1}^n t_i \le 10^6$$$.

Output format:
Print one integer: the maximum possible sum of all elements in Vasya's pocket after $$$k$$$ operations.

Constraints:
Time limit: 1.5 s
Memory limit: 512.0 MB

Example input:
3 3
2 5 10
3 1 2 3
2 1 20

Example output:
26

Editorial:
Straightforward dp solution, where $$$s(i, j)$$$ – max possible sum after $$$j$$$ operations on first $$$i$$$ arrays and transition in $$$O(k)$$$, has complexity of $$$O(nk^2)$$$ or precisely $$$O(k \cdot min(nk, \sum\limits_{i=1}^n t_i))$$$ and doesn't fit into the time limit.
Taking into account the fact that the arrays are sorted helps to optimize it.
Consider the optimal solution. Let's denote as $$$x_i$$$ number of operations on $$$i$$$-th array. Let's call the array partially removed if we applied at least one operation to that array, but the array is not yet empty.
Consider two partially removed arrays within the optimal solution and integers $$$p$$$ and $$$q$$$ where $$$0 < x_p < t_p$$$ and $$$0 < x_q < t_q$$$. Assume, without loss of generality, $$$a_{p, x_p+1} \le a_{q, x_q+1}$$$. Let $$$y = min(x_p, t_q - x_q) \ge 1$$$. If we replace $$$y$$$ operations on $$$p$$$-th array with $$$y$$$ operations on $$$q$$$-th array, total sum will increase by $$$\sum\limits_{i=1}^y a_{q, x_q + i} - \sum\limits_{i=1}^y a_{p, x_p + 1 - i} \ge y \cdot a_{q, x_q + 1} - y \cdot a_{p, x_p + 1} \ge 0$$$, but the number of partially removed arrays will lower by 1. We can repeat that substitution until we get a single partially removed array.
Now we need to identify the single partially removed array in the final solution. Every other array can either all be Vasya's pocket, or remain as is. We can solve the knapsack problem with $$$(n-1)$$$ items, with array sizes as weights and sum of array's elements as value. For each $$$0 \le w \le k$$$ we need to find $$$g(w)$$$ – max possible total value of items with total weight $$$w$$$. The only remaining step is to brute force the size of prefix, Vasya removed from the single partially removed array and combine it with $$$g(w)$$$.
Solving each knapsack problem independently results in $$$O(n^2k + \sum\limits_{i=1}^n t_i)$$$ complexity, but the similarities between the problems allows to optimize down to $$$O(kn\log n)$$$ using divide and conquer approach.
Let's split the items into two halves of approximately similar size. Before going in recursively into the first half we will relax dp values with each element of the second half (just like in usual knapsack problem) and undo the changes after.
This way as soon as we reach the subset with just one piece we have already calculated dp for every other piece. Adding each piece into dp takes $$$O(\log n)$$$, each relaxation takes $$$O(k)$$$, final complexity is $$$O(kn\log n + \sum\limits_{i=1}^n t_i)$$$.