Problem p03032 (python)

Fixed submission:
import sys
# gcd
from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
from collections import deque
# import math
# from functools import reduce
#
# input関係の定義
# fin = open('in_3.txt', 'r')
# sys.stdin = fin
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word


if __name__ == '__main__':

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    V = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    # write code

    left = []
    right = []
    left.append(0)
    right.append(0)
    left.append(max(V[0], 0))
    right.append(max(V[-1], 0))
    for i in range(2, 2*N+1):
        tmp_max = 0
        for j in range(-(-i // 2), i+1):
            tmp_V = V[:j]
            tmp_V.sort()
            # print(i, j, tmp_V[i - 2 * j:])
            if tmp_max < sum(tmp_V[i - 2 * j:]):
                tmp_max = sum(tmp_V[i - 2 * j:])
        # print(tmp_max)
        left.append(tmp_max)

    for i in range(2, 2*N+1):
        tmp_max = 0
        for j in range(-(-i // 2), i+1):
            tmp_V = V[-j:]
            tmp_V.sort()
            if tmp_max < sum(tmp_V[i - 2 * j:]):
                tmp_max = sum(tmp_V[i - 2 * j:])
        # print(tmp_max)
        right.append(tmp_max)
    ans = []
    # print(left)
    # print(right)
    sV = sum([i for i in V if i >= 0])
    # print(sV)
    for j in range(0, min(2*N, K) + 1):
        tmp_ans = -10**9
        for i in range(j+1):
            if tmp_ans < left[i] + right[j - i]:
                tmp_ans = left[i] + right[j - i]
        ans.append(tmp_ans)
    print(min(max(ans), sV))

Buggy submission (verdict: Runtime Error):
import sys
# gcd
from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
from collections import deque
# import math
# from functools import reduce
#
# input関係の定義
# fin = open('in_3.txt', 'r')
# sys.stdin = fin
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word


if __name__ == '__main__':

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    V = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    # write code
    left = [-10 ** 9] * (K+10)
    right = [-10 ** 9] * (K + 10)
    left[0] = 0
    right[0] = 0
    left[1] = V[0]
    right[1] = V[-1]
    for i in range(2, N+1):
        tmp_max = 0
        for j in range(i // 2, i):
            tmp_V = V[:j]
            tmp_V.sort()
            if tmp_max < sum(tmp_V[i - 2 * j:]):
                tmp_max = sum(tmp_V[i - 2 * j:])
        # print(tmp_max)
        left[i] = tmp_max

    for i in range(2, N+1):
        tmp_max = 0
        for j in range(i // 2, i):
            tmp_V = V[-j:]
            tmp_V.sort()
            if tmp_max < sum(tmp_V[i - 2 * j:]):
                tmp_max = sum(tmp_V[i - 2 * j:])
        # print(tmp_max)
        right[i] = tmp_max
    ans = []
    # print(left)
    # print(right)
    for j in range(0, min(N, K) + 1):
        tmp_ans = -10**9
        for i in range(j+1):
            if tmp_ans < left[i] + right[j - i]:
                tmp_ans = left[i] + right[j - i]
        ans.append(tmp_ans)
    print(max(ans))

Buggy submission (verdict: Runtime Error):
import sys
# gcd
from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
from collections import deque
# import math
# from functools import reduce
#
# input関係の定義
# fin = open('in_1.txt', 'r')
# sys.stdin = fin
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word


if __name__ == '__main__':

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    V = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"

    # write code
    left = [-10 ** 9] * (K+10)
    right = [-10 ** 9] * (K + 10)
    left[0] = 0
    right[0] = 0
    left[1] = V[0]
    right[1] = V[-1]
    for i in range(2, N+1):
        tmp_max = 0
        for j in range(i // 2, i):
            tmp_V = V[:j]
            tmp_V.sort()
            if tmp_max < sum(tmp_V[i - 2 * j:]):
                tmp_max = sum(tmp_V[i - 2 * j:])
        # print(tmp_max)
        left[i] = tmp_max

    for i in range(2, N+1):
        tmp_max = 0
        for j in range(i // 2, i):
            tmp_V = V[-j:]
            tmp_V.sort()
            if tmp_max < sum(tmp_V[i - 2 * j:]):
                tmp_max = sum(tmp_V[i - 2 * j:])
        # print(tmp_max)
        right[i] = tmp_max
    ans = []
    # print(left)
    # print(right)
    for j in range(0, N + 1):
        tmp_ans = -10**9
        for i in range(j+1):
            if tmp_ans < left[i] + right[j - i]:
                tmp_ans = left[i] + right[j - i]
        ans.append(tmp_ans)
    print(max(ans))