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

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

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

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

dpa = [0]*N
dpb = [0]*N
dpc = [0]*N
dpa[0] = a[0]
dpb[0] = b[0]
dpc[0] = c[0]

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

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

Solution (Python):
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

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

Solution (Python):
n = int(input())
dp = [0, 0, 0]
for i in range(n):
    val = list(map(int, input().split()))
    next_dp = [0, 0, 0]
    for j in range(3):
        next_dp[j] = val[j] + max([dp[k] for k in range(3) if j != k])
    dp = next_dp
print(max(dp))

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

Solution (Python):
import numpy as np
n= int(input())
a = np.zeros(n+2)
b = np.zeros(n+2)
c = np.zeros(n+2)
dp = np.zeros(3)
for i in range(n):
 a[i],b[i],c[i] = (int(j) for j in input().split())
 dp = [a[i]+max(dp[1],dp[2]),b[i]+max(dp[0],dp[2]),c[i]+max(dp[0],dp[1])]

print(int(max(dp)))

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

Solution (Python):
n = int(input())
dp = [0, 0, 0]
 
for i in range(n):
    A = [int(i) for i in input().split()]
    dp = [A[0] + max(dp[1], dp[2]), A[1] + max(dp[0], dp[2]), A[2] + max(dp[0], dp[1])]
 
print( max(dp) )

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

Solution (Python):
n = int(input())
dp = [0, 0, 0]

for i in range(n):
    A = [int(i) for i in input().split()]
    dp = [A[0] + max(dp[1], dp[2]), A[1] + max(dp[0], dp[2]), A[2] + max(dp[0], dp[1])]

print(max(dp))

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)

NOW = [[-1,-1,-1] for i in range(N)]
NOW[0] = [A[0],B[0],C[0]]

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

ans = max(NOW[-1])
print(ans)

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 = a + max(y,z),b + max(z,x),c + max(x,y)

print(max(x,y,z))

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

dp = [[10**18]*3 for i in range(N)]
for i in range(3):
    dp[0][i] = days[0][i]

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

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

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

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


for i in range(1, N + 1):
    s = list(map(int, input().split()))
    for j in range(3):
        dp[i][j] = max(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + s[j]
print(max(dp[N]))

Solution (Python):


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

A = [0]
B = [0]
C = [0]
for i in range(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 += [a]
    B += [b]
    C += [c]
print(max(A[-1], B[-1], C[-1]))

Solution (Python):
n = int(input())
ma,mb,mc=0,0,0
for i in range(n):
    a,b,c = map(int,input().split())
    ma1, mb1, mc1 = ma,mb,mc
    ma = max(mb1 + b, mc1 + c)
    mb = max(ma1 + a, mc1 + c)
    mc = max(mb1 + b, ma1 + a)
print(max(ma,mb,mc))

Solution (Python):
n = int(input())
dp = [int(i) for i in input().split()]

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

Solution (Python):
N = int(input())
h = [tuple(map(int,input().split())) for i in range(N)]
inf = float('inf')
DP = [[inf for i in range(3)] for i in range(N)]
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]=h[i+1][0]+max(DP[i][1],DP[i][2])
    DP[i+1][1]=h[i+1][1]+max(DP[i][0],DP[i][2])
    DP[i+1][2]=h[i+1][2]+max(DP[i][0],DP[i][1])

print(max(DP[-1]))

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


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

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

Solution (Python):
N = int( input())
H = [ 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] = H[0]
for i in range(1,N):
    a, b, c = H[i]
    dp[i][0] = max( dp[i-1][1]+a, dp[i-1][2]+a)
    dp[i][1] = max( dp[i-1][0]+b, dp[i-1][2]+b)
    dp[i][2] = max( dp[i-1][0]+c, dp[i-1][1]+c)
print( max( dp[-1]))

Solution (Python):
N = int( input())
H = [ 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] = H[0]
for i in range(1,N):
    a, b, c = H[i]
    dp[i][0] = max( dp[i-1][1]+a, dp[i-1][2]+a)
    dp[i][1] = max( dp[i-1][0]+b, dp[i-1][2]+b)
    dp[i][2] = max( dp[i-1][0]+c, dp[i-1][1]+c)
print( max( dp[-1]))

Solution (Python):
import sys, math


def main():
    N = input()
    days = [map(int, raw_input().split()) for i in range(N)]

    dpMax = [[0, 0, 0] for i in range(N)]
    dpMax[0] = days[0]
    
    for i in range(1, N):
        for j in range(3):
            for k in range(3):
                if j != k:
                    dpMax[i][j] = max(dpMax[i][j], dpMax[i - 1][k] + days[i][j])
            
    print max(max(dpMax[N - 1][0], dpMax[N - 1][1]), dpMax[N - 1][2])


if __name__ == '__main__':
    main()

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

X = [[0]*3 for i in range(N)]
for i in range(N):
    a, b, c = map(int, input().split())
    if i == 0:
        X[i][0] = a
        X[i][1] = b
        X[i][2] = c
    else:
        X[i][0] = max(X[i-1][1], X[i-1][2]) + a
        X[i][1] = max(X[i-1][0], X[i-1][2]) + b
        X[i][2] = max(X[i-1][0], X[i-1][1]) + c

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

Solution (Python):
N = int(input())
happy_list = [list(map(int, input().split())) for n in range(N)]
def chmax(a, b):
    if a > b:
        return a
    else:
        return b
dp_list = [[0, 0, 0]]
for n in range(1, N+1):
    tmp = [0, 0, 0]
    tmp[1] = chmax(tmp[1], dp_list[n-1][0] + happy_list[n-1][1])
    tmp[2] = chmax(tmp[2], dp_list[n-1][0] + happy_list[n-1][2])
    tmp[0] = chmax(tmp[0], dp_list[n-1][1] + happy_list[n-1][0])
    tmp[2] = chmax(tmp[2], dp_list[n-1][1] + happy_list[n-1][2])
    tmp[0] = chmax(tmp[0], dp_list[n-1][2] + happy_list[n-1][0])
    tmp[1] = chmax(tmp[1], dp_list[n-1][2] + happy_list[n-1][1])
    dp_list.append(tmp)
print(max(tmp))

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

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

for index in range(N):
  a,b,c=map(int,input().split())
  if index==0:
    dp[index][0]=a
    dp[index][1]=b
    dp[index][2]=c
  else:
    dp[index][0]=max(dp[index-1][1],dp[index-1][2])+a
    dp[index][1]=max(dp[index-1][0],dp[index-1][2])+b
    dp[index][2]=max(dp[index-1][1],dp[index-1][0])+c

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

Solution (Python):
N = int(input())
s = [[0 for i in range(3)] for j in range(N)]
dp = [[0 for i in range(3)] for j in range(N+1)]
for i in range(N):
    s[i] = [int(j) for j in input().split()]


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

print(max(dp[N]))

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][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):
        if j == 0:
            dp[i][j] = max(dp[i-1][1], dp[i-1][2]) + abc[i][j]
        if j == 1:
            dp[i][j] = max(dp[i-1][0], dp[i-1][2]) + abc[i][j]
        if j == 2:
            dp[i][j] = max(dp[i-1][0], dp[i-1][1]) + abc[i][j]
print(max(dp[n-1]))

Solution (Python):
N=int(input())
a0,b0,c0=map(int,input().split())
for _ in range(1,N):
    a,b,c=map(int,input().split())
    a0,b0,c0=a+max(b0,c0),b+max(a0,c0),c+max(a0,b0)
print(max(a0,b0,c0))

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

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

dpa = [0] * N
dpb = [0] * N
dpc = [0] * N

dpa[0] = a[0]
dpb[0] = b[0]
dpc[0] = c[0]
for i in range(1, N):
    dpa[i] = a[i] + max(dpb[i - 1], dpc[i - 1])
    dpb[i] = b[i] + max(dpc[i - 1], dpa[i - 1])
    dpc[i] = c[i] + max(dpa[i - 1], dpb[i - 1])
print(max(dpa[N - 1], dpb[N - 1], dpc[N - 1]))

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

dpa = [0] * N
dpb = [0] * N
dpc = [0] * N

dpa[0] = a[0]
dpb[0] = b[0]
dpc[0] = c[0]
for i in range(1, N):
    dpa[i] = a[i] + max(dpb[i - 1], dpc[i - 1])
    dpb[i] = b[i] + max(dpc[i - 1], dpa[i - 1])
    dpc[i] = c[i] + max(dpa[i - 1], dpb[i - 1])
print(max(dpa[N - 1], dpb[N - 1], dpc[N - 1]))

Solution (Python):
n = int(input())
a = []
b = []
c = []
for i in range(n):
    at,bt,ct = map(int,input().split())
    a.append(at)
    b.append(bt)
    c.append(ct)
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] = a[i] + max(dp[i-1][1],dp[i-1][2])
    dp[i][1] = b[i] + max(dp[i-1][0],dp[i-1][2])
    dp[i][2] = c[i] + max(dp[i-1][0],dp[i-1][1])
print(max(dp[-1]))

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    aa = [LI() for _ in range(n)]
    r = [0,0,0]
    for a in aa:
        r = [a[i] + max(r[i-1], r[i-2]) for i in range(3)]

    return max(r)


print(main())

Solution (Python):

import sys

sys.setrecursionlimit(100000)
N = int(raw_input())
act = [map(int, raw_input().split()) for _ in range(N)]
memo = [[-1]*3 for _ in range(N)]

def happy(n, i):
  if memo[n][i] >= 0:
    return memo[n][i]
  if n == 0:
    h = act[n][i]
  else:
    h = -1
    for j in range(3):
      if j == i:
        continue
      c = happy(n-1,j)+act[n][i]
      h = h if h > c else c
  memo[n][i] = h
  return h
print max(happy(N-1,0),happy(N-1,1),happy(N-1,2))

Solution (Python):
import sys
import numpy as np

N = int(sys.stdin.readline().strip())

a_list = [None for _ in range(N)]
b_list = [None for _ in range(N)]
c_list = [None for _ in range(N)]

for i in range(N):
    a, b, c = list(map(int, sys.stdin.readline().strip().split(" ")))
    a_list[i] = a
    b_list[i] = b
    c_list[i] = c
    
tmp = [a_list, b_list, c_list]
happy = [[0 for _ in range(3)] for __ in range(N)]

happy[0][0] = a_list[0]
happy[0][1] = b_list[0]
happy[0][2] = c_list[0]

for i in range(1, N):
    for j in range(3):
        
        max_h = 0
        for k in range(3):
            
            if k == j:
                continue
            
            
            max_h = max(max_h, happy[i-1][k] + tmp[j][i])
        happy[i][j] = max_h


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

"""

happy = [0 for _ in range(N)]
select = [None for _ in range(N)]

ind = np.argmax([a_list[0], b_list[0], c_list[0]])
select[0] = [0, 1, 2][ind]
happy[0] = [a_list[0], b_list[0], c_list[0]][ind]

if N == 1:
    print(happy[0])
    sys.exit()

ind = np.argmax([a_list[0] + b_list[1], a_list[0] + c_list[1], b_list[0] + a_list[1], b_list[0] + c_list[1], c_list[0] + a_list[1], c_list[0] + b_list[1]])
happy[1] = [a_list[0] + b_list[1], a_list[0] + c_list[1], b_list[0] + a_list[1], b_list[0] + c_list[1], c_list[0] + a_list[1], c_list[0] + b_list[1]][ind]
select[1] = [1, 2, 0, 2, 0, 1][ind]

if N == 2:
    print(happy[1])
    sys.exit()

for i in range(2, N):
    max_h = 0
    for j in range(3):
        for k in range(3):
            if k == j:
                continue
            if j == select[i-2]:
                continue
            if max_h < tmp[k][i] + tmp[j][i-1] + happy[i-2]:
                max_h = tmp[k][i] + tmp[j][i-1] + happy[i-2]
                select[i] = k
            
    happy[i] = max_h

print(happy[N-1])
"""

Solution (Python):
import sys
N = int(input())
x, y, z = 0, 0, 0
for i, e in enumerate(sys.stdin):
    a, b, c = map(int, e.split())
    nx = max(y, z) + a
    ny = max(x, z) + b
    nz = max(x, y) + c
    x, y, z = nx, ny, nz
print(max(x, y, z))

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

Solution (Python):
import sys
N = int(input())
A = [0] * N
B = [0] * N
C = [0] * N
for i, e in enumerate(sys.stdin):
    A[i], B[i], C[i] = map(int, e.split())
dp = [[0] * 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][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[N - 1]))

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

Solution (Python):
nb_days = int(input())
now_a, now_b, now_c = 0, 0, 0
for _ in range(nb_days):
    a, b, c = [int(x) for x in input().split()]
    next_a = a + max(now_b, now_c)
    next_b = b + max(now_a, now_c)
    next_c = c + max(now_a, now_b)
    now_a, now_b, now_c = next_a, next_b, next_c
print(max(next_a, next_b, next_c))

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

n = int(input())

lis_pnt = []

for _ in range(n):
	lis_pnt.append(in_list())

cost = []

for _ in range(n+1):
	cost.append([0,0,0])

for i in range(n):
	for bef in range(3):
		for aft in range(3):
			if bef != aft:
				cost[i+1][aft] = max(cost[i][bef]+lis_pnt[i][aft],cost[i+1][aft])
print(max(cost[n]))

Solution (Python):
import sys
raw_input = sys.stdin.readline
N = int(raw_input())
dp = [[0,0,0] for x in range(N+1)]
for i in range(N):
    li = map(int,raw_input().split())
    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]+li[k])
print max(dp[N])

Solution (Python):

import sys
input = sys.stdin.readline

def dp_happiness(N):
    today_a, today_b, today_c = 0, 0, 0
    for _ in range(N):
        a, b, c = map(int, input().split())

        tommorow_a = a + max(today_b, today_c)
        tommorow_b = b + max(today_c, today_a)
        tommorow_c = c + max(today_a, today_b)

        today_a = tommorow_a
        today_b = tommorow_b
        today_c = tommorow_c
    return max(tommorow_a, tommorow_b, tommorow_c)


N = int(input())
print(dp_happiness(N))

Solution (Python):

import sys
input = sys.stdin.readline

def dp_happiness(N):
    yesterday_a, yesterday_b, yesterday_c = 0, 0, 0
    for _ in range(N):
        a, b, c = map(int, input().split())

        today_a = a + max(yesterday_b, yesterday_c)
        today_b = b + max(yesterday_c, yesterday_a)
        today_c = c + max(yesterday_a, yesterday_b)

        yesterday_a = today_a
        yesterday_b = today_b
        yesterday_c = today_c
    return max(today_a, today_b, today_c)

N = int(input())
print(dp_happiness(N))

Solution (Python):




def dp_happiness(N):
    yesterday_a, yesterday_b, yesterday_c = 0, 0, 0
    for _ in range(N):
        a, b, c = map(int, input().split())

        today_a = a + max(yesterday_b, yesterday_c)
        today_b = b + max(yesterday_c, yesterday_a)
        today_c = c + max(yesterday_a, yesterday_b)

        yesterday_a = today_a
        yesterday_b = today_b
        yesterday_c = today_c
    return max(today_a, today_b, today_c)

N = int(input())
print(dp_happiness(N))

Solution (Python):
def main():
    N = int(input())
    prev = [0] * 3
    current = [0] * 3
    for _ in range(N):
        a, b, c = map(int, input().split())
        current[0] = a + max(prev[1], prev[2])
        current[1] = b + max(prev[0], prev[2])
        current[2] = c + max(prev[0], prev[1])
        prev = list(current)
    print(max(current))


if __name__ == "__main__":
    main()

Solution (Python):


import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


n = I()

dp = [[0] * (n + 1) for _ in range(3)]
for i in range(n):
    H = LI()
    for k in range(3):
        k1, k2 = (k + 1) % 3, (k + 2) % 3
        dp[k1][i + 1] = max(dp[k1][i + 1], dp[k][i] + H[k1])
        dp[k2][i + 1] = max(dp[k2][i + 1], dp[k][i] + H[k2])

print(max([dp[k][n] for k in range(3)]))

Solution (Python):
N = int(input())
a_list = [[0 for _ in range(3)] for _ in range(N)]

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

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

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

Solution (Python):
n=int(input())
k=3
l=[]
for _ in range(n):
    l.append(list(map(int,input().split())))
dp=[l[0]]
for i,s in enumerate(l):
    if not i:continue
    t=[t for t in dp[-1]]
    d=[]
    for i in range(k):
        d.append(max(t[j]for j in range(k)if i!=j)+s[i])
    dp.append(d)
print(max(dp[-1]))

Solution (Python):
n=int(input())
a,b,c=[],[],[]
for _ in range(n):
    t=map(int,input().split())
    a.append(t.__next__())
    b.append(t.__next__())
    c.append(t.__next__())
dpA,dpB,dpC=[a[0]],[b[0]],[c[0]]
for i,(A,B,C)in enumerate(zip(a,b,c)):
    if not i:continue
    ta,tb,tc=dpA[-1],dpB[-1],dpC[-1]
    dpA.append(max(tb,tc)+A)
    dpB.append(max(tc,ta)+B)
    dpC.append(max(ta,tb)+C)
print(max(dpA[-1],dpB[-1],dpC[-1]))

Solution (Python):
n = int(input())
a,b,c = [],[],[]
for i in range(n):
    tmp = list(int(i) for i in input().split())
    a.append(tmp[0])
    b.append(tmp[1])
    c.append(tmp[2])

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

Solution (Python):
import itertools

n = int(input())
happiness = [list(map(int, input().split())) for _ in range(n)]
dp = [[0, 0, 0] for _ in range(n + 1)] 

tpls = tuple((i, j) for i, j in itertools.product(range(3), repeat=2) if i != j)
for x in range(n):
    for i, j in tpls:
        dp[x + 1][j] = max(dp[x + 1][j], dp[x][i] + happiness[x][i])

print(max(dp[n]))

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

a,b,c = 0,0,0

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

print(max(a,b,c))

Solution (Python):
n=int(input())
best=[int(s) for s in input().split()]
for i in range(n-1):
  a,b,c=map(int,input().split())
  aa=max(best[1]+a,best[2]+a)
  bb=max(best[0]+b,best[2]+b)
  cc=max(best[0]+c,best[1]+c)
  best=[aa,bb,cc]
print(max(best))

Solution (Python):
from itertools import combinations

N=int(input())

activity = []

for i in range(N):
    activity.append(list(map(int,input().split())))

h = [0]*3

for i in range(N):
    if i==0:
        for j in range(3):
            h[j]=activity[0][j]
    else:
        tmp=[0]*3
        for j in range(3):
            tmp[j]=activity[i][j]+max([h[k] for k in range(3) if k!=j])
        for j in range(3):
            h[j]=tmp[j]

print(max(h))

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

abc = [(0, 0, 0)]
for i in range(N):
    a, b, c = [int(x) for x in input().split()]
    abc.append((a, b, c))

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

for i in range(1, N + 1):
    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[N][0], dp[N][1], dp[N][2]))

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

dpA=[0]*N
dpB=[0]*N
dpC=[0]*N

dpA[0]=H[0][0]
dpB[0]=H[0][1]
dpC[0]=H[0][2]

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

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

Solution (Python):
import sys
readline = sys.stdin.readline
n = int(input())
dp = list(list(map(int, readline().split())) for _ in range(n))
for i in range(1, n):
    dp[i][0] += max(dp[i - 1][1], dp[i - 1][2]);
    dp[i][1] += max(dp[i - 1][2], dp[i - 1][0]);
    dp[i][2] += max(dp[i - 1][0], dp[i - 1][1]);
print(max(dp[n - 1]))

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

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

dpA = [0 for _ in range(N)]
dpB = [0 for _ in range(N)]
dpC = [0 for _ in range(N)]

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

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

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

dpA = [0 for _ in range(N)]
dpB = [0 for _ in range(N)]
dpC = [0 for _ in range(N)]

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

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

Solution (Python):
import sys
N = int(sys.stdin.readline())
a = []
b = []
c = []
for i in range(N):
    tmpa, tmpb, tmpc = map(int, sys.stdin.readline().split())
    a.append(tmpa)
    b.append(tmpb)
    c.append(tmpc)

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

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

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

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

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


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

act = None
for i in range(N):
    a, b, c = happy[i]
    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[-1]))

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

dp_a = [0]*n
dp_b = [0]*n
dp_c = [0]*n

dp_a[0] = A[0]
dp_b[0] = B[0]
dp_c[0] = C[0]

for i in range(1, n):
    dp_a[i] = max(dp_b[i-1], dp_c[i-1]) + A[i]
    dp_b[i] = max(dp_a[i-1], dp_c[i-1]) + B[i]
    dp_c[i] = max(dp_b[i-1], dp_a[i-1]) + C[i]

print(max(dp_a[-1], dp_b[-1], dp_c[-1]))

Solution (Python):
n = int(input())
A = [[int(i) for i in input().split()] for i in range(n)]
dp = [0, 0, 0]

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

Solution (Python):
import copy

def main():
	n = int(input())
	a = []
	for _ in range(0, n):
		x = [int(x) for x in input().split()]
		a.append(x)
	
	cur = a[0]
	nxt = [0] * 3

	for i in range(1, len(a)):
		nxt[0] = max(a[i][0] + cur[1], a[i][0] + cur[2])
		nxt[1] = max(a[i][1] + cur[0], a[i][1] + cur[2])
		nxt[2] = max(a[i][2] + cur[1], a[i][2] + cur[0])

		cur = copy.deepcopy(nxt)

	print(max(cur[0], cur[1], cur[2]))

if __name__ == "__main__":
	main()

Solution (Python):
import sys
N=input()
A=[ map(int, sys.stdin.readline().split()) for i in range(N) ]

if N==1:
	print max( A[-1] )
	quit()

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


a,b,c=A[0][0],A[0][1],A[0][2]

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



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

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

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

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

print  max( dp[-1] )

Solution (Python):
N = int(input())
a_list = []
b_list = []
c_list = []
a_append = a_list.append
b_append = b_list.append
c_append = c_list.append
for i in range(N):
    a, b, c = map(int, input().split())
    a_append(a)
    b_append(b)
    c_append(c)

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

for i in range(1, N + 1):

    if i == 1:
        dp[i][0] = a_list[i - 1]
        dp[i][1] = b_list[i - 1]
        dp[i][2] = c_list[i - 1]
    else:
        dp[i][0] = max(dp[i][0], dp[i - 1][1] + a_list[i - 1])
        dp[i][0] = max(dp[i][0], dp[i - 1][2] + a_list[i - 1])
        dp[i][1] = max(dp[i][1], dp[i - 1][0] + b_list[i - 1])
        dp[i][1] = max(dp[i][1], dp[i - 1][2] + b_list[i - 1])
        dp[i][2] = max(dp[i][2], dp[i - 1][0] + c_list[i - 1])
        dp[i][2] = max(dp[i][2], dp[i - 1][1] + c_list[i - 1])

print(max(dp[N]))

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

Solution (Python):

from sys import stdin

s_in = lambda: stdin.readline()[:-1]  
d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  


N = d_in()

happiness = [0] * 3
for _ in range(N):
    today = ds_in()
    pre = happiness.copy()
    happiness[0] = max(pre[1], pre[2]) + today[0]
    happiness[1] = max(pre[0], pre[2]) + today[1]
    happiness[2] = max(pre[1], pre[0]) + today[2]

print(max(happiness))

Solution (Python):
N=int(raw_input())
A=[]
for i in range(N):
    A.append([int(x) for x in raw_input().split()])
C=[[0,0,0] for x in range(N)]
C[0]=[A[0][0],A[0][1],A[0][2]]
for i in range(1,N):
    for j in range(3):
        C[i][j]=A[i][j] + max([ C[i-1][k] for k in range(3) if k != j])
print max(C[-1])