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())
data_ls = list()
memo_ls = [{} for i in range(N)]
for i in range(N):
    data_ls.append([int(i) for i in input().split()])
def dfs(ind, last, cnt):
    if ind == N:
        memo_ls[ind][last] = cnt
        return cnt
    if memo_ls[ind].get(last) is not None:
        return memo_ls[ind][last]
    for i in range(3):
        if i != last:
            res = max(cnt,
                      dfs(ind+1, i, cnt + data_ls[ind][i]))
    memo_ls[ind][i] = res
    return res

for i in range(3):
    memo_ls[-1][i] = data_ls[-1][i]
for ind in range(N-2,-1,-1):
    for i in range(3):
        memo_ls[ind][i] = data_ls[ind][i] + max([memo_ls[ind+1][k] for k in range(3) if i != k])
print(max(memo_ls[0].values()))

Solution (Python):
n = int(input())
a = []
b = []
c = []
dp = []
for i in range(n):
    dp.append([0, 0, 0])
for i in range(n):
    a_i, b_i, c_i = [int(i) for i in input().split(' ')]
    a.append(a_i)
    b.append(b_i)
    c.append(c_i)

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

print(max(dp[-1]))

Solution (Python):

import sys

def main():
	N = int(input())
	plan = []
	for _ in range(N):
		a, b, c = map(int, input().split(" "))
		plan.append((a, b, c))
		
	DP = [[-1 for _ in range(3)] for _ in range(N)]
	a, b, c = plan[0]
	DP[0][0] = a
	DP[0][1] = b
	DP[0][2] = c
	
	for i in range(1, len(plan)):
		a, b, c = plan[i]
		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]))
		
if __name__ == "__main__":
	main()

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

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

print(max(dp[-1]))

Solution (Python):
def main():
    N = int(input())
    dp = [[0, 0, 0] for i in range(N)]
    a0, b0, c0 = [int(n) for n in input().split()]
    dp[0] = [a0, b0, c0]
    for i in range(1, N):
        li = [int(n) for n in input().split()]
        for t in range(3):
            dp[i][t] = max(dp[i-1][(t+1)%3], dp[i-1][(t+2)%3]) + li[t]
    print(max(dp[N-1]))

if __name__ == "__main__":
    main()

Solution (Python):


import math
import os
import random
import re
import sys



if __name__ == '__main__':
    n = int(input())
    h = []
    for _ in range(n):
        h.append(list(map(int, input().split())))

    dp = []
    for _ in range(n):
        dp.append([])
        for _ in range(3):
            dp[-1].append(0)

    for i in range(n):
        for j in range(3):
            for k in range(3):
                if k != j:
                    dp[i][j] = max((dp[i - 1][k] if i - 1 >= 0 else 0) + h[i][j], dp[i][j])

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

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

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

a = [0]*(N+1)
b = [0]*(N+1)
c = [0]*(N+1)

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

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

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

print(max(dp[N]))

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])

def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])


def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    C()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007


def A():
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return


def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return


def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


def I():
    return 























if __name__ == '__main__':
    C()

Solution (Python):
'''input
3
10 40 70
20 50 80
30 60 90
'''
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]=arr[i-1][0]+max(dp[i-1][1],dp[i-1][2])
	dp[i][1]=arr[i-1][1]+max(dp[i-1][2],dp[i-1][0])
	dp[i][2]=arr[i-1][2]+max(dp[i-1][1],dp[i-1][0])
print(max(dp[n]))

Solution (Python):


import sys


n = int(input())
abc = [[0 for j in range(3)] for i in range(n)]
for i in range(n):
  abc[i] = list(map(int, sys.stdin.readline().rstrip().split()))


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

Solution (Python):


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

dp = []
for i in range(N):
    dp.append([- float('inf')] * 3)

dp[0] = [a[0], b[0], 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[N - 1]))

Solution (Python):


def c_vacation(n):
    dp=[[0 for i in xrange(3)] for j in xrange(n)]
    dp[0][0],dp[0][1],dp[0][2]=map(int,raw_input().split())
    for i in xrange(1,n):
        a,b,c=map(int,raw_input().split())
        dp[i][0]=max(a+dp[i-1][1],a+dp[i-1][2])
        dp[i][1]=max(b+dp[i-1][0],b+dp[i-1][2])
        dp[i][2]=max(c+dp[i-1][0],c+dp[i-1][1])
    print max(dp[-1])
n=int(input())
c_vacation(n)

Solution (Python):

N = int(input())




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


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


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

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

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

print(max(dp[N]))

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

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

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

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

Solution (Python):
n=int(input())
a=[[0,0,0]for i in range(n+1)]
for i in range(n):
    s,t,u=map(int,input().split())
    a[i+1][0]=max(a[i][1]+s,a[i][2]+s)
    a[i+1][1]=max(a[i][0]+t,a[i][2]+t)
    a[i+1][2]=max(a[i][1]+u,a[i][0]+u)
print(max(a[n]))

Solution (Python):
n = int(input())
memo =[[0,0,0] for _ in range(n)]
days = []
for i in range(n):
    days.append(list(map(int, input().split())))
memo[-1] = days[-1]


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

Solution (Python):
import sys
input = sys.stdin.readline
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 = [a[0]]+[0]*(n-1)
dpb = [b[0]]+[0]*(n-1)
dpc = [c[0]]+[0]*(n-1)
for i in range(1,n):
    dpa[i] = max(dpb[i-1],dpc[i-1]) + a[i]
    dpb[i] = max(dpc[i-1],dpa[i-1]) + b[i]
    dpc[i] = max(dpa[i-1],dpb[i-1]) + c[i]
print(max(dpa[-1],dpb[-1],dpc[-1]))

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

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

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

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

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

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

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

n = int(input())

abc = [[int(i) for i in input().split()] for j in range(n)]

def happy(n, abc):
    da, db, dc = 0, 0, 0
    for a, b, c in abc:
        na = max(db, dc) + a
        nb = max(dc, da) + b
        nc = max(da, db) + c
        da, db, dc = na, nb, nc

    return max(da, db, dc)

print(happy(n, abc))

Solution (Python):

n = int(input())

a = [[int(i) for i in input().split()] for j in range(n)]

def happy(n, a):
    d = [[0] * 3 for j in range(n)]
    for i in range(3):
        d[0][i] = a[0][i]

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

    return max(d[n - 1])

print(happy(n, a))

Solution (Python):


import sys
input = sys.stdin.readline

def f(n, abc):
    la, lb, lc = 0, 0, 0
    for a, b, c in abc:
        na, nb, nc = max(lb + a, lc + a), \
            max(la + b, lc + b), max(la + c, lb + c)
        la, lb, lc = na, nb, nc
    return(max(la, lb, lc))

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

print(f(n, abc))

Solution (Python):

import sys
input = sys.stdin.readline

def f(n, abc):
    dp = [0] * 3
    for a, b, c in abc:
        dp = [ max(dp[1] + a, dp[2] + a), \
               max(dp[0] + b, dp[2] + b), \
               max(dp[0] + c, dp[1] + c) ]
    return(max(dp))

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

print(f(n, abc))

Solution (Python):

import sys
input = sys.stdin.readline

def f(n, abc):
    dp = [0] * 3
    for i in range(n):
        a, b, c = abc[i]
        dp0, dp1, dp2 = dp
        dp = [ max(dp1 + a, dp2 + a), \
               max(dp0 + b, dp2 + b), \
               max(dp0 + c, dp1 + c) ]
    return(max(dp))

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

print(f(n, abc))

Solution (Python):

import sys
input = sys.stdin.readline

def f(n, abc):
    dp = [0] * 3
    for i in range(1, n + 1):
        a, b, c = abc[i - 1]
        dp = [ max(dp[1] + a, dp[2] + a), \
               max(dp[0] + b, dp[2] + b), \
               max(dp[0] + c, dp[1] + c) ]
    return(max(dp))

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

print(f(n, abc))

Solution (Python):


import sys
input = sys.stdin.readline

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

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

print(f(n, abc))

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

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] =  [int(x) for x in input().split()]
dp = [[0 for _ in range(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][1]+C[i],dp[i-1][0]+C[i])
print(max(dp[-1][0],dp[-1][1],dp[-1][2]))

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

for i in range(n):
    cur = [int(i) for i in input().split()]
    joy.append(cur)

dp = [[0 for i in range(n+5)] for j in range(3)]
import sys
sys.setrecursionlimit(10000000)
def brute(curday, prvmove):
    if curday>=n:
        return 0
    if dp[prvmove][curday]!=0:
        return dp[prvmove][curday]
    ans = 0
    
    for i in range(3):
        if prvmove == i:
            continue
        ans = max(ans, brute(curday+1, i) + joy[curday][i])

    
    
    dp[prvmove][curday] = ans
    return ans

ans = 0

for i in range(3):
    ans = max(ans, brute(0, i))
print(ans)

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

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

Solution (Python):
import pdb


def solve(a,n):
    if n==1:
        return max(a[0])
    dp = [[0,0,0] for i in xrange(n)]
    dp[0]= [a[0][0],a[1][0],a[2][0]]
    for i in xrange(1,n):
        try:
            dp[i][0] = a[0][i]+max(dp[i-1][1],dp[i-1][2])
            dp[i][1] = a[1][i]+max(dp[i-1][0],dp[i-1][2])
            dp[i][2] = a[2][i]+max(dp[i-1][0],dp[i-1][1])
        except:
            pdb.set_trace()
    return max(dp[n-1])

        
    

if __name__=='__main__':
    n = int(raw_input())
    
    a = [[],[],[]]
    for i in xrange(n):
        ai,bi,ci = map(int,raw_input().split())
        a[0].append(ai)
        a[1].append(bi)
        a[2].append(ci)
    print solve(a,n)

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

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

dp = [ [0,0,0] for _ in range(N) ]
dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]

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

print(max(dp[-1]))

Solution (Python):
N = int(input())
a = [[0]*N for i in range(3)]
for i in range(N):
    bin = [int(i) for i in input().split()]
    for j in range(3):
        a[j][i] = bin[j]

dp = [[0]*(N+1) for i in range(3)]
for i in range(3):
    dp[i][1] = a[i][0]
ls = [0, 1, 2]

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

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

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

dp[0] = [t[0][0], t[0][1], t[0][2]]

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

print(max(dp[-1]))

Solution (Python):


"""
Created on 2019/3/2
Solved on 2019/3/
@author: shinjisu
"""




import numpy as np


def getInt(): return int(input())



def getIntList(): return np.array(input().split(), dtype='int')



def zeros(n): return np.zeros(n, dtype='int')


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**12


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def prob_A():  
    N = getInt()
    H = getIntList()
    dmp((N, H), 'N, H')
    c = zeros(N)
    c[1] = abs(H[1]-H[0])
    for i in range(2, N):
        c[i] = min(c[i-1] + abs(H[i]-H[i-1]),
                   c[i-2] + abs(H[i]-H[i-2]))
    dmp(c, 'c')
    return c[N-1]


def prob_B_TLE():  
    N, K = getIntList()
    H = getIntList()
    dmp((N, K, H), 'N, K, H')
    c = np.zeros(N)
    c[0] = 0
    for i in range(1, N):
        
        for j in range(max(0, i-K), i):
            c[i] = min(c[i], c[j] + abs(H[i]-H[j]))
    dmp(c, 'c')
    return c[N-1]


def prob_B():  
    N, K = getIntList()
    H = np.array(input().split(), dtype='int')
    dmp((N, K, H), 'N, K, H')
    c = np.zeros(N, dtype='int')
    c[0] = 0
    for i in range(1, N):
        c[i] = np.min(c[max(0, i-K):i] + np.abs(H[max(0, i-K):i] - H[i]))
    dmp(c, 'c')
    return c[N-1]


def prob_C():  
    N = getInt()
    a = zeros(N)
    b = zeros(N)
    c = zeros(N)
    for i in range(N):
        a[i], b[i], c[i] = getIntList()
    dmp(N, 'N')
    dmp(a, 'a')
    dmp(b, 'b')
    dmp(c, 'c')
    dpa = zeros(N)
    dpb = zeros(N)
    dpc = zeros(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], dpc[i-1]) + a[i]
        dpb[i] += max(dpc[i-1], dpa[i-1]) + b[i]
        dpc[i] += max(dpa[i-1], dpb[i-1]) + c[i]
    dmp(dpa, 'dpa')
    dmp(dpb, 'dpb')
    dmp(dpc, 'dpc')
    return max(dpa[N-1], dpb[N-1], dpc[N-1])


debug = False  
ans = prob_C()
print(ans)

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

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

dp = [[0] * n for _ in range(3)]
dp[0][-1], dp[1][-1], dp[2][-1] = a[-1], b[-1], c[-1]

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

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

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

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

dp = [[0] * 3 for _ in range(n)]
dp[-1] = [a[-1], b[-1], c[-1]]

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

print(max(dp[0]))

Solution (Python):

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


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

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

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

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

Solution (Python):
n = int(input())
A = [0]*n
B = [0]*n
C = [0]*n

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

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

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

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

for i, happinesses in enumerate(happinesses_each_day):
    for j, happiness in enumerate(happinesses):
        for k in range(3):
            if j == k:
                continue
            if dp[i + 1][k] < (dp[i][j] + happiness):
                dp[i + 1][k] = (dp[i][j] + happiness)

print(max(dp[N]))

Solution (Python):
n=int(input())
A,B,C=0,0,0

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

print(max(A,B,C))

Solution (Python):
N = int(input())
L = []
for i in range(N):
  L.append(list(map(int,input().split())))
dp_a = [L[0][0]]
dp_b = [L[0][1]]
dp_c = [L[0][2]]
for i in range(N-1):
  dp_a.append(max(dp_b[i]+L[i+1][0],dp_c[i]+L[i+1][0]))
  dp_b.append(max(dp_a[i]+L[i+1][1],dp_c[i]+L[i+1][1]))
  dp_c.append(max(dp_a[i]+L[i+1][2],dp_b[i]+L[i+1][2]))
print(max(dp_a[N-1],dp_b[N-1],dp_c[N-1]))

Solution (Python):
n = int(input())
x, y, z = 0, 0, 0

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

Solution (Python):
N=int(input())
H=[[int(x) for x in input().split()] for y in range(N)]

dp=[[0,0,0] 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(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[-1]))

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

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

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

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

for idx, val in enumerate(lis[1:], start=1):
	a = val[0] + max([dp[idx-1][i] for i in range(3) if 0 != i ])
	b = val[1] + max([dp[idx-1][i] for i in range(3) if 1 != i ])
	c = val[2] + max([dp[idx-1][i] for i in range(3) if 2 != i ])
	dp[idx] = [a,b,c]
print(max(dp[-1]))

Solution (Python):
from sys import stdin
n=int(stdin.readline())
dp=[0]*3
for i in range(n):
    before=[0,0,0]
    l=list(map(int,stdin.readline().split()))
    for i in range(3):
        before[i]=max(dp[(i+1)%3],dp[(i+2)%3])+l[i]
    dp=before
print(max(dp))

Solution (Python):
def solve(actions, n):
    
    dp = [[0] * 4 for _ in range(n + 1)]

    for day, action in enumerate(actions, 1):
        action1, action2, action3 = action[0], action[1], action[2]
        for key in range(1, 4):
            if key == 1:
                dp[day][key] = action1 + max(dp[day - 1][2], dp[day - 1][3])
            elif key == 2:
                dp[day][key] = action2 + max(dp[day - 1][1], dp[day - 1][3])
            else:
                dp[day][key] = action3 + max(dp[day - 1][1], dp[day - 1][2])

    return max(dp[n])


def main():
    n = int(input())
    actions = []

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

    ans = solve(actions, n)
    print(ans)


main()

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]
aa = [0]*(n+1)
bb = [0]*(n+1)
cc = [0]*(n+1)
for i in range(1,n+1):
  I = i-1
  front = abc[I]
  aa[i] = front[0] + max([bb[I],cc[I]])
  bb[i] = front[1] + max([aa[I],cc[I]])
  cc[i] = front[2] + max([bb[I],aa[I]])
print(max([aa[n],bb[n],cc[n]]))

Solution (Python):

n=int(input())

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

Solution (Python):
def solve(abc):
    dp1 = [0, 0, 0]
    dp2 = [0, 0, 0]
    for i in abc:
        for j in range(3):
            for k in range(3):
                if j == k:
                    continue
                dp2[j] = max(dp2[j], dp1[k] + i[j])
        for j in range(3):
            dp1[j] = dp2[j]
    return max(dp2)

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

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

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


dp = [None] * n


dp[0] = [0, 0, 0]
dp[0][0] = data[0][0]
dp[0][1] = data[0][1]
dp[0][2] = data[0][2]

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

mx = max(dp[n - 1])

print(mx)

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 for _ in range(N)] for i in range(3) ]
flag = ""

dp[0][0] = A[0]
dp[1][0] = B[0]
dp[2][0] = C[0]

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

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