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.

Solution (Python):
import math
from math import sqrt
import sys
from collections import deque, defaultdict
from heapq import heappop,heappush
from copy import deepcopy

INF=10**18
MOD=10**9+7
MAX=10**5+7



def main():
  N=int(input())
  dp=[[0]*3 for i in range(MAX)]
  
  for i in range(N):
    a,b,c=map(int, input().split())
    dp[i+1][0]=max([dp[i+1][0], dp[i][1]+a, dp[i][2]+a])
    dp[i+1][1]=max([dp[i+1][1], dp[i][2]+b, dp[i][0]+b])
    dp[i+1][2]=max([dp[i+1][2], dp[i][0]+c, dp[i][1]+c])
  print(max(dp[N]))

if __name__=='__main__':
  main()

Solution (Python):
N=int(input())
a=[]
b=[]
c=[]

for _ in range(N):
    A,B,C=map(int,input().split())
    a.append(A)
    b.append(B)
    c.append(C)

dp=[[a[0],b[0],c[0]]]

for i in range(1,N):
    DA=a[i]+max(dp[i-1][1:])
    DB=b[i]+max(dp[i-1][0::2])
    DC=c[i]+max(dp[i-1][0:2])
    dp.append([DA,DB,DC])
print(max(dp[-1]))

Solution (Python):
n = int(input())
abc = []
for i in range(n):
    abc.append(list(map(int, input().split())))
h = [[0 for i in range(3)] for i in range(n)]
h[0] = abc[0]
for i in range(1, n):
    h[i][0] = max(h[i-1][1]+abc[i][0],h[i-1][2]+abc[i][0])
    h[i][1] = max(h[i-1][2]+abc[i][1],h[i-1][0]+abc[i][1])
    h[i][2] = max(h[i-1][0]+abc[i][2],h[i-1][1]+abc[i][2])
print(max(h[n-1]))

Solution (Python):
N = int(input())
ac = [list(map(int, input().split())) for _ in range(N)]




se = [[1, 2], [0, 2], [0, 1]]


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

for i in range(N):
  for j in range(3):
    dp[i + 1][j] = max(dp[i][se[j][0]] + ac[i][j], dp[i][se[j][1]] + ac[i][j])

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

Solution (Python):
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(1, N+1):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i][j] = max(dp[i][j], dp[i-1][k] + abc[i-1][k])

print(max(dp[N]))

Solution (Python):
n = int(input())
a,b,c = [0] * n, [0] * n, [0] * n

for i in range(n):
	a[i], b[i], c[i] = map(int, input().split())
dp = [[0] * 3 for _ in range(n)]
dp[0] = [a[0], b[0], c[0]]
for i in range(n - 1):
	dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + a[i + 1], dp[i][2] + a[i + 1])
	dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + b[i + 1], dp[i][2] + b[i + 1])
	dp[i + 1][2] = max(dp[i + 1][2], dp[i][0] + c[i + 1], dp[i][1] + c[i + 1])
print(max(dp[-1]))

Solution (Python):
n = int(input())
activities = [list(map(int, input().split())) for _ in range(n)]

pre_a = 0
pre_b = 0
pre_c = 0
res = 0
for a, b, c in activities:
    tmp_a = max(pre_b, pre_c) + a
    tmp_b = max(pre_a, pre_c) + b
    tmp_c = max(pre_b, pre_a) + c
    pre_a = tmp_a
    pre_b = tmp_b
    pre_c = tmp_c
print(max(pre_a, pre_b, pre_c))

Solution (Python):
n = int(input())
a, b, c = [[0] * n for i in range(3)]
for i in range(n):
  a[i], b[i], c[i] = map(int, input().split())

dp = [[0, 0, 0] for i in range(n)]

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

for i in range(1, n):
  dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i]
  dp[i][1] = max(dp[i-1][2], dp[i-1][0]) + b[i]
  dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i]

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

Solution (Python):
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)

dp = [[0] * 3 for _ in range(n+1)]

for i in range(n):
    dp[i+1][0] = max(dp[i+1][0], max(dp[i][1], dp[i][2])+A[i])
    dp[i+1][1] = max(dp[i+1][1], max(dp[i][0], dp[i][2])+B[i])
    dp[i+1][2] = max(dp[i+1][2], max(dp[i][1], dp[i][0])+C[i])
print(max(dp[n]))

Solution (Python):
n=int(input())
li=[list(map(int,input().split())) for i in range(n)]



dp = [[0 for j in range(3)] for i in range(n)]


dp[0][0] = li[0][0]
dp[0][1] = li[0][1]
dp[0][2] = li[0][2]


for i in range(1, n):
    dp[i][0] = max(dp[i-1][1]+li[i][0], dp[i-1][2]+li[i][0])
    dp[i][1] = max(dp[i-1][2]+li[i][1], dp[i-1][0]+li[i][1])
    dp[i][2] = max(dp[i-1][0]+li[i][2], dp[i-1][1]+li[i][2])


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

Solution (Python):
import numpy as np

N = int(input())
A,B,C = 0,0,0
for i in range(N):
  a,b,c = map(int,input().split())
  A,B,C = a+max(B,C),b+max(A,C),c+max(A,B)
print(max(A,B,C))

Solution (Python):
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]

dp = [[0 for i in range(3)] for i in range(n)]

dp[0] = l[0]

for i in range(1,n):
    dp[i][0] = max(dp[i-1][1]+l[i][0], dp[i-1][2]+l[i][0])
    dp[i][1] = max(dp[i-1][0]+l[i][1], dp[i-1][2]+l[i][1])
    dp[i][2] = max(dp[i-1][0]+l[i][2], dp[i-1][1]+l[i][2])

print(max(dp[-1]))

Solution (Python):
n = int(input())

abc=list()
for i in range(n):
    abc.append([int(e) for e in input().split()])

A=[]
B=[]
C=[]

A.append(abc[0][0])
B.append(abc[0][1])
C.append(abc[0][2])

for i in range(1,n):
    a = abc[i][0] + max(B[-1],C[-1])
    b = abc[i][1] + max(A[-1],C[-1])
    c = abc[i][2] + max(A[-1],B[-1])
    A.append(a)
    B.append(b)
    C.append(c)

print(max(A[-1],B[-1],C[-1]))

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007



def main():
	n = int(input())
	pp=[0]*3
	np=[0]*3
	for i in range(n):
		a,b,c=IN()
		np[0] = max(pp[1],pp[2])+a
		np[1] = max(pp[0],pp[2])+b
		np[2] = max(pp[0],pp[1])+c
		pp=np[:]
	
	
	print(max(pp))
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
N = int(input())
A_B_C = []
for i in range(N):
    A_B_C.append(tuple(map(int, input().split())))

DP = [[0]*3 for i in range(N)]

DP[0][0] = A_B_C[0][0]
DP[0][1] = A_B_C[0][1]
DP[0][2] = A_B_C[0][2]
for i in range(1, N):
    for j in range(3):
        j_a = (j + 1) % 3
        j_b = (j + 2) % 3
        DP[i][j] = max(DP[i-1][j_a], DP[i-1][j_b]) + A_B_C[i][j]

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

Solution (Python):
n=int(input())
ar=[]
for i in range (n):
	temp=list(map(int,input().split()))
	ar.append(temp)
for i in range (1,n):
	ar[i][0]=ar[i][0]+max(ar[i-1][1],ar[i-1][2])
	ar[i][1]=ar[i][1]+max(ar[i-1][0],ar[i-1][2])
	ar[i][2]=ar[i][2]+max(ar[i-1][0],ar[i-1][1])
print(max(ar[-1]))

Solution (Python):
N=int(input())
abc_list=[]
for i in range(N) :
  k=input().split()
  abc_list.append([int(i) for i in k])
n_list=  [[0 for i in range(3)] for j in range(N)]

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

print(max(n_list[-1]))

Solution (Python):
n = int(input())
efforts = [list(map(int, input().split())) for _ in range(n)]

dp = [[float('inf')] * 3] * n

dp[0][0] = efforts[0][0]
dp[0][1] = efforts[0][1]
dp[0][2] = efforts[0][2]

for i in range(1, n):
    eab = dp[i-1][0] + efforts[i][1]
    eac = dp[i-1][0] + efforts[i][2]
    eba = dp[i-1][1] + efforts[i][0]
    ebc = dp[i-1][1] + efforts[i][2]
    eca = dp[i-1][2] + efforts[i][0]
    ecb = dp[i-1][2] + efforts[i][1]

    dp[i][0] = max(eba, eca)
    dp[i][1] = max(eab, ecb)
    dp[i][2] = max(eac, ebc)

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

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
dp = [[0,0,0] for _ in range(N+1)]
for i in range(1,N+1):
    a,b,c = LI()
    dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + a
    dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + b
    dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + c
print(max(dp[-1]))

Solution (Python):
import numpy as np









N = int(input().strip())
h = []
for i in range(N):
    h.append(list(map(int, input().strip().split())))
H = np.array(h)


dp = np.zeros(N * 3, dtype=np.int).reshape(N, 3)

dp[0][0] = H[0][0]
dp[0][1] = H[0][1]
dp[0][2] = H[0][2]

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

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

Solution (Python):












n=int(input())
abc=[]
for i in range(n):
    abc.append(list(map(int,input().split())))
dp=[[-1,-1,-1] for i in range(n)]


for i in range(n):
    if i==0:
        for j in range(3):
            dp[i][j]=abc[i][j]
    else:
        dp[i][0]=max(dp[i-1][1]+abc[i][0],dp[i-1][2]+abc[i][0])
        dp[i][1]=max(dp[i-1][2]+abc[i][1],dp[i-1][0]+abc[i][1])
        dp[i][2]=max(dp[i-1][0]+abc[i][2],dp[i-1][1]+abc[i][2])
print(max(dp[n-1]))

Solution (Python):
N= int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
dp = [ list([0,0,0]) for i in range(N)]
for i,l in enumerate(arr):
  if i == 0:
    dp[0] = l
    continue
  dp[i] = [max(dp[i-1][1:])+l[0], max(dp[i-1][0],dp[i-1][2])+l[1],max(dp[i-1][:2])+l[2]]
print(max(dp[-1]))

Solution (Python):
N = int(input())
matrix = []
for i in range(N):
    matrix.append([int(i) for i in input().split()])
ans = -float("inf")
dp = [[0 for i in range(4)] for j in range(len(matrix)+1)]
for i in range(len(matrix)-1,-1,-1):
    for j in range(len(matrix[0])-1,-1,-1):
        dp[i][j] = -float("inf")
        for k in range(3):
            if j != k:
                dp[i][j] = max(dp[i][j],dp[i+1][k]+matrix[i][j])
        ans = max(ans,dp[i][j])
print(ans)

Solution (Python):
N=int(input())
ABC=[list(map(int,input().split())) for i in range(N)]
dp=[0]*3
for a,b,c in ABC:
    dp=[max(dp[1:])+a,max(dp[0],dp[2])+b,max(dp[:2])+c]
print(max(dp))

Solution (Python):

"""
Created on Sat May  2 20:35:42 2020

@author: Kanaru Sato
"""

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

dp = []
for i in range(n):
    dp.append([-1,-1,-1])

for i in range(n):
    if i == 0:
        for j in range(3):
            dp[0][j] = abc[0][j]
    else:
        dp[i][0] = max(dp[i-1][1],dp[i-1][2])+abc[i][0]
        dp[i][1] = max(dp[i-1][2],dp[i-1][0])+abc[i][1]
        dp[i][2] = max(dp[i-1][0],dp[i-1][1])+abc[i][2]

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

Solution (Python):
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*3 for i in range(n+1)]
for i in range(n):
    dp[i+1][0]=l[i][0]+max(dp[i][1],dp[i][2])
    dp[i + 1][1] = l[i][1] + max(dp[i][0], dp[i][2])
    dp[i + 1][2] = l[i][2] + max(dp[i][1], dp[i][0])
print(max(dp[n]))

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

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


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

print(max(dp[-1]))

Solution (Python):
n = int(input())
happy = [tuple(map(int, input().split())) for _ in range(n)]

dp = [[0] * 3 for _ in range(n + 1)]


for i in range(n):
    dp[i + 1][0] = max(dp[i][1], dp[i][2]) + happy[i][0]
    dp[i + 1][1] = max(dp[i][2], dp[i][0]) + happy[i][1]
    dp[i + 1][2] = max(dp[i][0], dp[i][1]) + happy[i][2]

ans = max(dp[n])
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]
a, b, c = 0, 1, 2

dp = [[0, 0, 0] for _ in range(n)]
dp[0] = abc[0][:]
for i in range(1, n):
    dp[i][a] = max(dp[i-1][b], dp[i-1][c]) + abc[i][a]
    dp[i][b] = max(dp[i-1][a], dp[i-1][c]) + abc[i][b]
    dp[i][c] = max(dp[i-1][b], dp[i-1][a]) + abc[i][c]

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

Solution (Python):
def main():
    n = int(input())
    abc = []
    for _ in range(n):
        abc.append(tuple(map(int, input().split())))
    dp = [[0,0,0] for _ in range(n)]
    dp[0][0] = abc[0][0]
    dp[0][1] = abc[0][1]
    dp[0][2] = abc[0][2]

    for i in range(1, n):
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + abc[i][0]
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + abc[i][1]
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + abc[i][2]
    print(max(dp[n-1]))

if __name__ == '__main__':
    main()

Solution (Python):

n=int(input())
abc=[]
for i in range(0,n):
    temp=list(map(int,input().split()))
    abc.append(temp)  
dp=[["

dp[0][0]= abc[0][0]
dp[0][1]= abc[0][1]
dp[0][2]= abc[0][2]

for i in range(1,n):
    dp[i][0]= max( dp[i-1][1], dp[i-1][2] )+ abc[i][0]
    dp[i][1]= max( dp[i-1][0], dp[i-1][2] )+ abc[i][1]
    dp[i][2]= max( dp[i-1][0], dp[i-1][1] )+ abc[i][2]

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

Solution (Python):
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)

dp = [[0] * 3 for _ in range(n)]
dp[0] = [A[0], B[0], C[0]]

for i in range(n - 1):
	dp[i + 1][0] = max(dp[i][1] + A[i + 1], dp[i][2] + A[i + 1])
	dp[i + 1][1] = max(dp[i][2] + B[i + 1], dp[i][0] + B[i + 1])
	dp[i + 1][2] = max(dp[i][0] + C[i + 1], dp[i][1] + C[i + 1])

print(max(dp[-1]))

Solution (Python):
n=int(input())
l=[[0]]*n
for i in range(n):
  v=list(map(int,input().split()))
  l[i]=v
dp=l[0]
for m in l[1:]:
  a=max(m[0]+dp[1],m[0]+dp[2])
  b=max(m[1]+dp[0],m[1]+dp[2])
  c=max(m[2]+dp[1],m[2]+dp[0])
  dp=[a,b,c]
print(max(dp))

Solution (Python):
n = int(input())
acts = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * 3 for _ in range(n)]
a, b, c = acts[0]
dp[0] = [a, b, c]
for i in range(1, n):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i][j] = max(dp[i][j], dp[i - 1][k] + acts[i][j])
print(max(dp[-1]))

Solution (Python):
n=int(input())
l=[[0]]*n
for i in range(n):
  v=list(map(int,input().split()))
  l[i]=v
dp=l[0]
for m in l[1:]:
  a=max(m[0]+dp[1],m[0]+dp[2])
  b=max(m[1]+dp[0],m[1]+dp[2])
  c=max(m[2]+dp[1],m[2]+dp[0])
  dp=[a,b,c]
print(max(dp))

Solution (Python):

import sys


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    dp = [[float("-inf")] * 3 for _ in range(N)]
    dp[0][0] = a[0]
    dp[0][1] = b[0]
    dp[0][2] = c[0]
    for i in range(1, N):
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i]
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i]
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i]
    print(max(dp[-1]))



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N)  
    b = [int()] * (N)  
    c = [int()] * (N)  
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, a, b, c)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
a = []
b = [[0]*3 for k in range(N+1)]

for j in range(N):
    a.append(list(map(int,input().split())))

b[0][0] = 0
b[0][1] = 0
b[0][2] = 0


for i in range(N):
    b[i+1][0] = max(b[i][1]+a[i][0],b[i][2]+a[i][0])
    b[i+1][1] = max(b[i][0]+a[i][1],b[i][2]+a[i][1])
    b[i+1][2] = max(b[i][0]+a[i][2],b[i][1]+a[i][2])

print(max(b[N]))

Solution (Python):

import sys
from collections import Counter
from itertools import permutations, combinations
from fractions import gcd

from math import ceil, floor
import bisect
sys.setrecursionlimit(10 ** 6)
inf = float("inf")

def input():
    return sys.stdin.readline()[:-1]

def chmin(a, b):
    if a > b:
        return b
    else:
        return a

def chmax(a, b):
    if a < b:
        return b
    else:
        return a

def main():
    n = int(input())
    abc = [None] * n
    for i in range(n):
        abc[i] = tuple(map(int, input().split()))

    dp = [[0] * 3 for _ in range(n+1)]
    for i in range(n):
        for j in range(3):
            for k in range(3):
                if j != k:
                    dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + abc[i][k])
    
    ans = 0
    for j in range(3):
        ans = chmax(ans, dp[n][j])
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def c():
    n = int(input())
    arr = []
    for _ in range(n):
        line = list(map(int, input().split() ))
        arr.append(line)
    
    dp = [[0 for _ in range(3)] for _ in range(n)]

    for i in range(n):
        for j in range(3):
            if i == 0:
                dp [i][j] = arr[i][j]
            else:
                dp[i][j] = arr[i][j] + max([x for ii, x in enumerate(dp[i-1]) if ii != j])

    return max(dp[-1])


print(c())

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

dp =[[0,0,0] for i in range(N)]

for i in range(3):
    dp[0][i] = li[0][i]

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

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

Solution (Python):


n = int(input())
l = []

for i in range(n):
    l.append(list(map(int, input().split())))


dp = []
for i in range(n + 1):
    dp.append([-1, -1, -1])

dp[1][0] = l[0][0]
dp[1][1] = l[0][1]
dp[1][2] = l[0][2]

for i in range(2, n + 1):
    dp[i][0] = l[i - 1][0] + max(dp[i - 1][1], dp[i - 1][2])
    dp[i][1] = l[i - 1][1] + max(dp[i - 1][0], dp[i - 1][2])
    dp[i][2] = l[i - 1][2] + max(dp[i - 1][0], dp[i - 1][1])

print(max(dp[n][0], max(dp[n][1], dp[n][2])))

Solution (Python):
n = int(input())
u = [[0,0,0]]
for i in range(n):
    u.append(list(map(int,input().split())))

dp = [[0,0,0],u[1]]
for i in range(2,n+1):
    dp.append([0,0,0])
for i in range(2,n+1):
    dp[i][0]=max(dp[i-1][1]+u[i][0],dp[i-1][2]+u[i][0])
    dp[i][1]=max(dp[i-1][2]+u[i][1],dp[i-1][0]+u[i][1])
    dp[i][2]=max(dp[i-1][0]+u[i][2],dp[i-1][1]+u[i][2])

print(max(dp[n]))

Solution (Python):
n=int(input())
happy=[[] for i in range(n)]
for i in range(n):
  happy[i]=list(map(int,input().split()))
dp=[[0,0,0] for i in range(n)]
dp[0]=[happy[0][0],happy[0][1],happy[0][2]]
for i in range(1,n):
  
  for j in range(3):
    x=[]
    for k in range(3):
      if k!=j:
        x.append(dp[i-1][k])
    dp[i][j]=max(x)+happy[i][j]
    
print(max(dp[n-1]))

Solution (Python):
N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
dp = [[0] * 3 for i in range(N)]

dp[0][0]=abc[0][0]
dp[0][1]=abc[0][1]
dp[0][2]=abc[0][2]
for i in range(1,N):
  dp[i][0]=abc[i][0]+max(dp[i-1][1],dp[i-1][2])
  dp[i][1]=abc[i][1]+max(dp[i-1][0],dp[i-1][2])
  dp[i][2]=abc[i][2]+max(dp[i-1][0],dp[i-1][1])
print(max(dp[-1]))

Solution (Python):
n = int(input())

dp = [[0 for _ in range(3)] for _ in range(n)]

a, b, c = map(int, input().split())
dp[0][0] = a
dp[0][1] = b
dp[0][2] = c

for i in range(1, n):
    abc = [int(x) for x in input().split()]
    
    for j in range(len(abc)):
        dp[i][j] = max(dp[i - 1][(j + 1) % 3] + abc[j], dp[i - 1][(j + 2) % 3] + abc[j])

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

Solution (Python):
n = int(input())
dp = [[-float("inf") for x in range(3)] for x in range(n)]
dp[0] = list(map(int,input().split()))
for i in range(1,n):
    a = list(map(int,input().split()))
    for x in range(3):
        for y in range(3):
            if(x == y):
                continue
            if(dp[i-1][x]+a[y]>dp[i][y]):
                dp[i][y] = dp[i-1][x]+a[y]
print(max(dp[-1]))

Solution (Python):
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)] 
happy = [[0, 0, 0] for _ in range(n+1)]
for i in range(n):
    for j in range(3):
        happy[i + 1][j % 3] = abc[i][j % 3] + max(happy[i][(j + 1) % 3], happy[i][(j + 2) % 3])
print(max(happy[-1][i] for i in range(3)))

Solution (Python):
N = int(input())
plans = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (3) for _ in range(N+1)]

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            else:
                dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + plans[i][k])
                
res = 0
for j in range(3):
    res = chmax(res, dp[-1][j])
print(res)

Solution (Python):
N = int(input())

last_a = 0
last_b = 0
last_c = 0

for _ in range(N):
    a, b, c = map(int, input().split())
    last_a, last_b, last_c = a + max(last_b, last_c), b + max(last_c, last_a), c + max(last_a, last_b)

print(max(last_a, last_b, last_c))

Solution (Python):
def resolve():
	n = int(input())
	dp = [[0]*3 for _ in range(n+1)]
	for i in range(1, n+1):
		nums = list(map(int, input().split()))
		for j in range(3):
			for k in range(3):
				if j == k:
					continue
				dp[i][j] = max(dp[i][j], nums[j] + dp[i-1][k])
	print(max(dp[-1]))
resolve()

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

n = inp()
dp = [[0] * 3 for i in range(n+1)]
for i in range(n):
    work = inpl()
    for j in range(3):
        option = [dp[i][k] + work[k] for k in range(3) if j != k]
        dp[i + 1][j] = max(option)
print(max(dp[n]))

Solution (Python):
n = int(input())
lst = [list(map(int, input().split())) for i in range(n)]
ans = [[0]*3 for i in range(n)]
ans[0] = lst[0]
for i in range(1, n):
  ans[i][0] = lst[i][0] + max(ans[i-1][1], ans[i-1][2])
  ans[i][1] = lst[i][1] + max(ans[i-1][0], ans[i-1][2])
  ans[i][2] = lst[i][2] + max(ans[i-1][0], ans[i-1][1])

res = max(ans[n-1][0], max(ans[n-1][1], ans[n-1][2]))
print(res)

Solution (Python):
N = int(input())
a, b, c = [0] * N, [0] * N, [0] * N
for i in range(N):
	a[i], b[i], c[i] = map(int, input().split())
dp = [[0] * 3 for _ in range(N)]
dp[0] = [a[0], b[0], c[0]]
for i in range(N - 1):
	dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + a[i + 1], dp[i][2] + a[i + 1])
	dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + b[i + 1], dp[i][2] + b[i + 1])
	dp[i + 1][2] = max(dp[i + 1][2], dp[i][0] + c[i + 1], dp[i][1] + c[i + 1])
print(max(dp[N - 1]))

Solution (Python):
n=int(input())
satis=[]

for i in range(n):
	satis.extend(map(int,input().split()))

tempA=satis[0]
tempB=satis[1]
tempC=satis[2]
if n > 1:
  for i in range(n-1):
    tempA2=satis[3*i+3]+max([tempB,tempC])
    tempB2=satis[3*i+4]+max([tempA,tempC])
    tempC2=satis[3*i+5]+max([tempA,tempB])
    tempA=tempA2
    tempB=tempB2
    tempC=tempC2
  print(max([tempA,tempB,tempC]))
else:
  print(max([tempA,tempB,tempC]))

Solution (Python):
n=int(input())
satis=[]

for i in range(n):
  A=list(map(int,input().split()))
  satis.extend(A)

tempA=satis[0]
tempB=satis[1]
tempC=satis[2]
if n > 1:
  for i in range(n-1):
    tempA2=satis[3*i+3]+max([tempB,tempC])
    tempB2=satis[3*i+4]+max([tempA,tempC])
    tempC2=satis[3*i+5]+max([tempA,tempB])
    tempA=tempA2
    tempB=tempB2
    tempC=tempC2
  print(max([tempA,tempB,tempC]))
else:
  print(max([tempA,tempB,tempC]))

Solution (Python):

import sys
input = sys.stdin.readline

n = int(input())

count  = [[0] * 3 for i in range(n)]

for i in range(n):
    a, b, c = map(int, input().split())

    if i == 0:
        count[i][0] = a
        count[i][1] = b
        count[i][2] = c

    else:
        count[i][0] = a + max(count[i-1][1],count[i-1][2])
        count[i][1] = b + max(count[i-1][0],count[i-1][2])
        count[i][2] = c + max(count[i-1][0],count[i-1][1])
        

print(max(count[-1][0],count[-1][1],count[-1][2]))

Solution (Python):
n = int(input())
a,b,c = [0]*n, [0]*n, [0]*n
for i in range(n):
    a[i], b[i],c[i] = map(int,input().split())
dp = [[0]*3 for _ in range(n)]
dp[0] = [a[0],b[0],c[0]]
for i in range(n-1):
    dp[i+1][0] = max(dp[i+1][0], dp[i][1]+a[i+1], dp[i][2]+a[i+1])
    dp[i+1][1] = max(dp[i+1][1], dp[i][0]+b[i+1], dp[i][2]+b[i+1])
    dp[i+1][2] = max(dp[i+1][2], dp[i][0]+c[i+1], dp[i][1]+c[i+1])
print(max(dp[n-1]))

Solution (Python):





import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string


BUFSIZE = 8192

BUFSIZE = 8192

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

def main():
    n=int(input())
    nums=[list(map(int,input().split())) for i in range(n)]
    dp=[[0]*3 for i in range(n)]
    dp[0]=nums[0]
    for i in range(1,n):
        for j in range(3):
            if j==0:
                dp[i][j]=max(dp[i-1][j+1],dp[i-1][j+2])+nums[i][j]
            elif j==1:
                dp[i][j]=nums[i][j]+max(dp[i-1][j-1],dp[i-1][j+1])
            elif j==2:
                dp[i][j]=max(dp[i-1][j-1],dp[i-1][j-2])+nums[i][j]
    print (max(dp[n-1]))
if __name__ == "__main__":
    main()

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

Solution (Python):
import sys

sys.setrecursionlimit(200000)

n = int(input())
 
m ={}
def dp(i, a, b, c):
	if (i,a,b,c) in m:
		return m[(i,a,b,c)]
	if i == -1: return 0
	a_v = dp(i-1, a=False, b=True, c=True) + al[i] if a else -1
	b_v = dp(i-1, a=True, b=False, c=True) + bl[i] if b else -1
	c_v = dp(i-1, a=True, b=True, c=False) + cl[i] if c else -1
	m[(i,a,b,c)] = max([a_v, b_v, c_v])
	return max([a_v, b_v, c_v])
 
al = []
bl = []
cl = []
for i in range(n):
	a, b, c = list(map(int, input().split(" ")))
	al.append(a)
	bl.append(b)
	cl.append(c)
    
print(dp(n-1, a=True, b=True, c=True))

Solution (Python):
N = int(input())
x, y, z = 0, 0, 0
for _ in range(N):
    a, b, c = map(int, input().split())
    x, y, z = max(y, z) + a, max(z, x) + b, max(x, y) + c
print(max(x, y, z))

Solution (Python):
N = int(input())
x, y, z = 0, 0, 0
for _ in range(N):
    a, b, c = map(int, input().split())
    x, y, z = max(y, z) + a, max(z, x) + b, max(x, y) + c
print(max(x, y, z))

Solution (Python):



N = int(input())
a=[i for i in range(N)]
b=[i for i in range(N)]
c=[i for i in range(N)]

for i in range(N):
    a[i],b[i],c[i] = list(map(int,input().split()))

dp = [[0,0,0] for i in range(N)]
dp[0] = [a[0],b[0],c[0]]

for i in range(N-1):
    dp[i+1] = [a[i+1] + max(dp[i][1], dp[i][2]), b[i+1] + max(dp[i][0], dp[i][2]), c[i+1] + max(dp[i][1], dp[i][0])]

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

Solution (Python):
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]
dp = []

for i in range(n):
    if i == 0:
        dp.append([abc[0][0], abc[0][1], abc[0][2]])
        continue
    dp.append([max(dp[i-1][1]+abc[i][0], dp[i-1][2]+abc[i][0]), max(dp[i-1][2]+abc[i][1], dp[i-1][0]+abc[i][1]), max(dp[i-1][0]+abc[i][2], dp[i-1][1]+abc[i][2])])

print(max(dp[-1]))

Solution (Python):
N = int(input())
abc = [0]*N
for i in range(N):
    abc[i] = list(map(int,input().split()))
dp = [0]*N
for i in range(N):
    dp[i] = [0,0,0]
dp[0][0],dp[0][1],dp[0][2]= abc[0][0], abc[0][1], abc[0][2]

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

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

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

Solution (Python):
n = int(input())
abc = []
ia, ib, ic = map(int, input().split())
for _ in range(n-1):
    a, b, c = map(int, input().split())
    abc.append((a, b, c))

dp = [ia, ib, ic]

for a, b, c in abc:
    newdp = [None]*3
    newdp[0] = max(dp[1], dp[2]) + a
    newdp[1] = max(dp[2], dp[0]) + b
    newdp[2] = max(dp[0], dp[1]) + c
    dp = newdp

print(max(dp))

Solution (Python):
N=int(input())
ABC=[[0,0,0]]
for i in range(N):
	ABC+=[[int(i) for i in input().split()]]
DP=[[0,0,0] for i in range(N+1)]
for i in range(N):
	for j in range(3):
		DP[i+1][j]=ABC[i+1][j]+max(DP[i][(j+1)%3],DP[i][(j+2)%3])
print(max(DP[N]))

Solution (Python):
N=int(input())
ABC=[]
for i in range(N):
	ABC+=[[int(i) for i in input().split()]]
DP=[[0,0,0] for i in range(N+1)]
for i in range(N):
	for j in range(3):
		DP[i][j]=ABC[i][j]+max(DP[i-1][(j+1)%3],DP[i-1][(j+2)%3])
print(max(DP[N-1]))