Problem:


Score : 100 points

Problem Statement

Taro's summer vacation starts tomorrow, and he has decided to make plans for it now.

The vacation consists of N days.
For each i (1 \leq i \leq N), Taro will choose one of the following activities and do it on the i-th day:

A: Swim in the sea. Gain a_i points of happiness.

B: Catch bugs in the mountains. Gain b_i points of happiness.

C: Do homework at home. Gain c_i points of happiness.

As Taro gets bored easily, he cannot do the same activities for two or more consecutive days.

Find the maximum possible total points of happiness that Taro gains.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq a_i, b_i, c_i \leq 10^4

Input

Input is given from Standard Input in the following format:

N
a_1 b_1 c_1
a_2 b_2 c_2
:
a_N b_N c_N

Output

Print the maximum possible total points of happiness that Taro gains.

Sample Input 1

3
10 40 70
20 50 80
30 60 90

Sample Output 1

210

If Taro does activities in the order C, B, C, he will gain 70 + 50 + 90 = 210 points of happiness.

Sample Input 2

1
100 10 1

Sample Output 2

100

Sample Input 3

7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1

Sample Output 3

46

Taro should do activities in the order C, A, B, A, C, B, A.



Sample input:
3
10 40 70
20 50 80
30 60 90


Sample output:
210

Submission status: Wrong Answer

Solution code:
a = int(input())

b = []
m = 0
for i in range(a):
	b.append(list(map(int,input().split())))

c = [[0,0,0] for i in range(a+1)]

for i in range(a):
	for j in range(3):
		for k in range(3):
			if j == k:
				continue
			else:
				c[i+1][k] = max(c[i+1][k],c[i][k] + b[i][j])

print(max(c[-1]))

Submission status: Wrong Answer

Solution code:
N = int(input())
L = [list(map(int, input().split())) for i in range(N)]
dp = [0] * (N + 1)
dp[1] = max(L[0])
flag = L[0].index(max(L[0]))
for i in range(1, N):
    dp[i+1] = dp[i] + max(L[i][flag-1], L[i][flag-2])
    flag = L[i].index(max(L[i][flag-1], L[i][flag-2]))
print(dp[-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
a,b,c = [],[],[]
for i in range(N):
    aa,bb,cc = map(int,input().split())
    a.append(aa)
    b.append(bb)
    c.append(cc)

dp = [ [0 for i in range(3)] for i in range(N+1)]

dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]

for i in range(1,N):
    for j in range(3):
        if j == 0:
            if b[i] == c[i]:
                dp[i][1] = max(dp[i][1] , dp[i-1][j] + b[i])
                dp[i][2] = max(dp[i][2] , dp[i-1][j] + c[i])
            elif b[i] > c[i]:
                dp[i][1] = max(dp[i][1] , dp[i-1][j] + b[i])
            else:
                dp[i][2] = max(dp[i][2] , dp[i-1][j] + c[i])
        elif j == 1:
            if a[i] == c[i]:
                dp[i][0] = max(dp[i][0] , dp[i-1][j] + a[i])
                dp[i][2] = max(dp[i][2] , dp[i-1][j] + c[i])
            elif a[i] > c[i]:
                dp[i][0] = max(dp[i][0] , dp[i-1][j] + a[i])
            else:
                dp[i][2] = max(dp[i][2] , dp[i-1][j] + c[i])
        elif j == 2:
            if a[i] == b[i]:
                dp[i][0] = max(dp[i][0] , dp[i-1][j] + a[i])
                dp[i][1] = max(dp[i][1] , dp[i-1][j] + b[i])
            elif a[i] > b[i]:
                dp[i][0] = max(dp[i][0] , dp[i-1][j] + a[i])
            else:
                dp[i][1] = max(dp[i][1] , dp[i-1][j] + b[i])

print(max([dp[N-1][0] , dp[N-1][1] , dp[N-1][2]]))

Submission status: Wrong Answer

Solution code:
from itertools import cycle
N = int(input())
Happiness = [sorted([int(i) for i in input().split()]) for j in range(N)]

ans1 = ans2 = 0
for move, choice1, choice2 in zip(Happiness, cycle([1, 2]), cycle([2, 1])):
    ans1 += move[choice1]
    ans2 += move[choice2]

print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = []
B = []
C = []

for i in range(N) :
    a,b,c = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
ans = 0
res = 0
state = -1

for k in range(3) :
    state = k
    ans = 0
    for i in range(N) :
        if state == 0 :
            if B[i] < C[i] :
                ans += C[i]
                state = 2
            elif B[i] > C[i] :
                ans += B[i]
                state = 1
            else :
                ans += C[i]
                state = -1
        elif state == 1 :
            if A[i] < C[i] :
                ans += C[i]
                state = 2
            elif A[i] > C[i] :
                ans += A[i]
                state = 0
            else :
                ans += A[i]
                state = -1
        elif state == 2 :
            if A[i] < B[i] :
                ans += B[i]
                state = 1
            elif A[i] > B[i] :
                ans += A[i]
                state = 0
            else :
                ans += B[i]
                state = -1
        else :
            ans += max(A[i],B[i],C[i])
            ma = max(A[i],B[i],C[i])
            if (A[i] == B[i] == ma) or (B[i] == C[i] == ma) or (C[i] == A[i] == ma) :
                state = -1
            else :
                state = np.argmax([A[i],B[i],C[i]])
    if ans > res :
        res = ans
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = []
B = []
C = []

for i in range(N) :
    a,b,c = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
ans = 0
state = -1
for i in range(N) :
    if state == 0 :
        if B[i] < C[i] :
            ans += C[i]
            state = 2
        elif B[i] > C[i] :
            ans += B[i]
            state = 1
        else :
            ans += C[i]
            state = -1
    elif state == 1 :
        if A[i] < C[i] :
            ans += C[i]
            state = 2
        elif A[i] > C[i] :
            ans += A[i]
            state = 0
        else :
            ans += A[i]
            state = -1
    elif state == 2 :
        if A[i] < B[i] :
            ans += B[i]
            state = 1
        elif A[i] > B[i] :
            ans += A[i]
            state = 0
        else :
            ans += B[i]
            state = -1
    else :
        ans += max(A[i],B[i],C[i])
        ma = max(A[i],B[i],C[i])
        if (A[i] == B[i] == ma) or (B[i] == C[i] == ma) or (C[i] == A[i] == ma) :
            state = -1
        else :
            state = np.argmax([A[i],B[i],C[i]])
    #print(state,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = []
B = []
C = []

for i in range(N) :
    a,b,c = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
res = 0
for k in range(3) :
    state = k
    ans = 0
    for i in range(N) :
        if state == 0 :
            if B[i] < C[i] :
                ans += C[i]
                state = 2
            elif B[i] > C[i] :
                ans += B[i]
                state = 1
            else :
                ans += C[i]
                state = -1
        elif state == 1 :
            if A[i] < C[i] :
                ans += C[i]
                state = 2
            elif A[i] > C[i] :
                ans += A[i]
                state = 0
            else :
                ans += A[i]
                state = -1
        elif state == 2 :
            if A[i] < B[i] :
                ans += B[i]
                state = 1
            elif A[i] > B[i] :
                ans += A[i]
                state = 0
            else :
                ans += B[i]
                state = -1
        else :
            ans += max(A[i],B[i],C[i])
            state = np.argmax([A[i],B[i],C[i]])
    if res < ans :
        res = ans
print(res)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[list(map(int, input().split())) for i in range(n)]
dp=[[0]*3 for i in range(n)]
dp[0]=a[0]
for i in range(1,n):
    for j in range(3):
        dp[i][j]=max(dp[i-1][(j+1)%3]+a[i][(j+1)%3],dp[i-1][(j+2)%3]+a[i][(j+2)%3])
print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]


score = [[0] * N for i in range(3)] # N - 1 is used as -1
for i in range(N):
    for dst in range(3):
        tmp = abc[i][dst]
        for src in range(3):
            if dst == src: continue
            elif score[src][i - 1] + tmp > score[dst][i]:
                score[dst][i] = score[src][i - 1] + tmp

# print('#', score)
print(max((score[0][-1], score[1][-1], score[2][-1])))

Submission status: Wrong Answer

Solution code:
N = int(input())
happy = 0
d = {}
post, post1 = None, None
for i in range(N):
  a, b, c = map(int,input().split())
  d[1], d[2], d[3] = a, b, c
  max_key = max(d, key = d.get)
  if(max_key != post):
    happy += d[max_key]
    post = max_key
  else:
    d[max_key] = 0
    max_key = max(d, key = d.get)
    if(max_key != post1):
      happy += d[max_key]
      post = max_key
    else:
      d[max_key] = 0
      max_key = max(d, key = d.get)
      happy += d[max_key]
      post1 = max_key
print(happy)

Submission status: Wrong Answer

Solution code:
N = int(input())
happy = 0
d = {}
post, post1 = None, None
for i in range(N):
  a, b, c = map(int,input().split())
  d[1], d[2], d[3] = a, b, c
  max_key = max(d, key = d.get)
  if(max_key != post):
    happy += d[max_key]
  else:
    d[max_key] = 0
    max_key = max(d, key = d.get)
    if(max_key != post1):
      happy += d[max_key]
    else:
      d[max_key] = 0
      max_key = max(d, key = d.get)
      happy += d[max_key]
    post1 = max_key
  post = max_key
print(happy)

Submission status: Wrong Answer

Solution code:
N = int(input())
happy = 0
d = {}
post = None
for i in range(N):
  a, b, c = map(int,input().split())
  d[1], d[2], d[3] = a, b, c
  max_value = max(d.values())
  max_key = max(d, key = d.get)
  if(max_key != post):
    happy += max_value
  else:
    d[max_key] = 0
    max_key = max(d, key = d.get)
    happy += d[max_key]
  post = max_key
print(happy)

Submission status: Wrong Answer

Solution code:
def amax(l):
    am = 0
    am2 = 0
    for i in range(1, len(l)):
        if l[i] > l[am]:
            am2 = am
            am = i
        elif l[i] > l[am2]:
            am2 = i
    return am, am2

def vacation(abc):
    sel = amax(abc[0])[0]
    p = abc[0][sel]
    for i in range(1, len(abc)):
        am, am2 = amax(abc[i])
        if am != sel:
            p += abc[i][am]
            sel = am
        else:
            p += abc[i][am2]
            sel = am2
    return p

N = int(raw_input())
abc = []
for _ in range(N):
    abc.append(map(int, raw_input().split()))

print(vacation(abc))

Submission status: Wrong Answer

Solution code:
N = int(input())
L1 = []
L2 = []

for i in range(N) :
    l = list(map(int,input().split()))
    l = sorted(l)
    if i % 2 :
        L1.append(l[1])
        L2.append(l[2])
    else :
        L1.append(l[2])
        L2.append(l[1])
        
print(max(sum(L1),sum(L2)))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = []
for i in range(N):
  a.append(list(map(int,input().split())))
A = [a[0][0]]
B = [a[0][1]]
C = [a[0][2]]
if N == 1:
  print(max(a))
else:
  for i in range(N-1):
    A.append(max(B[i],C[i])+a[i+1][0])
    B.append(max(A[i],C[i])+a[i+1][1])
    C.append(max(A[i],B[i])+a[i+1][2])
  print(max(A[N-1],B[N-1],C[N-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
N=int(input())
ABC=[]
for _ in range(N):
    ABC.append(list(map(int,input().split())))
def dynam(n):
    if n>1:
        a=max(dynam(n-1)[1]+ABC[n-1][0],
              dynam(n-1)[2]+ABC[n-1][0])
        b=max(dynam(n-1)[0]+ABC[n-1][1],
              dynam(n-1)[2]+ABC[n-1][1])
        c=max(dynam(n-1)[0]+ABC[n-1][2],
              dynam(n-1)[1]+ABC[n-1][2])
        return (a,b,c)
    return tuple(ABC[0])
print(max(dynam(N)))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
a, b, c = [], [], []
for i in range(n):
    x,y,z = gil()
    a.append(x)
    b.append(y)
    c.append(z)
    
mem = {}
def rp(i, p, h):
    global a,b,c,n
    if i >= n:
        return h
    
    av = [rp(i+1, 0, h+a[i]), rp(i+1, 1, h+b[i]), rp(i+1, 2, h+c[i])]
    if p != -1:
        av[p] = 0
    ans = max(av)
    return ans
ans = rp(0, -1, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = []
for i in range(n):
    x= list(map(int, input().split()))
    l.append(x)
def find(ele, l):
    cc = 0
    ans = []
    for i in l:
        if i==ele:
            ans.append(cc)
        cc+=1
    return ans
c = n-1
for i in l[::-1]:
    if c==n-1:
        m = max(i)
        xxx = i.copy()
        xxx.remove(m)
        m2 = max(xxx)
        if m==m2:
            count = 0
            count2 = 0
            for aa in xxx:
                if aa==m2 and count2==1:
                    ii = count
                    break
                elif aa==m2:
                    count2+=1
                count+=1
            index = [i.index(m), ii]
        else:
            index = [i.index(m), i.index(m2)]
        maxval = [m, m2]
        c-=1
        #print(index, maxval, "m")
        continue
    else:
        m = max(i)
        xxx = i.copy()
        xxx.remove(m)
        m2 = max(xxx)
        count = 0
        count2 = len(maxval)
        #print(maxval)
        found2 =find(m2,i)
        found = find(m,i)
        #print(found, found2, "Found")
        for a in maxval:
            #print(count, count2, i)
            if count==count2:
                break
            if index[count] not in found2 or len(found2)!=1:
                maxval.append(a+m2)
            if index[count] not in found or len(found)!=1:
                maxval[count]+=m
            count+=1
        if m==m2:
            index =[found[0]]*(2*count2)
        else:
            index = [found[0]]*count2+[found2[0]]*count2
        c-=1
        #print(maxval, index, "i")
print(max(maxval))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
action = []
for i in range(n):
    action.append(list(map(int,input().split())))

memo = []
for i in range(n):
    memo.append([-1]*3)

def dp(i, a):
    if i == 0:
        return action[0][a]
    else:
        memo[i][a] = max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]
        return memo[i][a]

print(max([dp(n-1,a) for a in range(3)]))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

n = int(input())
action = []
for i in range(n):
    action.append(list(map(int,input().split())))

@lru_cache(maxsize=300000)
def dp(i, a):
    if i == 0:
        return action[0][a]
    else:
        return max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]

import sys
sys.setrecursionlimit(1000000)
print(max([dp(n-1,a) for a in range(3)]))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

n = int(input())
action = []
for i in range(n):
    action.append(list(map(int,input().split())))

@lru_cache(maxsize=1000000)
def dp(i, a):
    if i == 0:
        return action[0][a]
    else:
        return max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]

import sys
sys.setrecursionlimit(1000000)
print(max([dp(n-1,a) for a in range(3)]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
 
li = [list(map(int,input().split())) for i in range(N)]
 
from sys import setrecursionlimit
setrecursionlimit(pow(10,6))
from functools import lru_cache
 
 
#i回目にa..0,b..1,c..2 を選んだ時の最大幸福値
@lru_cache(None)
def func(i,num):
    s = num%3
    if i==0:
        return max(li[0][(s+1)%3],li[0][(s+2)%3])
    return max(func(i-1,(s+1)%3),func(i-1,(s+2)%3)) + li[i][num]
 
print(max( func(N-1,0), func(N-1,1), func(N-1,2) ))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

li = [list(map(int,input().split())) for i in range(N)]

from sys import setrecursionlimit
setrecursionlimit(pow(10,6))
from functools import lru_cache


#i回目にa..0,b..1,c..2 を選んだ時の最大幸福値
@lru_cache(None)
def func(i,num):
    s = num%3
    if i==0:
        return max(li[0][(s+1)%3],li[0][(s+2)%3])
    if num==0:
        return max(func(i-1,1),func(i-1,2)) + li[i][num]
    if num==1:
        return max(func(i-1,2),func(i-1,0)) + li[i][num]
    if num==2:
        return max(func(i-1,0),func(i-1,1)) + li[i][num]

print(max( func(N-1,0), func(N-1,1), func(N-1,2) ))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

li = [list(map(int,input().split())) for i in range(N)]

from sys import setrecursionlimit
setrecursionlimit(pow(10,6))
from functools import lru_cache


#i回目にa..0,b..1,c..2 を選んだ時の最大幸福値
@lru_cache(None)
def func(i,num):
    s = num%3
    if i==0:
        return max(li[0][(s+1)%3],li[0][(s+2)%3])
    return max(func(i-1,(s+1)%3),func(i-1,(s+2)%3)) + li[i][num]

print(max( func(N-1,0), func(N-1,1), func(N-1,2) ))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

N = int(input())
V = np.array([[int(i) for i in input().split()] for j in range(N)])

dp = np.zeros((N, 3), int)
dp[0] = V[0]
for i in range(1, N):
    dp[i,0] = max(dp[i-1,np.array([1,2])]+V[i,0])
    dp[i,1] = max(dp[i-1,np.array([0,2])]+V[i,1])
    dp[i,2] = max(dp[i-1,np.array([0,1])]+V[i,2])

print(dp[N-1].max())

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    abc=np.array([list(map(int,readline().split())) for _ in range(n)],dtype=np.int64)

    x=np.array([1,2])
    y=np.array([2,0])
    z=np.array([0,1])

    dp=np.zeros((n+1,3),dtype=np.int64)
    for i in range(n):
        dp[i+1,x]=np.maximum(dp[i+1,x],dp[i][0]+abc[i,x])
        dp[i+1,y]=np.maximum(dp[i+1,y],dp[i][1]+abc[i,y])
        dp[i+1,z]=np.maximum(dp[i+1,z],dp[i][2]+abc[i,z])

    print(dp[-1].max())

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    abc=np.array([list(map(int,readline().split())) for _ in range(n)],dtype=np.int64)

    x=np.array([1,2])
    y=np.array([2,0])
    z=np.array([0,1])

    dp=np.zeros((n+1,3),dtype=np.int64)
    for i in range(1,n+1):
        dp[i]=[(dp[i-1,x]+abc[i-1,x]).max(),(dp[i-1,y]+abc[i-1,y]).max(),(dp[i-1,z]+abc[i-1,z]).max()]

    print(dp[n].max())

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
 
 
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
 
 
def get_ints(): return map(int, sys.stdin.readline().strip().split())
 
 
def input(): return sys.stdin.readline().strip()
 
 
def maxim(i, char):
    if i < 0:
        return 0
 
    if li[i][char] != -1:
        ##print('hi')
        ##print(i,char)
        return li[i][char]
    if char == 2:
        li[i][2] = max(c[i] + maxim(i - 1, 1), c[i] + maxim(i - 1, 0))
        return li[i][2]
    if char == 1:
        li[i][1] = max(b[i] + maxim(i - 1, 0), b[i] + maxim(i - 1, 2))
        return li[i][1]
    if char == 0:
        li[i][0] = max(a[i] + maxim(i - 1, 1), a[i] + maxim(i - 1, 2))
        return li[i][0]
    if char == 3:
        li[i][3] = (max(maxim(i - 1, 2), maxim(i - 1, 1), maxim(i - 1, 0)))
        return li[i][3]
 
 
n = int(input())
a, b, c = [], [], []
for _ in range(n):
    x, y, z = get_ints()
    li = [[-1 for i in range(4)] for j in range(n+1)]
    a.append(x)
    b.append(y)
    c.append(z)
li = [[-1 for i in range(4)] for j in range(n+1)]
print(maxim(n , 3))

Submission status: Time Limit Exceeded

Solution code:
import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    li=[[-1 for i in range(3)]for j in range(n)]
    a.append(x)
    b.append(y)
    c.append(z)
li[0][0],li[0][1],li[0][2]=a[0],b[0],c[0]
for i in range(1,n):


        li[i][0] = max(a[i] + li[i-1][1] ,a[i] + li[i - 1][2])

        li[i][1] = max(b[i] + li[i - 1][0], b[i] +li[i - 1][2])

        li[i][2] = max(c[i] + li[i - 1][1], c[i] + li[i - 1][0])
print(max(li[n-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    li=[[-1 for i in range(4)]for j in range(n)]
    a.append(x)
    b.append(y)
    c.append(z)
for i in range(n):
   for j in range(4):
        if i==0:
            if j==0:
                li[i][j]=a[i]
            if j==1:
                li[i][j]=b[i]
            if j==2:
                li[i][j]=c[i]
            if j==3:
                li[i][j] = 0
            continue
        if j==0:
            li[i][j] = max(a[i] + li[i-1][1] ,a[i] + li[i - 1][2])
        if j==1:
            li[i][j] = max(b[i] + li[i - 1][0], b[i] +li[i - 1][2])
        if j==2:
            li[i][j] = max(c[i] + li[i - 1][1], c[i] + li[i - 1][0])
        if j==3:
            li[i][3] = (max(li[i - 1][2],li[i - 1][1], li[i - 1][0]))
print(max(li[n-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys


def get_array(): return list(map(int, sys.stdin.readline().strip().split()))


def get_ints(): return map(int, sys.stdin.readline().strip().split())


def input(): return sys.stdin.readline().strip()


def maxim(i, char):
    if i < 0:
        return 0

    if li[i][char] != -1:
        ##print('hi')
        ##print(i,char)
        return li[i][char]
    if char == 2:
        li[i][2] = max(c[i] + maxim(i - 1, 1), c[i] + maxim(i - 1, 0))
        return li[i][2]
    if char == 1:
        li[i][1] = max(b[i] + maxim(i - 1, 0), b[i] + maxim(i - 1, 2))
        return li[i][1]
    if char == 0:
        li[i][0] = max(a[i] + maxim(i - 1, 1), a[i] + maxim(i - 1, 2))
        return li[i][0]
    if char == 3:
        li[i][3] = (max(maxim(i - 1, 2), maxim(i - 1, 1), maxim(i - 1, 0)))
        return li[i][3]


n = int(input())
a, b, c = [], [], []
for _ in range(n):
    x, y, z = get_ints()
    li = [[-1 for i in range(4)] for j in range(n+1)]
    a.append(x)
    b.append(y)
    c.append(z)
print(maxim(n , 3))

Submission status: Time Limit Exceeded

Solution code:
import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

def maxim(i,char):
    if i<0:
        return 0

    if li[i][char]!=-1:
            ##print('hi')
            ##print(i,char)
            return li[i][char]
    if char==2:
        li[i][2]= max(c[i]+maxim(i-1,1),c[i]+maxim(i-1,0))
        return li[i][2]
    if char==1:
        li[i][1]= max(b[i] + maxim(i - 1, 0), b[i] + maxim(i - 1, 2))
        return li[i][1]
    if char==0:
        li[i][0]= max(a[i] + maxim(i - 1, 1), a[i] + maxim(i - 1, 2))
        return li[i][0]
    if char==3:
        li[i][3]= (max(maxim(n - 1, 2), maxim(n - 1, 1), maxim(n - 1, 0)))
        return li[i][3]
n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    li=[[-1 for i in range(4)]for j in range(n)]
    a.append(x)
    b.append(y)
    c.append(z)
print(maxim(n-1,3))

Submission status: Time Limit Exceeded

Solution code:
import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

def maxim(i,char):
    if i<0:
        return 0
    if i!=n:
        if d[i,char]!=-1:
            ##print('hi')
            ##print(i,char)
            return d[i,char]
    if char=='C':
        d[i,char]= max(c[i]+maxim(i-1,'B'),c[i]+maxim(i-1,'A'))
        return d[i,char]
    if char=='B':
        d[i,char]= max(b[i] + maxim(i - 1, 'A'), b[i] + maxim(i - 1, 'C'))
        return d[i,char]
    if char=='A':
        d[i,char]= max(a[i] + maxim(i - 1, 'B'), a[i] + maxim(i - 1, 'C'))
        return d[i,char]
    return (max(maxim(n - 1, 'C'), maxim(n - 1, 'B'), maxim(n - 1, 'A')))
n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    d=dict()
    for i in range(n):
        d[i,'A']=-1
        d[i,'B']=-1
        d[i,'C']=-1
    a.append(x)
    b.append(y)
    c.append(z)

print(maxim(n,'D'))

Submission status: Time Limit Exceeded

Solution code:
import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

def maxim(i,char):
    if i<0:
        return 0
    if d[i,char]!=-1:
        ##print('hi')
        ##print(i,char)
        return d[i,char]
    if char=='C':
        d[i,char]= max(c[i]+maxim(i-1,'B'),c[i]+maxim(i-1,'A'))
        return d[i,char]
    if char=='B':
        d[i,char]= max(b[i] + maxim(i - 1, 'A'), b[i] + maxim(i - 1, 'C'))
        return d[i,char]
    if char=='A':
        d[i,char]= max(a[i] + maxim(i - 1, 'B'), a[i] + maxim(i - 1, 'C'))
        return d[i,char]
n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    d=dict()
    for i in range(n):
        d[i,'A']=-1
        d[i,'B']=-1
        d[i,'C']=-1
    a.append(x)
    b.append(y)
    c.append(z)
ans1=maxim(n-1,'C')
ans2=maxim(n-1,'B')
ans3=maxim(n-1,'A')
print(max(ans1,ans2,ans3))

Submission status: Time Limit Exceeded

Solution code:
import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

def maxim(i,char):
    if i<0:
        return 0
    if d[i,char]!=-1:
        ##print('hi')
        ##print(i,char)
        return d[i,char]
    if char=='C':
        d[i,char]= max(c[i]+maxim(i-1,'B'),c[i]+maxim(i-1,'A'))
        return d[i,char]
    if char=='B':
        d[i,char]= max(b[i] + maxim(i - 1, 'A'), b[i] + maxim(i - 1, 'C'))
        return d[i,char]
    if char=='A':
        d[i,char]= max(a[i] + maxim(i - 1, 'B'), a[i] + maxim(i - 1, 'C'))
        return d[i,char]
n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    d=dict()
    for i in range(n):
        d[i,'A']=-1
        d[i,'B']=-1
        d[i,'C']=-1
    a.append(x)
    b.append(y)
    c.append(z)
print(max(maxim(n-1,'C'),maxim(n-1,'B'),maxim(n-1,'A')))

Submission status: Time Limit Exceeded

Solution code:
def maxim(i,char):
    if i<0:
        return 0
    if d[i,char]!=-1:
        return d[i,char]
    if char=='C':
        d[i,char]= max(c[i]+maxim(i-1,'B'),c[i]+maxim(i-1,'A'))
        return d[i,char]
    if char=='B':
        d[i,char]= max(b[i] + maxim(i - 1, 'A'), b[i] + maxim(i - 1, 'C'))
        return d[i,char]
    if char=='A':
        d[i,char]= max(a[i] + maxim(i - 1, 'B'), a[i] + maxim(i - 1, 'C'))
        return d[i,char]
n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=map(int,input().split())
    d=dict()
    for i in range(n):
        d[i,'A']=-1
        d[i,'B']=-1
        d[i,'C']=-1


    a.append(x)
    b.append(y)
    c.append(z)
print(max(maxim(n-1,'C'),maxim(n-1,'B'),maxim(n-1,'A')))

Submission status: Time Limit Exceeded

Solution code:
import sys,io
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n=read()
a,b,c=[0]*n,[0]*n,[0]*n
for i,line in enumerate(readlines()):
    a[i],b[i],c[i]=mp(line)
dp=[]
@lru_cache(None)
def dp(k,choice):
    if k==0:
        return 0
    one=dp(k-1,1)+a[k-1]
    two=dp(k-1,2)+b[k-1]
    zero=dp(k-1,0)+c[k-1]
    if choice==0:
        return one if one >= two else two
    if choice==1:
        return zero if zero >= two else two
    if choice==2:
        return one if one >= zero else zero
print(max(dp(n,0),dp(n,1),dp(n,2)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
base = np.zeros((1,3))
for _ in range(N):
  base = np.vstack([base, np.array(list(map(int, input().split()))).reshape(1,-1) ])

base = base[1:]

DP_list = [[0,0,0] for _ in range(N)]
pre_check = -1

i = 0
DP_list[i][0] = base[i][0]
DP_list[i][1] = base[i][1]
DP_list[i][2] = base[i][2]


for i in range(1,N):
  DP_list[i][0] = base[i][0] + max(DP_list[i-1][1], DP_list[i-1][2])
  DP_list[i][1] = base[i][1] + max(DP_list[i-1][0], DP_list[i-1][2])
  DP_list[i][2] = base[i][2] + max(DP_list[i-1][1], DP_list[i-1][0])

print(int(max(DP_list[-1])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
base = np.zeros((1,3))
for _ in range(N):
  base = np.vstack([base, np.array(list(map(int, input().split()))).reshape(1,-1) ])

base = base[1:]

DP_list = [0 for _ in range(N)]
pre_check = -1

for i in range(0,N):
  for j in [0,1,2]:
    if j != pre_check:
      PRE = DP_list[i-1] if i>0 else 0
      if PRE + base[i, j] > DP_list[i]:
        DP_list[i] = PRE + base[i, j]
        pre_check_cnt = j
  pre_check = pre_check_cnt

print(int(DP_list[-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())

values = np.array([list(map(int, input().split(' '))) for _ in range(N)])
dp = np.zeros(shape=(N, 3), dtype=int)

dp[0] = values[0]

for i in range(1, N):
    dp[i][0] = np.max(values[i][0] + dp[i - 1][1:3])
    dp[i][1] = np.max(values[i][1] + dp[i - 1][0::2])
    dp[i][2] = np.max(values[i][2] + dp[i - 1][:2])

print(np.max(dp[N - 1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
H = np.array([list(map(int, input().split())) for _ in range(n)], dtype = np.int)
dp = np.zeros((n, 3), dtype = np.int)
dp[0] = H[0]
def except_ind(num):
    ind = np.ones((3, ), dtype = bool)
    ind[num] = False
    return ind
for i in range(1, n):
    for j in range(3):
        dp[i][j] = np.max(dp[i - 1][except_ind(j)]) + H[i][j]
print(np.max(dp[n - 1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


N = int(input())
abc = []
for n in range(N):
    abc.append(list(map(int, input().split())))

# initialize
dp = np.zeros((N+1, 3))

# dp    
for i in range(N+1):
    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            try:
                dp[i+1][k] = max(dp[i+1][k], dp[i][j] + abc[i][k])
            except:
                pass

print(int(max(dp[-1])))