Card game

from functools import cache
from time import time
from math import ceil

@cache
def findMaxBuildIn(start, end, cards):
    # print(start,end)
    suMax = 0
    for ii in range(start, end-3+1):
        su = cards[ii+1]
        if start+3-1 < ii:
            ret = findMaxBuildIn(start, ii, cards)
            su += ret
            # print("LeftCut", start, ii, ret)
        if end-3-3+1 > ii:
            ret = findMaxBuildIn(ii+3, end, cards)
            su += ret
            # print("RightCut", ii+3, end, ret)
        if su > suMax:
            # print("max",su, suMax)
            suMax = su
    return suMax
# @cache
def findMax(start, end, cards, myCache):
    # print(start,end)
    suMax = 0
    for ii in range(start, end-3+1):
        su = cards[ii+1]
        if start+3-1 < ii:
            ret = 0
            if myCache[start][ii] !=-1: ret = myCache[start][ii]
            else: ret = findMax(start, ii, cards, myCache)
            su += ret
            # print("LeftCut", start, ii, ret)
        if end-3-3+1 > ii:
            ret = 0
            if myCache[ii+3][end] != -1: ret = myCache[ii+3][end]
            else: ret = findMax(ii+3, end, cards, myCache)
            su += ret
            # print("RightCut", ii+3, end, ret)
        if su > suMax:
            # print("max",su, suMax)
            suMax = su
    myCache[start][end] = suMax
    return suMax

def printCache(cach):
    ma = ceil(max(max(cach))**(1/10))
    for line in cach:
        for ch in line:
            print(f"{ch:2}", end=" ")
        print()
def dp(endMax, cards):
    if endMax < 3:
        return 0
    myCache = [-1 for _ in range(endMax-2)]
    myCache[0] = cards[1]
    for startLastSeg in range(1, endMax-2):
        ma = 0
        for ii in range(1, 3):
            if startLastSeg >= ii:
                if ma < myCache[startLastSeg-ii]:
                    ma = myCache[startLastSeg-ii]
        if startLastSeg >= 3:
            if ma < myCache[startLastSeg-3]+cards[startLastSeg+1]:
                ma = myCache[startLastSeg-3]+cards[startLastSeg+1]
        else:
            if ma < cards[startLastSeg+1]:
                ma = cards[startLastSeg+1]
        myCache[startLastSeg] = ma

    return myCache[-1]
 
cardCount = int(input())
cards = tuple([int(aa) for aa in input().split()])

# stupidBuildIn = findMaxBuildIn(0, cardCount, cards)
# t0 = time()
# myCache = [[-1 for _ in range(0,cardCount+1)] for _ in range(0,cardCount+1)]
# stupid = findMax(0, cardCount, cards, myCache)
t1 = time()
dpCount = dp(cardCount, cards)
t2 = time()
# print(stupid, dpCount)
print(dpCount)
# print(t1-t0,t2-t1)
# print(t2-t1)
# print(dpCount)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED