Porcelain (Codeforces 148E)
Tags: DP, dp

During her tantrums the princess usually smashes some collectable porcelain. Every furious shriek is accompanied with one item smashed.The collection of porcelain is arranged neatly on n shelves. Within each shelf the items are placed in one row, so that one can access only the outermost items — the leftmost or the rightmost item, not the ones in the middle of the shelf. Once an item is taken, the next item on that side of the shelf can be accessed (see example). Once an item is taken, it can't be returned to the shelves.You are given the values of all items. Your task is to find the maximal damage the princess' tantrum of m shrieks can inflict on the collection of porcelain.

Input: The first line of input data contains two integers n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ 10000). The next n lines contain the values of the items on the shelves: the first number gives the number of items on this shelf (an integer between 1 and 100, inclusive), followed by the values of the items (integers between 1 and 100, inclusive), in the order in which they appear on the shelf (the first number corresponds to the leftmost item, the last one — to the rightmost one). The total number of items is guaranteed to be at least m.

Output: Output the maximal total value of a tantrum of m shrieks.

Note: In the first case there are two shelves, each with three items. To maximize the total value of the items chosen, one can take two items from the left side of the first shelf and one item from the right side of the second shelf.In the second case there is only one shelf, so all three items are taken from it — two from the left side and one from the right side.

Sample Inputs:
2 3
3 3 7 2
3 4 1 5

1 3
4 4 3 1 2

Sample Outputs:
15

9

Solution (Python):
""""""
import sys
import os
from io import BytesIO, IOBase
from types import GeneratorType
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, **kwargs):
        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')

def debug(func):

    def wrapper(*args, **kwargs):
        res = func(*args, **kwargs)
        print('----------------')
        return res
    return wrapper

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
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

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

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

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

def LII():
    return list(map(int, 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()))
from itertools import accumulate, combinations, permutations, groupby
MOD = int(1000000000.0 + 7)
M9D = int(998244353)
INF = int(1e+20)

def solve():
    (n, m) = MI()
    dp = [0] * (m + 1)
    mn = 0
    for _ in range(n):
        (k, *arr) = LII()
        pres = [0] + list(accumulate(arr))
        mx = [0] * (k + 1)
        for i in range(1, k + 1):
            mx[i] = pres[i]
            for j in range(i):
                mx[i] = max(mx[i], pres[j] + pres[-1] - pres[k - i + j])
        mn = min(m, mn + k)
        for i in range(mn, 0, -1):
            for j in range(1, min(k, i) + 1):
                dp[i] = max(dp[i], dp[i - j] + mx[j])
    print(dp[-1])
    return
solve()

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
dp = [0]
c = 0
for _ in range(n):
    a = list(map(int, input().split()))[1:]
    l = len(a)
    u = [0]
    for i in a:
        u.append(u[-1] + i)
    s = u[l]
    ma = [0] * (l + 1)
    for i in range(l):
        ui = u[i]
        for j in range(i + 1, l + 1):
            k = l - (j - i)
            ma[k] = max(ma[k], s - (u[j] - ui))
    ma[l] = s
    c += l
    dp0 = [0] * (c + 1)
    for i in range(c - l + 1):
        dpi = dp[i]
        for j in range(l + 1):
            dp0[i + j] = max(dp0[i + j], dpi + ma[j])
    dp = dp0
ans = dp[m]
print(ans)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase

class FastO:

    def __init__(self, fd=1):
        stream = BytesIO()
        self.flush = lambda : os.write(fd, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
        self.write = lambda b: stream.write(b.encode())

class ostream:

    def __lshift__(self, a):
        sys.stdout.write(str(a))
        return self
(sys.stdout, cout) = (FastO(), ostream())
(numbers, num, sign) = ([], 0, 1)
for char in os.read(0, os.fstat(0).st_size):
    if char >= 48:
        num = num * 10 + char - 48
    elif char == 45:
        sign = -1
    elif char != 13:
        numbers.append(sign * num)
        (num, sign) = (0, 1)
if char >= 48:
    numbers.append(sign * num)
getnum = numbers[::-1].pop

def main():
    (n, m) = (getnum(), getnum())
    _dp = [[] for _ in range(n)]
    for i in range(n):
        ni = getnum()
        ai = [getnum() for _ in range(ni)]
        cumsum = [0] * (ni + 1)
        for j in range(ni):
            cumsum[j + 1] = cumsum[j] + ai[j]
        _dpi = [0] * (ni + 1)
        for j in range(ni + 1):
            for k in range(j, ni + 1):
                _dpi[ni + j - k] = max(_dpi[ni + j - k], cumsum[j] + cumsum[-1] - cumsum[k])
        _dp[i] = _dpi
    dp = [0] * (m + 1)
    for i in range(n):
        _dpi = _dp[i]
        for j in reversed(range(m + 1)):
            dpj = dp[j]
            for k in range(min(len(_dp[i]), j + 1)):
                dpj = max(dpj, _dpi[k] + dp[j - k])
            dp[j] = dpj
    cout << dp[m]
if __name__ == '__main__':
    main()