Sum (Codeforces 1442D)
Tags: Greedy, divide and conquer

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: 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: Print one integer: the maximum possible sum of all elements in Vasya's pocket after $$$k$$$ operations.


Sample Inputs:
3 3
2 5 10
3 1 2 3
2 1 20

Sample Outputs:
26

Solution (Python):
def main():
    (n, k) = [int(x) for x in input().split()]
    pls = []
    for _ in range(n):
        pls.append([int(x) for x in input().split()][1:])
    ans = 0
    dp = [0] * (k + 1)

    def f(a, total):
        nonlocal dp, ans
        if len(a) == 1:
            s = 0
            for (i, x) in enumerate(a[0]):
                if i >= k:
                    break
                s += x
                ans = max(ans, dp[k - (i + 1)] + s)
            return
        tmp = dp.copy()
        m = len(a) // 2
        (left, right) = (a[:m], a[m:])
        for (i, row) in enumerate(left):
            for j in range(k, len(row) - 1, -1):
                dp[j] = max(dp[j], dp[j - len(row)] + total[i])
        f(right, total[m:])
        dp = tmp
        for (i, row) in enumerate(right):
            for j in range(k, len(row) - 1, -1):
                dp[j] = max(dp[j], dp[j - len(row)] + total[m + i])
        f(left, total[:m])
    total = [sum(x) for x in pls]
    f(pls, total)
    print(ans)
main()

Solution (Python):
(standard_input, packages, dfs, hashing) = (1, 1, 0, 0)
if standard_input:
    import sys
    input = lambda : sys.stdin.readline().rstrip('\r\n')

    def I():
        return input()

    def II():
        return int(input())

    def MII():
        return map(int, input().split())

    def LI():
        return list(input().split())

    def LII():
        return list(map(int, input().split()))

    def LFI():
        return list(map(float, input().split()))

    def GMI():
        return map(lambda x: int(x) - 1, input().split())

    def LGMI():
        return list(map(lambda x: int(x) - 1, input().split()))
    inf = float('inf')
if packages:
    from io import BytesIO, IOBase
    import math
    import random
    import os
    import bisect
    import typing
    from collections import Counter, defaultdict, deque
    from copy import deepcopy
    from functools import cmp_to_key, lru_cache, reduce
    from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
    from itertools import accumulate, combinations, permutations, count
    from operator import add, iand, ior, itemgetter, mul, xor
    from string import ascii_lowercase, ascii_uppercase, ascii_letters
    from typing import *
    BUFSIZE = 4096

    class FastIO(IOBase):
        newlines = 0

        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = 'x' in file.mode or 'r' not in file.mode
            self.write = self.buffer.write if self.writable else None

        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
            self.newlines = 0
            return self.buffer.read()

        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b'\n') + (not b)
                ptr = self.buffer.tell()
                (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
            self.newlines -= 1
            return self.buffer.readline()

        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                (self.buffer.truncate(0), self.buffer.seek(0))

    class IOWrapper(IOBase):

        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode('ascii'))
            self.read = lambda : self.buffer.read().decode('ascii')
            self.readline = lambda : self.buffer.readline().decode('ascii')
    sys.stdin = IOWrapper(sys.stdin)
    sys.stdout = IOWrapper(sys.stdout)
if dfs:
    from types import GeneratorType

    def bootstrap(f, stack=[]):

        def wrappedfunc(*args, **kwargs):
            if stack:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if type(to) is GeneratorType:
                        stack.append(to)
                        to = next(to)
                    else:
                        stack.pop()
                        if not stack:
                            break
                        to = stack[-1].send(to)
                return to
        return wrappedfunc
if hashing:
    RANDOM = random.getrandbits(20)

    class Wrapper(int):

        def __init__(self, x):
            int.__init__(x)

        def __hash__(self):
            return super(Wrapper, self).__hash__() ^ RANDOM
read_from_file = 0
if read_from_file:
    file = open('input.txt', 'r').readline().strip()[1:-1]
    fin = open(file, 'r')
    input = lambda : fin.readline().strip()
    output_file = open('output.txt', 'w')

    def fprint(*args, **kwargs):
        print(*args, **kwargs, file=output_file)
(n, k) = MII()
lengths = []
tot = []
lsts = []
for _ in range(n):
    (m, *nums) = MII()
    lengths.append(m)
    tot.append(sum(nums))
    lsts.append(list(accumulate(nums, initial=0)))
ans = 0
dp = [0] * (k + 1)

def solve(l, r):
    global ans, dp
    if l == r:
        for (i, v) in enumerate(lsts[l]):
            if i <= k:
                ans = max(ans, dp[k - i] + v)
        return
    m = (l + r) // 2
    tmp = dp[:]
    for i in range(l, m + 1):
        for j in range(k, lengths[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - lengths[i]] + tot[i])
    solve(m + 1, r)
    dp = tmp
    for i in range(m + 1, r + 1):
        for j in range(k, lengths[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - lengths[i]] + tot[i])
    solve(l, m)
solve(0, n - 1)
print(ans)

Solution (Python):
import sys
import random
input = sys.stdin.readline
rd = random.randint(10 ** 9, 2 * 10 ** 9)
(n, k) = map(int, input().split())
li = []
for _ in range(n):
    a = list(map(int, input().split()))
    S = [0] * min(k + 1, len(a))
    for i in range(1, len(S)):
        S[i] = S[i - 1] + a[i]
    li.append(S)
dp = [0] * (k + 1)
ans = 0

def solve(l, r):
    global ans, dp
    if l == r:
        for i in range(min(k + 1, len(li[l]))):
            ans = max(ans, dp[k - i] + li[l][i])
        return
    mid = (l + r) // 2
    tmp = dp[:]
    for idx in range(mid + 1, r + 1):
        le = len(li[idx]) - 1
        for x in range(k, le - 1, -1):
            dp[x] = max(dp[x], dp[x - le] + li[idx][le])
    solve(l, mid)
    dp = tmp[:]
    for idx in range(l, mid + 1):
        le = len(li[idx]) - 1
        for x in range(k, le - 1, -1):
            dp[x] = max(dp[x], dp[x - le] + li[idx][le])
    solve(mid + 1, r)
solve(0, n - 1)
print(ans)