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):
def vacation(n, nums):
    dp = [nums[0]]
    for i in range(1, n):
        dp.append([
            nums[i][0] + max(dp[-1][1], dp[-1][2]),
            nums[i][1] + max(dp[-1][0], dp[-1][2]),
            nums[i][2] + max(dp[-1][0], dp[-1][1])
        ])
    return max(dp[-1])


n = int(input())
nums = []
for _ in range(n):
    row = [int(i) for i in input().split()]
    nums.append(row)

ans = vacation(n, nums)
print(ans)

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

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

for i in range(1, n):
    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_list[i][j])
                
print(max(dp[n - 1]))

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

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

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

Solution (Python):
n = int(input())
happiness = []
for _ in range(n):
    a,b,c = map(int,input().split())
    happiness.append((a,b,c,a,b,c))

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 k != j:
                dp[i][j] = max(dp[i][j],dp[i-1][k] + happiness[i-1][j])
print(max(dp[n]))

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

Solution (Python):




N = int(input())

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

for i in range(1, N+1):
    a, b, c = map(int, input().split())
    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[N]))

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

def main():
    n = int(input())
    colA, colB, colC = map(int, input().split())
    for i1 in range(1, n):
        a, b, c = map(int, input().split())
        colA, colB, colC = a + max(colB, colC), b + max(colA, colC), c + max(colA, colB)
    print(max(colA, colB, colC))

if __name__ == '__main__':
    main()

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


dp = [0]*3

for i in range(n):
    prev = dp.copy()
    for j in range(3):
        dp[j] = happymat[i][j] + max(prev[(j+1)%3], prev[(j+2)%3])

print(max(dp))

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


dp[0][0] = happymat[0][0]
dp[0][1] = happymat[0][1]
dp[0][2] = happymat[0][2]

for i in range(1, n):
    for j in range(3):
        dp[i][j] = happymat[i][j] + max(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3])

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

Solution (Python):



import sys
readline = sys.stdin.buffer.readline
geta = lambda fn: map(fn, readline().split())
gete = lambda fn: fn(readline())

def main():
    N = gete(int)
 
    cur, prev = [0]*3, [0]*3
    
    for _ in range(N):
        a, b, c = geta(int)
        prev, cur = cur, prev
        cur[0] = max(prev[1], prev[2]) + a
        cur[1] = max(prev[2], prev[0]) + b
        cur[2] = max(prev[0], prev[1]) + c
    
    
    print(max(cur))

	
if __name__ == "__main__":
	main()

Solution (Python):



import sys
readline = sys.stdin.buffer.readline
geta = lambda fn: list(map(fn, readline().split()))
gete = lambda fn: fn(readline())

def main():
	n=gete(int)
	dp=[[0]*3 for _ in range(n+1)]
	
	
	for i in range(n):
		a,b,c = geta(int)
		dp[i+1][0] = max(dp[i][1], dp[i][2]) + a
		dp[i+1][1] = max(dp[i][2], dp[i][0]) + b
		dp[i+1][2] = max(dp[i][0], dp[i][1]) + c
		
	print(max(dp[n][0],dp[n][1],dp[n][2]))
	
	
	
if __name__ == "__main__":
	main()

Solution (Python):



import sys
readline = sys.stdin.buffer.readline
geta = lambda fn: map(fn, readline().split())
gete = lambda fn: fn(readline())

def main():
	n=gete(int)
	dp=[[0]*3 for _ in range(n+1)]
	
	
	for i in range(n):
		a,b,c = geta(int)
		dp[i+1][0] = max(dp[i][1], dp[i][2]) + a
		dp[i+1][1] = max(dp[i][2], dp[i][0]) + b
		dp[i+1][2] = max(dp[i][0], dp[i][1]) + c
		
	print(max(dp[n][0],dp[n][1],dp[n][2]))
	
	
	
if __name__ == "__main__":
	main()

Solution (Python):



geta = lambda fn: map(fn, input().split())
gete = lambda fn: fn(input())

def main():
	n=gete(int)
	dp=[[0]*3 for _ 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][2], dp[i][0]) + b
		dp[i+1][2] = max(dp[i][0], dp[i][1]) + c
		
	print(max(dp[n][0],dp[n][1],dp[n][2]))
	
	
	
if __name__ == "__main__":
	main()

Solution (Python):



geta = lambda fn: map(fn, input().split())
gete = lambda fn: fn(input())

def main():
	n=gete(int)
	dp=[[0]*3 for _ in range(n+1)]
	
	
	for i in range(n):
		a,b,c = geta(int)
		dp[i+1][0] = max(dp[i][1], dp[i][2]) + a
		dp[i+1][1] = max(dp[i][2], dp[i][0]) + b
		dp[i+1][2] = max(dp[i][0], dp[i][1]) + c
		
	print(max(dp[n][0],dp[n][1],dp[n][2]))
	
	
	
if __name__ == "__main__":
	main()

Solution (Python):



geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
	n=gete(int)
	dp=[[0]*3 for _ in range(n+1)]
	
	
	for i in range(n):
		a,b,c=geta(int)
		dp[i+1][0] = max(dp[i][1], dp[i][2]) + a
		dp[i+1][1] = max(dp[i][2], dp[i][0]) + b
		dp[i+1][2] = max(dp[i][0], dp[i][1]) + c
		
	print(max(dp[n][0],dp[n][1],dp[n][2]))
	
	
	
if __name__ == "__main__":
	main()

Solution (Python):

import sys
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines
 
 




 
def main():
	n=int(input())
	dp=[[0]*3 for _ 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][2], dp[i][0]) + b
		dp[i+1][2] = max(dp[i][0], dp[i][1]) + c
		
	print(max(dp[n][0],dp[n][1],dp[n][2]))
	
	
	
if __name__ == "__main__":
	main()

Solution (Python):



geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
    N = gete(int)
    a = [0]*(N+1)
    b, c = a[:], a[:]

    for i in range(N):
        av, bv, cv = geta(int)
        a[i+1] = max(av + b[i], av + c[i])
        b[i+1] = max(bv + c[i], bv + a[i])
        c[i+1] = max(cv + a[i], cv + b[i])

    print(max(a[-1], b[-1], c[-1]))

if __name__ == "__main__":
    main()

Solution (Python):



geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
    N = gete(int)
    a = [0]*(N+1)
    b, c = a[:], a[:]

    for i in range(N):
        av, bv, cv = geta(int)
        a[i+1] = av + max(b[i], c[i])
        b[i+1] = bv + max(c[i], a[i])
        c[i+1] = cv + max(a[i], b[i])

    print(max(a[-1], b[-1], c[-1]))

if __name__ == "__main__":
    main()

Solution (Python):



geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
    N = gete(int)
    p, q, r = 0,0,0
    for _ in range(N):
        a,b ,c = geta(int)
        p,q,r = a + max(q,r), b + max(r,p), c + max(p,q)

    print(max(p,q,r))

if __name__ == "__main__":
    main()

Solution (Python):



geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
    N = gete(int)
    cur = [0]*3 
    for _ in range(N):
        a = geta(int)
        cur = [max(cur[j-1], cur[j-2]) + a[j] for j in range(3)] 

    print(max(cur))

if __name__ == "__main__":
    main()

Solution (Python):



geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
    N = gete(int)
    a = (geta(int) for _ in range(N))

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

    for i, ai in enumerate(a):
        for j in range(3):
            dp[i+1][j] = max(dp[i][j-1], dp[i][j-2]) + ai[j] 


    print(max(dp[N]))

if __name__ == "__main__":
    main()

Solution (Python):



geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
    N = gete(int)

    cur, prev = [0]*3, [0]*3

    for _ in range(N):
        a, b, c = geta(int)
        prev, cur = cur, prev
        cur[0] = max(prev[1], prev[2]) + a
        cur[1] = max(prev[2], prev[0]) + b
        cur[2] = max(prev[0], prev[1]) + c


    print(max(cur))

if __name__ == "__main__":
    main()

Solution (Python):



geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

N = gete(int)

cur, prev = [0]*3, [0]*3

for _ in range(N):
    a, b, c = geta(int)
    prev, cur = cur, prev
    cur[0] = max(prev[1], prev[2]) + a
    cur[1] = max(prev[2], prev[0]) + b
    cur[2] = max(prev[0], prev[1]) + c


print(max(cur))

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

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

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

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

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

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

Solution (Python):
import numpy as np
n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
dp = np.zeros((n,3), dtype='int64')
l = np.array(l)
dp[0] = l[0]
for i in range(1,n):
    dp[i][0] = l[i][0] + max(dp[i-1][1], dp[i-1][2]) 
    dp[i][1] = l[i][1] + max(dp[i-1][0], dp[i-1][2]) 
    dp[i][2] = l[i][2] + max(dp[i-1][0], dp[i-1][1])
print(np.max(dp[n-1]))

Solution (Python):



geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

N = gete(int)

cur = [0] * 3

for _ in range(N):
    a, b, c = geta(int)
    prev = cur[:]
    cur[0] = max(prev[1], prev[2]) + a
    cur[1] = max(prev[2], prev[0]) + b
    cur[2] = max(prev[0], prev[1]) + c

print(max(cur))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def solve(n,pos):
    global data,helper
    if(n==-1):
        return 0
    if(helper[n][pos]!=-1):
        return helper[n][pos]
    if(pos==0):
        helper[n][pos]=max(data[n][1]+solve(n-1,1),data[n][2]+solve(n-1,2))
        return helper[n][pos]
    elif(pos==1):
        helper[n][pos] = max(data[n][0]+solve(n-1,0),data[n][2]+solve(n-1,2))
        return helper[n][pos]
    else:
        helper[n][pos] = max(data[n][1]+solve(n-1,1),data[n][0]+solve(n-1,0))
        return helper[n][pos]
n=int(input())
data=[]
helper=[[-1 for y in range(3)] for x in range(n)]
for _ in range(n):
    temp=[int(x) for x in input().split()]
    data.append(temp)
t1=data[-1][0]+solve(n-2,0)
t2=data[-1][1]+solve(n-2,1)
t3=data[-1][2]+solve(n-2,2)
print(max(t1,t2,t3))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def solve(n,pos):
    global data,helper
    if(n==-1):
        return 0
    if(helper[n][pos]!=-1):
        return helper[n][pos]
    if(pos==0):
        helper[n][pos]=max(data[n][1]+solve(n-1,1),data[n][2]+solve(n-1,2))
        return helper[n][pos]
    elif(pos==1):
        helper[n][pos] = max(data[n][0]+solve(n-1,0),data[n][2]+solve(n-1,2))
        return helper[n][pos]
    else:
        helper[n][pos] = max(data[n][1]+solve(n-1,1),data[n][0]+solve(n-1,0))
        return helper[n][pos]
n=int(input())
data=[]
helper=[[-1 for y in range(3)] for x in range(n)]
for _ in range(n):
    temp=[int(x) for x in input().split()]
    data.append(temp)
t1=data[-1][0]+solve(n-2,0)
t2=data[-1][1]+solve(n-2,1)
t3=data[-1][2]+solve(n-2,2)
print(max(t1,t2,t3))

Solution (Python):
n=int(input())
data=[]
t=[[0 for x in range(4)] for w in range(n+1)]
for _ in range(n):
    temp=[int(x) for x in input().split()]
    data.append(temp)
for i in range(1,n+1):
    for j in range(1,4):
        large=0
        for w in range(1,4):
            if(w==j):
                continue
            else:
                if(t[i-1][w]>large):
                    large=t[i-1][w]
        t[i][j]=data[i-1][j-1]+large
print(max(t[-1]))

Solution (Python):
n=int(input())
data=[]
t=[[0 for x in range(4)] for w in range(n+1)]
for _ in range(n):
    temp=[int(x) for x in input().split()]
    data.append(temp)
for i in range(1,n+1):
    for j in range(1,4):
        large=0
        for w in range(1,4):
            if(w==j):
                continue
            else:
                if(t[i-1][w]>large):
                    large=t[i-1][w]
        t[i][j]=data[i-1][j-1]+large
print(max(t[-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):
    a,b,c=map(int,input().split())
    dp[i][0]=a+max(dp[i-1][1],dp[i-1][2])
    dp[i][1]=b+max(dp[i-1][0],dp[i-1][2])
    dp[i][2]=c+max(dp[i-1][0],dp[i-1][1])

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

Solution (Python):
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))

def main():
    n=I()
    a=[]
    b=[]
    c=[]
    for i in range(n):
        tmp=L()
        a.append(tmp[0])
        b.append(tmp[1])
        c.append(tmp[2])
    dp=[[0]*3 for i in range(n)]
    dp[0][0]=a[0]
    dp[0][1]=b[0]
    dp[0][2]=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]))
        
        
    
    
if __name__ == '__main__':
    main()

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

    dp = [[- float('inf') for i in range(3)] for j in range(n + 1)]
    dp[0] = [0] * 3
    for i in range(n):
        for j in range(3):
            for k in range(3):
                if (j == k):
                    continue
                dp[i + 1][k] = max(dp[i + 1][k],
                                   dp[i][j] + abc[i][k])
    print(max(dp[-1]))


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a, b, c = [], [], []
for _ in range(n):
    ai, bi, ci = map(int, input().strip().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
dp = []
dp.append((a[0], b[0], c[0]))
for i in range(1, n):
    prev = dp[i-1]
    chosen_a = a[i] + max(prev[1], prev[2])
    chosen_b = b[i] + max(prev[0], prev[2])
    chosen_c = c[i] + max(prev[0], prev[1])
    dp.append((chosen_a, chosen_b, chosen_c))
res = dp[n-1]
print(max(res[0], res[1], res[2]))

Solution (Python):
n = int(input())
a, b, c = [], [], []
for _ in range(n):
    ai, bi, ci = map(int, input().strip().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
dp = []
dp.append((a[0], b[0], c[0]))
for i in range(1, n):
    prev = dp[i-1]
    chosen_a = a[i] + max(prev[1], prev[2])
    chosen_b = b[i] + max(prev[0], prev[2])
    chosen_c = c[i] + max(prev[0], prev[1])
    dp.append((chosen_a, chosen_b, chosen_c))
res = dp[n-1]
print(max(res[0], res[1], res[2]))

Solution (Python):
def main():
    n = int(input())
    x=[]
    for i in range(n):
        x.append(list((map(int,input().split()))))
    
    for i in range(1,n):
        for j in range(3):
            x[i][j]+=max(x[i-1][(j+1)%3],x[i-1][(j+2)%3]);
    
    print(max(x[n-1]))
if __name__ == "__main__":
    main()

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

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


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

dp[1][0] = happy_mat[0][0]
dp[1][1] = happy_mat[0][1]
dp[1][2] = happy_mat[0][2]

for day in range(2, n+1):
    for activity in range(3):
        dp[day][activity] = max(dp[day-1][(activity+1)%3], dp[day-1][(activity+2)%3]) + happy_mat[day-1][activity]

print(max(dp[n]))

Solution (Python):
N, = list(map(int, input().split()))

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

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

for i in range(N):
  for j in range(3):
    if i - 1 < 0:
      dp[i][j] += ABC[i][j]
    else:
      x = (j + 1) % 3
      y = (j + 2) % 3
      dp[i][j] = max(dp[i-1][x], dp[i-1][y]) + ABC[i][j]

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

Solution (Python):
import numpy as np

N = int(input())
a = np.array([input().split() for i in range(N)], dtype=int)

dp = np.zeros((N, 3), dtype=int)
dp[0] = a[0]

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

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

Solution (Python):
import numpy as np

N = int(input())

a = np.array([input().split() for i in range(N)], dtype=int)

dp = np.zeros((N, 3), dtype=int)
dp[0] = a[0]

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

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

Solution (Python):
def main():
    n = int(input())
    happy = []
    for i in range(n):
        happy.append(list(map(int, input().split())))
    
    dp = [[0 for i in range(3)] for j in range(100010)]

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

    for i in range(n):
        for j in range(3):
            for k in range(3):
                if j == k:
                    continue
                dp[i + 1][k] = chmax(dp[i + 1][k], dp[i][j] + happy[i][k])
    
    print(max(dp[n]))

if __name__ == "__main__":
    main()

Solution (Python):

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



dp = [abcList[0]]


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

print(max(dp[-1]))

Solution (Python):
from sys import stdin


def solve():
    n = int(input())
    A = []
    for _ in range(n):
        k = [int(i) for i in stdin.readline().split()]
        A.append(k)
    if n == 1: return max(A[0])
    for i in range(1, len(A)):
        A[i][0] += max(A[i-1][1], A[i-1][2])
        A[i][1] += max(A[i-1][0], A[i-1][2])
        A[i][2] += max(A[i-1][0], A[i-1][1])
    return max(A[-1])

print(solve())

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(n):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + abc[i][k])
                
ans = 0                
for i in range(3):
  ans = max(ans, dp[n][i])
print(ans)

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

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

print(max(dp))

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

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

Solution (Python):

from __future__ import division, print_function
from collections import defaultdict, Counter, deque
from future_builtins import ascii, filter, hex, map, oct, zip
from itertools import imap as map, izip as zip, permutations, combinations, combinations_with_replacement
from __builtin__ import xrange as range
from math import ceil, factorial, log
from _continuation import continulet
from cStringIO import StringIO
from io import IOBase
import __pypy__
from bisect import bisect, insort, bisect_left, bisect_right
from fractions import Fraction
from functools import reduce
import string
import sys
import os
import re
inf = float('inf')
mod_ = int(1e9) + 7
mod = 998244353

def factors(n):
    from functools import reduce
    return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def sieve(m):
    n=1
    primes = {}
    arr=set([])
    for i in range(2, int(m ** 0.5) + 1):
        a = n // i
        b = m // i
        for k in range(max(2, a), b + 1):
            c = i * k
            primes[c] = 1

    for i in range(max(n, 2), m + 1):
        if i not in primes:
            arr.add(i)

    return arr

def nc2(x):
    return (x*(x-1))//2
class DisjointSetUnion:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = n
 
    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a
 
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a != b:
            if self.size[a] < self.size[b]:
                a, b = b, a
 
            self.num_sets -= 1
            self.parent[b] = a
            self.size[a] += self.size[b]
 
    def set_size(self, a):
        return self.size[self.find(a)]
 
    def __len__(self):
        return self.num_sets



def main():
    n=int(input())
    arr=[list(map(int,input().split())) for i in range(n)]
    dp=[[0,0,0] for i in range(n+1)]
    for i in range(1,n+1):
        dp[i][0]=max(dp[i-1][0],arr[i-1][0]+max(dp[i-1][1],dp[i-1][2]))
        dp[i][1]=max(dp[i-1][1],arr[i-1][1]+max(dp[i-1][0],dp[i-1][2]))
        dp[i][2]=max(dp[i-1][2],arr[i-1][2]+max(dp[i-1][0],dp[i-1][1]))
    
    print(max(dp[-1]))











        

        
    




    





BUFSIZE = 8192

class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    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("\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()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
ls = [(0, 0, 0)]
for x in range(n):
    a, b, c = map(int, input().split())
    ls.append((a, b, c))
 
dpa = 0
dpb = 0
dpc = 0
    
for i in range(1, n+1):
    a, b, c = ls[i]
    dpa, dpb, dpc = max(dpb+a, dpc+a), max(dpa+b, dpc+b), max(dpa+c, dpb+c)

print(max(dpa, dpb, dpc))

Solution (Python):
n = int(input())
ls = [(0,0,0)]
for _ in range(n):
    a,b,c=map(int, input().split())
    ls.append((a,b,c))

dpa = 0
dpb = 0
dpc = 0

for x in range(1,n+1):
    a,b,c = ls[x]
    dpa, dpb, dpc = max(dpc+a,dpb+a), max(dpa+b,dpc+b), max(dpa+c,dpb+c)


print(max(dpa,dpb,dpc))

Solution (Python):
n = int(input())
ls = [(0,0,0)]
for _ in range(n):
    a,b,c=map(int, input().split())
    ls.append((a,b,c))

dpa = [0]*(n+1)
dpb = [0]*(n+1)
dpc = [0]*(n+1)

for x in range(1,n+1):
    a,b,c = ls[x]
    dpa[x] = max(dpc[x-1]+a,dpb[x-1]+a)
    dpb[x] = max(dpa[x-1]+b,dpc[x-1]+b)
    dpc[x] = max(dpa[x-1]+c,dpb[x-1]+c)


print(max(dpa[-1],dpb[-1],dpc[-1]))

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
x=int(input())
A=[]
B=[]
C=[]
dictA=[-1]*x
dictB=[-1]*x
dictC=[-1]*x
for i in range(x):
    a,b,c=list(map(int,input().split()))
    A.append(a)
    B.append(b)
    C.append(c)
def maxA(n):
    if dictA[n]!=-1:
        return dictA[n]
    if n==0:
        dictA[n]=A[0]
        return A[0]
    dictA[n]=A[n]+max(maxB(n-1),maxC(n-1))
    return dictA[n]
def maxB(n):
    if dictB[n]!=-1:
        return dictB[n]
    if n==0:
        dictB[n]=B[0]
        return B[0]
    dictB[n]=B[n]+max(maxA(n-1),maxC(n-1))
    return dictB[n]
def maxC(n):
    if dictC[n]!=-1:
        return dictC[n]
    if n==0:
        dictC[n]=C[0]
        return C[0]
    dictC[n]=C[n]+max(maxB(n-1),maxA(n-1))
    return dictC[n]
def Nmax(n):
    return max(maxA(n),maxB(n),maxC(n))
print(Nmax(x-1))

Solution (Python):
n = int(input())
inf = float("inf")

dp = [[inf]*(3) for i in range(n)]
dp[0] = list(map(int, input().split()))

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

  dp[i+1][0] = max(dp[i][1] + a, dp[i][2] + a)
  dp[i+1][1] = max(dp[i][2] + b, dp[i][0] + b)
  dp[i+1][2] = max(dp[i][0] + c, dp[i][1] + c)  


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

Solution (Python):
def main():
    n=int(input())
    dp=[0]*(3)
    for _ in range(n):
        dp1=[0]*3 
        nums=list(map(int,input().split()))
        for i in range(3):
            for j in range(3):
                if i!=j:
                    dp1[j]=max(dp1[j],dp[i]+nums[j])
            
        dp=dp1
    print( max(dp[0],dp[1],dp[2]))
if __name__ == '__main__':
    main()

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(n):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + abc[i][k])
ans = 0
for i in range(3):
    ans = max(ans, dp[n][i])
print(ans)

Solution (Python):
from pprint import pprint


n = int(input())

points = [list(map(int,input().split())) for _ in range(n)]

dp_table = [[-float("inf")]*(n+1) for _ in range(3)]


dp_table[0][0] = 0
dp_table[1][0] = 0
dp_table[2][0] = 0

for i in range(1,n+1):
    for abc in range(3):
        for before_abc in range(3):
            if abc != before_abc:
                dp_table[abc][i] = max(dp_table[abc][i],dp_table[before_abc][i-1] + points[i-1][abc])
            else:
                continue

pprint(max(dp_table[0][-1],dp_table[1][-1],dp_table[2][-1]))

Solution (Python):
from pprint import pprint


n = int(input())

points = [list(map(int,input().split())) for _ in range(n)]

dp_table = [[-float("inf")]*(n+1) for _ in range(3)]


dp_table[0][0] = 0
dp_table[1][0] = 0
dp_table[2][0] = 0

for i in range(1,n+1):
    for abc in range(3):
        for before_abc in range(3):
            if abc != before_abc:
                dp_table[abc][i] = max(dp_table[abc][i],dp_table[before_abc][i-1] + points[i-1][abc])
            else:
                continue

pprint(max(dp_table[0][-1],dp_table[1][-1],dp_table[2][-1]))

Solution (Python):
def main():
    N = int(input())
    happiness = [list(map(int, input().split(' '))) for _ in range(N)]
    dp = [[0 for _ in range(3)] for _ in range(N)]
    dp[0] = happiness[0]
    for i in range(1, N):
        for j in range(3):
            dp[i][j] = max([
                dp[i][j],
                happiness[i][j] + dp[i - 1][(j + 1) % 3],
                happiness[i][j] + dp[i - 1][(j + 2) % 3]
            ])
    print(max(dp[N - 1]))


if __name__ == '__main__':
    main()

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

Solution (Python):


N = int(input())
act = []
for i in range(N):
	act.append([int(x) for x in input().split()])

dp = [[0 for x in range(3)] for y in range(N)]

dp[0][0] = act[0][0]
dp[0][1] = act[0][1]
dp[0][2] = act[0][2]

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

m = 0
for i in range(3):
	m = max(m, dp[N-1][i])

print(m)