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):
n = int(input())
abc = []
for i in range(n):
    abc.append([int(i) for i in input().split()])

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

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

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)]
for i in range(N):
	DP[i]=[ABC[i][0]+max(DP[i-1][1],DP[i-1][2]),ABC[i][1]+max(DP[i-1][0],DP[i-1][2]),ABC[i][2]+max(DP[i-1][1],DP[i-1][0])]
print(max(DP[N-1]))

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

ans = [a[0]]

for i in range(1, n):
    t = [0,0,0]
    for j in range(3):
        t[j] = max([ans[i-1][k] + a[i][j] if k != j else 0 for k in range(3)])
    ans.append(t)
    
print(max(ans[n-1]))

Solution (Python):
def knapsack(points):
    days = len(points)

    
    dp = [[0] * 3 for _ in range(days)]
    dp[0] = points[0]
    for i in range(1, days):
        for j in range(3):
            dp[i][j] = points[i][j] + max([dp[i-1][k] for k in range(3) if k != j])
    return max(dp[-1])


if __name__ == "__main__":
    N = int(input())
    points = []
    for _ in range(N):
        points.append([int(x) for x in input().split()])

    print(knapsack(points))

Solution (Python):
n = int(input())
a = [[0]*3 for i in range(n+1)]

for i in range(1,n+1) :
    a[i] = list(map(int,input().split()))


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

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

print(max(dp[n]))

Solution (Python):
def knapsack(points):
    days = len(points)

    
    dp = [[0]*3] * days
    dp[0] = points[0]
    for i in range(1, days):
        newdp = [0] * 3
        for j in range(3):
            newdp[j] = points[i][j] + max([dp[i-1][k] for k in range(3) if k != j])
            
        dp[i] = newdp

    return max(dp[-1])


if __name__ == "__main__":
    N = int(input())
    points = []
    for _ in range(N):
        points.append([int(x) for x in input().split()])

    print(knapsack(points))

Solution (Python):
import numpy as np

n = int(input())
X = np.array([input().split() for _ in range(n)], np.int64)
dp = np.zeros((n + 1, 3), np.int64)
dp[0, 0] = dp[0, 1] = dp[0, 2] = 0
for i in range(n):
    for j in range(3):
        dp[i + 1, j] = X[i, j] + max(dp[i, k] for k in range(3) if j != k)
print(max(dp[n]))

Solution (Python):

import numpy as np

n = int(input())
dp = np.zeros((n+10, 3))

def cmax(a,b):
    if a>b:
        return a
    else: 
        return b
        
for i in range(1, n+1):
    a, b, c = map(int, input().split())
    
    dp[i][0] = cmax(dp[i-1][1]+a, dp[i-1][2]+a)
    
    dp[i][1] = cmax(dp[i-1][0]+b, dp[i-1][2]+b)
    
    dp[i][2] = cmax(dp[i-1][0]+c, dp[i-1][1]+c)

print(int(max(dp[i,:])))

Solution (Python):
n=input()
a=[map(int,raw_input().split()) for _ in xrange(n)]
z=[[0]*3 for _ in xrange(n)]
z[0]=a[0]
for i in xrange(1,n):
    for j in xrange(3):
        for k in xrange(3):
            if j!=k:
                z[i][j]=max(z[i][j],z[i-1][k]+a[i][j])
print max(z[-1])

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

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[n]))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
options = [None] * N
for i in range(N):
    options[i] = tuple(int(x) for x in readline().split())


def solve():
    da, db, dc = 0, 0, 0
    for i in range(N):
        xa, xb, xc = options[i]
        xa += da
        xb += db
        xc += dc
        da, db, dc = max(xb, xc), max(xa, xc), max(xa, xb)
    print(max(da, db, dc))


if __name__ == "__main__":
    solve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
options = [None] * N
for i in range(N):
    options[i] = tuple(int(x) for x in readline().split())


def solve():
    da, db, dc = 0, 0, 0
    for i in range(N):
        xa, xb, xc = options[i]
        xa += da
        xb += db
        xc += dc
        da, db, dc = max(xb, xc), max(xa, xc), max(xa, xb)
    print(max(da, db, dc))


if __name__ == "__main__":
    solve()

Solution (Python):
def main():
    N = int(input())
    a = [None for _ in range(N)]
    b = [None for _ in range(N)]
    c = [None for _ in range(N)]
    for i in range(N):
        a[i], b[i], c[i] = map(int, input().split())
    dp = [None for _ in range(N)]
    dp[0] = [a[0], b[0], c[0]]
    for i in range(1, N):
        dp[i] = [None for _ in range(3)]
        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]))


if __name__ == "__main__":
    main()

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]+a[i] , dp[i][2]+a[i] )
    dp[i+1][1]= max( dp[i][0]+b[i] , dp[i][2]+b[i] )
    dp[i+1][2]= max( dp[i][0]+c[i] , dp[i][1]+c[i] )
print(max(dp[n]))

Solution (Python):
N = int(input())
abc = [tuple(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):
    dp[i+1][j] = max(dp[i][j-1], dp[i][j-2]) + abc[i][j]
    
print(max(dp[-1]))

Solution (Python):
t=int(input())
a=[[0 for i in range(3)] for j in range(t)]
res=0
for i in range (t):
  a[i][0],a[i][1],a[i][2]=list(map(int, input().split()))
 
   
dp = [[0] * 3 for _ in range(t + 1)]


 
for i in range (0,t):
  for curr in range(3):
    for last in range(3):
      if last!=curr:
        dp[i+1][curr]=max(dp[i+1][curr],dp[i][last]+a[i][curr])
    
    if i==t-1:
      res=max(res,dp[i+1][curr])
      
print(res)

Solution (Python):
n=int(input())
a,b,c=map(int,input().split())
for _ in range(1,n):
    aa,bb,cc=map(int,input().split())
    a,b,c=aa+max(b,c),bb+max(a,c),cc+max(a,b)
print(max(a,b,c))

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][j] = max(dp[i + 1][j], dp[i][k] + ABC[i][j])

ans = 0

for i in range(3):
    ans = max(ans, dp[N][i])

print(ans)

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][j] = max(dp[i + 1][j], dp[i][k] + ABC[i][j])

ans = 0

for i in range(3):
    ans = max(ans, dp[N][i])

print(ans)

Solution (Python):
import sys






input = sys.stdin.readline
import numpy as np
N = int(input())
abc = np.zeros((N,3))
for i in range(N):
    abc[i] = list(map(int,input().split()))

dp = np.zeros((N,3))
for i in range(N):
    if i == 0:
        dp[i] = abc[i]
        continue
    dp_a,dp_b,dp_c = dp[i-1]
    dp[i] = abc[i] + [max(dp_b,dp_c),max(dp_a,dp_c),max(dp_a,dp_b)]
print(int(max(dp[N-1])))

Solution (Python):
def solve(h):
    dp = [h[0]]
    for i in range(1, len(h)):
        a = h[i][0] + max(dp[i-1][1], dp[i-1][2])
        b = h[i][1] + max(dp[i-1][0], dp[i-1][2])
        c = h[i][2] + max(dp[i-1][0], dp[i-1][1])
        dp.append([a, b, c])
    return max(dp[-1])


if __name__ == "__main__":
    h = [[int(x) for x in input().split()] for y in range(int(input()))]
    print(solve(h))

Solution (Python):


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

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

dp[0] = Z[0]

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

print(max(dp[-1]))

Solution (Python):
from sys import stdin,stdout
n=int(stdin.readline())
p,q,r=map(int,stdin.readline().split())
for i in range(1,n):
    a,b,c=map(int,stdin.readline().split())
    p1=max(a+q,a+r)
    q1=max(b+p,b+r)
    r1=max(c+p,c+q)
    p,q,r=p1,q1,r1
stdout.write(str(max(p,q,r))+'\n')

Solution (Python):
import numpy as np
import math

def solve():
    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 i in range(n+5)]
    for i in range(1,n+1):
        dp[i][0] = max(dp[i-1][1]+a[i-1],dp[i-1][2]+a[i-1])
        dp[i][1] = max(dp[i-1][0]+b[i-1],dp[i-1][2]+b[i-1])
        dp[i][2] = max(dp[i-1][0]+c[i-1],dp[i-1][1]+c[i-1])
    print(max(dp[n]))
    return 0
 
if __name__ == "__main__":
    solve()

Solution (Python):
n=int(input())
a,b,c=map(int,input().split())
for _ in range(1,n):
    aa,bb,cc=map(int,input().split())
    a,b,c=aa+max(b,c),bb+max(a,c),cc+max(a,b)
print(max(a,b,c))

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


dp = [[0]*3 for _i 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], dp[i][2]) + a[i+1]
    dp[i+1][1] = max(dp[i][0], dp[i][2]) + b[i+1]
    dp[i+1][2] = max(dp[i][0], dp[i][1]) + c[i+1]
print(max(dp[n-1]))

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

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

print(max(dp[n]))

Solution (Python):
N = int(input())
ABC = []
for i in range(N):
    ABC.append(list(map(int,input().split())))
dp = [[0]*3 for i in range(N)]
dp[0] = ABC[0]
if N>1:
    for i in range(1,N):
        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][0]+ABC[i][1],dp[i-1][2]+ABC[i][1])
        dp[i][2] = max(dp[i-1][0]+ABC[i][2],dp[i-1][1]+ABC[i][2])
print(max(dp[-1]))

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

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

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

print(max(dp[-1]))

Solution (Python):
n=int(input())
abc=[list(map(int,input().split())) for _ in range(n)]
dp=[[0,0,0] for _ 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[n]))

Solution (Python):
import numpy as np


def main():
	N = int(input())

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

	h = list(map(int, input().split(" ")))
	dp[0,0], dp[0,1], dp[0,2] = h

	for i in range(1,N):
		h = list(map(int, input().split(" ")))
		dp[i,0] = max(dp[i-1,1]+h[0], dp[i-1,2]+h[0])
		dp[i,1] = max(dp[i-1,0]+h[1], dp[i-1,2]+h[1])
		dp[i,2] = max(dp[i-1,0]+h[2], dp[i-1,1]+h[2])

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

if __name__ == '__main__':
	main()

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



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

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

print(max(dp[N]))

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


max_happiness = [[None] * 3 for _ in range(N)]

for k in range(N):
    if k == 0:
        max_happiness[k] = [int(n) for n in input().split()]
    else:
        ak, bk, ck = [int(n) for n in input().split()]

        a_opt, b_opt, c_opt = max_happiness[k-1]
        max_happiness[k][0] = ak + max(b_opt, c_opt)
        max_happiness[k][1] = bk + max(a_opt, c_opt)
        max_happiness[k][2] = ck + max(a_opt, b_opt)

print(max(max_happiness[-1]))

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


max_happiness = [[None] * 3 for _ in range(N)]

for k in range(N):
    if k == 0:
        max_happiness[k] = [int(n) for n in input().split()]
    else:
        ak, bk, ck = [int(n) for n in input().split()]

        a_opt, b_opt, c_opt = max_happiness[k-1]
        max_happiness[k][0] = ak + max(b_opt, c_opt)
        max_happiness[k][1] = bk + max(a_opt, c_opt)
        max_happiness[k][2] = ck + max(a_opt, b_opt)

print(max(max_happiness[-1]))

Solution (Python):
def main():
    n = int(input())
    matrix = []
    tb = [[0] * 4 for _ in range(n + 1)]
    for _ in range(n):
        matrix.append([int(e) for e in input().split()])
    
    for i in range(1, n + 1):
        for j in range(1, 4):
            for l in range(1, 4):
                if j == l: continue
                tb[i][j] = max(tb[i][j], tb[i - 1][l] + matrix[i - 1][j - 1])
    
    print(max(tb[n]))
    return 0

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = [0]*n
b = [0]*n
c = [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][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] + a[i], dp[i-1][2] + a[i])
    dp[i][1] = max(dp[i-1][0] + b[i], dp[i-1][2] + b[i])
    dp[i][2] = max(dp[i-1][0] + c[i], dp[i-1][1] + c[i])

print(max(dp[-1]))

Solution (Python):
n = int(input())
l = [list(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])+l[i][0]
  dp[i+1][1] = max(dp[i][0],dp[i][2])+l[i][1]
  dp[i+1][2] = max(dp[i][0],dp[i][1])+l[i][2]
print(max(dp[n]))

Solution (Python):
N=int(input())
dp=[ [0,0,0] for i in range(N) ]

a,b,c=map(int,input().split())
dp[0][0],dp[0][1],dp[0][2]=a,b,c
for i in range (1,N):
  a,b,c=map(int,input().split())
  da,db,dc=dp[i-1][0],dp[i-1][1],dp[i-1][2]
  dp[i][0]=max(db+a,dc+a)
  dp[i][1]=max(da+b,dc+b)
  dp[i][2]=max(da+c,db+c)
print(max(dp[-1]))

Solution (Python):
import sys
import numpy as np 

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

x, y, z = 0, 0, 0
for a, b, c in h:
    x, y, z = max(y, z) + a, max(x, z) + b, max(x, y) + c

print(max(x, y, z))

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

    dp = [[0] * 3 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(n-1):
        for j in range(3):
            dp[i+1][j] = max(dp[i][(j+1) % 3], dp[i][(j+2) % 3]) + abc[i+1][j]

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

if __name__ == "__main__":
    main()

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

    dp = [[0] * 3 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(n-1):
        for j in range(3):
            dp[i+1][j] = max(dp[i][(j+1) % 3], dp[i][(j+2) % 3]) + abc[i+1][j]

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

if __name__ == "__main__":
    main()

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

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

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

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
data = [list(map(int, input().split(" "))) for i in range(N)]
dp = [[0] * 3 for i in range(N+1)]
dp[0][0]=0
dp[0][1]=0
dp[0][2]=0
ans=0
for i in range(0,N):
    for k in range(3):
        for j in range(3):
            if j != k:
                dp[i+1][k] = max(dp[i+1][k], dp[i][j] + data[i][k])
ans = max(dp[N][0], dp[N][1])
print(max(ans, dp[N][2]))

Solution (Python):
import numpy as np
n=int(input())
abc=np.array([list(map(int,input().split())) for _ in range(n)])
dp=np.zeros((n+1,3),np.int64)


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

Solution (Python):
N = input()

score = [[0,0,0] for n in range(N)]

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

  if n == 0 : score[0] = [a, b, c]
  else : 
    score[n][0] = a + max(score[n-1][1], score[n-1][2])
    score[n][1] = b + max(score[n-1][0], score[n-1][2])
    score[n][2] = c + max(score[n-1][0], score[n-1][1])
  
print max(score[-1])

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

dp = [[-1]*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):
    for j in range(3):
        dp[i][j] = max(dp[i-1][(j+1) % 3], dp[i-1][(j+2) % 3]) + abc[i][j]
print(max(dp[-1]))

Solution (Python):
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
dpa = [0]*N
dpb = [0]*N
dpc = [0]*N
dpa[0] = A[0][0]
dpb[0] = A[0][1]
dpc[0] = A[0][2]
for i in range(1,N):
    a = A[i][0]
    b = A[i][1]
    c = A[i][2]
    dpa[i] = max(dpb[i-1]+a,dpc[i-1]+a)
    dpb[i] = max(dpa[i-1]+b,dpc[i-1]+b)
    dpc[i] = max(dpb[i-1]+c,dpa[i-1]+c)
Min = dpa[N-1]
Mmin = max(dpb[N-1],dpc[N-1])
print(max(Min,Mmin))

Solution (Python):
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
dpa = [0]*N
dpb = [0]*N
dpc = [0]*N
dpa[0] = A[0][0]
dpb[0] = A[0][1]
dpc[0] = A[0][2]
for i in range(1,N):
    a = A[i][0]
    b = A[i][1]
    c = A[i][2]
    dpa[i] = max(dpb[i-1]+a,dpc[i-1]+a)
    dpb[i] = max(dpa[i-1]+b,dpc[i-1]+b)
    dpc[i] = max(dpb[i-1]+c,dpa[i-1]+c)
Min = dpa[N-1]
Mmin = max(dpb[N-1],dpc[N-1])
print(max(Min,Mmin))

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

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

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] + a[i][k])

print(max(dp[N]))

Solution (Python):
N=int(input())
h=[[0,0,0] for i in range(N)]
dp=[[0,0,0] for j in range(N)]
for i in range(N):
    h[i][0],h[i][1],h[i][2]=map(int,input().split())
dp[0][0],dp[0][1],dp[0][2]=h[0][0],h[0][1],h[0][2]
for i in range(1,N):
    dp[i][0]=max(dp[i-1][1],dp[i-1][2])+h[i][0]
    dp[i][1]=max(dp[i-1][0],dp[i-1][2])+h[i][1]
    dp[i][2]=max(dp[i-1][0],dp[i-1][1])+h[i][2]

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

Solution (Python):
import sys
from io import StringIO
import unittest

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

    ans = [[-1 for _ in range(3)] for __ in range(n)]

    ans[0][0], ans[0][1], ans[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:
                    ans[i][j] = max(ans[i][j], ans[i - 1][k] + abc[i][j])
                else:
                    continue
    print(max(ans[-1]))

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3
10 40 70
20 50 80
30 60 90"""
        output = """210"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1
100 10 1"""
        output = """100"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1"""
        output = """46"""
        self.assertIO(input, output)

if __name__ == "__main__":
    
    resolve()

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

ans = []
ans.append(happy[0])

for i in range(1, n):
    ans.append( [max(ans[i-1][(j+1)%3] + happy[i][j], ans[i-1][(j+2)%3] + happy[i][j]) for j in range(3)] )

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

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

Solution (Python):
def main():
  import sys
  input = sys.stdin.readline
  n=int(input())
  l=[tuple(map(int,input().split())) for _ in range(n)]
  dp=[[0]*3 for _ in range(n+1)]
  for i in range(1,n+1):
    dp[i][0]=max(dp[i-1][1],dp[i-1][2])+l[i-1][0]
    dp[i][1]=max(dp[i-1][2],dp[i-1][0])+l[i-1][1]
    dp[i][2]=max(dp[i-1][0],dp[i-1][1])+l[i-1][2]
  print(max(dp[-1]))
if __name__=='__main__':
  main()

Solution (Python):
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
     
    N = int(readline())
    m = map(int,read().split())
    ABC = zip(m,m,m)
     
    x,y,z = 0,0,0 
    for a,b,c in ABC:
        x,y,z = max(y,z)+a,max(x,z)+b,max(x,y)+c
     
    answer = max(x,y,z)
    print(answer)
main()

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

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


for day in range(N - 1):
    for todo in range(3):
        for did in range(3):
            if todo != did:
                dp[day + 1][todo] = max(dp[day][did] + abc[day + 1][todo], dp[day + 1][todo])
print(max(dp[N - 1]))

Solution (Python):
n=int(input())
happy=list(map(int,input().split(' ')))
for i in range(1,n):
    h=list(map(int,input().split(' ')))
    x=max(happy[1]+h[0],happy[2]+h[0])
    y=max(happy[2]+h[1],happy[0]+h[1])
    z=max(happy[0]+h[2],happy[1]+h[2])
    happy=[x,y,z]
print(max(happy))

Solution (Python):


def solve(N, arr):

	dp = [0] * 3

	for j in range(3):
		dp[j] = arr[0][j]

	for i in range(1, N):
		dp2 = [0] * 3
		for j in range(3):
			for x in [(j - 1) % 3, (j + 1) % 3]:

				if 0 <= x < 3:
					dp2[j] = max(dp2[j], dp[x] + arr[i][j])
		dp = dp2
	return max(dp)

N = int(input())
arr = []
for _ in range(N):
	arr.append([int(s) for s in input().split()])
print(solve(N, arr))

Solution (Python):
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N)]
INF = 1 << 100
dp = [[0] * 3 for i in range(N + 1)]
for i in range(1, N+1):
    for j in range(3):
        for k in range(3):
            if j == k : continue
            dp[i][k] = max(ABC[i-1][k] + dp[i - 1][j], dp[i][k])
print(max(dp[N]))

Solution (Python):
n = int(input())
ABC = [tuple(map(int, input().split())) for i in range(n)]
A = [a for a, b, c in ABC]
B = [b for a, b, c in ABC]
C = [c for a, b, c in ABC]
DP = [[0 for j in range(3)] for i in range(n+1)]
for i in range(1, n+1):
    DP[i][0] = max(DP[i-1][1], DP[i-1][2])+A[i-1]
    DP[i][1] = max(DP[i-1][2], DP[i-1][0])+B[i-1]
    DP[i][2] = max(DP[i-1][0], DP[i-1][1])+C[i-1]
print(max(DP[n]))

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

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

for i in range(1,n+1):
    a,b,c=d[i]
    dp_a,dp_b,dp_c=dp[i-1]
    dp[i]=[max(dp_b+a,dp_c+a),max(dp_c+b,dp_a+b),max(dp_a+c,dp_b+c)]

dp_a,dp_b,dp_c=dp[n]
print(max(dp_a,dp_b,dp_c))

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

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

dpA = [0]*N
dpB = [0]*N
dpC = [0]*N
dpA[0] = S[0][0]
dpB[0] = S[0][1]
dpC[0] = S[0][2]

for i in range(1, N):
    dpA[i] = max(dpB[i-1], dpC[i-1]) + S[i][0]
    dpB[i] = max(dpC[i-1], dpA[i-1]) + S[i][1]
    dpC[i] = max(dpA[i-1], dpB[i-1]) + S[i][2]

print(max(dpA[N-1],dpB[N-1],dpC[N-1]))

Solution (Python):
import math
import operator as op
from functools import reduce
from fractions import Fraction as frac

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
"""
int(input())
map(int,input().split())
list(map(int,input().split()))
"""

n=int(input())
A=[]
for i in range(n):
    x=list(map(int,input().split()))
    A.append(x)
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]+A[i-1][1],dp[i-1][2]+A[i-1][2])
    dp[i][1]=max(dp[i-1][0]+A[i-1][0],dp[i-1][2]+A[i-1][2])
    dp[i][2]=max(dp[i-1][1]+A[i-1][1],dp[i-1][0]+A[i-1][0])
print(max(dp[n]))

Solution (Python):
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq

from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write

INF=int(10e9)

n=int(data())
dp1=[0]*(n+1)
dp2=[0]*(n+1)
dp3=[0]*(n+1)
for i in range(1,n+1):
    a,b,c=mdata()
    dp1[i]=max(dp2[i-1],dp3[i-1])+a
    dp2[i] = max(dp1[i - 1], dp3[i - 1]) + b
    dp3[i] = max(dp2[i - 1], dp1[i - 1]) + c
print(max(dp1[-1],dp2[-1],dp3[-1]))

Solution (Python):
from sys import stdin



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


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  
    a_b_c_arr = []
    for i in range(N):
        _ = list(map(int,_in[i+1].split(' ')))  
        a_b_c_arr.append(_)
    
    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]+a_b_c_arr[i][k])
    cnt = max(dp[N])
    
    print(cnt)

Solution (Python):
N = int(input())
A = [0]*N
for i in range(N):
    A[i] = list(map(int, input().split()))
def solve(N,A):
    dp = [[0]*3 for i in range(N)]
    dp[0][0] = A[0][0]
    dp[0][1] = A[0][1]
    dp[0][2] = A[0][2]
    for i in range(1,N):
        dp[i][0] = max(dp[i-1][1],dp[i-1][2])+A[i][0]
        dp[i][1] = max(dp[i-1][0],dp[i-1][2])+A[i][1]
        dp[i][2] = max(dp[i-1][0],dp[i-1][1])+A[i][2]
    ans = max(dp[-1])
    return ans
print(solve(N,A))

Solution (Python):
N = int(input())
li = [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):
    a = 0
    for k in range(3):
      if j == k:
        continue
      a = max(a,(dp[i][k]))
    dp[i+1][j] = max(dp[i+1][j],a + li[i][j])
  
print(max(dp[-1]))

Solution (Python):


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

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


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

Solution (Python):
n = int(input())
a = [[int(i) for i in input().split()] for _ in range(n)]
dp = [[0,0,0] for i 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][k] = max(dp[i][k],dp[i-1][j] + a[i-1][k])
print(max(dp[n]))

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

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

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

Solution (Python):
N = int(input())
abc = []
for _ in range(N):
    x = tuple(map(int, input().split()))
    abc.append(x)
dp = [[0 for _ in range(3)] 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][0], dp[i-1][1] + abc[i][0], dp[i-1][2] + abc[i][0])
    dp[i][1] = max(dp[i][1], dp[i-1][0] + abc[i][1], dp[i-1][2] + abc[i][1])
    dp[i][2] = max(dp[i][2], dp[i-1][0] + abc[i][2], dp[i-1][1] + abc[i][2])


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