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







if __name__ == "__main__":
    n = int(input())
    x = range(n)
    dp = [ [0,0,0] for i in x]
    d = []
    for i in x:
        d.append(tuple(map(int,input().split())))

    dp[0][0] = max(d[0][1],d[0][2])
    dp[0][1] = max(d[0][0],d[0][2])
    dp[0][2] = max(d[0][1],d[0][0])

    for i in x:
        if i == 0:
            continue
        
        dp[i][0] = max(dp[i-1][1] + d[i][1] , dp[i-1][2] + d[i][2])
        dp[i][1] = max(dp[i-1][0] + d[i][0] , dp[i-1][2] + d[i][2])
        dp[i][2] = max(dp[i-1][1] + d[i][1] , dp[i-1][0] + d[i][0])
    print(max(dp[n-1]))

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

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

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

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

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

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

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

Solution (Python):
import sys
n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for i in range(n)]

dp = [[-1] * 3 for i in range(n)]

dp[0][0] = arr[0][0]
dp[0][1] = arr[0][1]
dp[0][2] = arr[0][2]

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

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

Solution (Python):
n = int(input())
ha, hb, hc = 0, 0, 0
for _ in range(n):
    a, b, c = map(int, input().split())
    ha, hb, hc = max(hb, hc) + a, max(hc, ha) + b, max(ha, hb) + c
print(max(ha, hb, hc))

Solution (Python):

"""
問題
https://atcoder.jp/contests/dp/tasks/dp_c

解説
https://qiita.com/drken/items/dc53c683d6de8aeacf5a
"""
def solve():
    N = int(input())
    A, B, C = [0], [0], [0]
    for i in range(N):
        a, b, c = list(map(int, input().split()))
        A.append(a)
        B.append(b)
        C.append(c)
    
    
    
    dp = [[j for j in range(3)] for i in range(N+1)]
    dp[0][0] = 0
    dp[0][1] = 0
    dp[0][2] = 0

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



if __name__ == "__main__":
    solve()

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

for i in range(1,N+1):
  ai,bi,ci = map(int,input().split())
  
  dp[i][0] = ai + max(dp[i-1][1],dp[i-1][2])
  dp[i][1] = bi + max(dp[i-1][0],dp[i-1][2])
  dp[i][2] = ci + max(dp[i-1][1],dp[i-1][0])
  
print(max(dp[N]))

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

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

Solution (Python):
N=int(input())
l=list(list(map(int,input().split())) for i in range(N))
dp=[[0]*3 for _ in range(N)]
for i,I in enumerate(l):
    if i==0:
        dp[0]=l[0]
    else:
        for k in range(3):
            dp[i][k]=max(dp[i-1][j]+l[i][k]  if j!=k else 0 for j in range(3))
print(max(dp[N-1]))

Solution (Python):
N = int(input())
H = []
for _ in range(N):
    H.append(list(map(int, input().split())))
dp = [[0, 0, 0] for _ in range(N)]
dp[0] = H[0]
for i,h in enumerate(H[1:], start=1):
    dp[i][0] = h[0]+max(dp[i-1][1], dp[i-1][2])
    dp[i][1] = h[1]+max(dp[i-1][0], dp[i-1][2])
    dp[i][2] = h[2]+max(dp[i-1][0], dp[i-1][1])
print(max(dp[-1]))

Solution (Python):



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

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

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

print(max(dp[n]))

Solution (Python):



N = int(input())

dp = [ [0] * (N+1), [0] * (N+1), [0] * (N+1) ]

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


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

Solution (Python):
n = int(input())
set_abc = {"a", "b", "c"}
abc_array = [{key: int(value) for key, value in zip(set_abc, input().split())} for y in range(n)]


dp = [{key: 0 for key in set_abc} for x in range(n)]
res = 0
for index in range(n):
    if index == 0:
        dp[index] = abc_array[index]
        continue
    for key, value in abc_array[index].items():
        candidate_key = set_abc - set(key)
        dp[index][key] = max(dp[index - 1][candidate_key.pop()] + value, dp[index - 1][candidate_key.pop()] + value)

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

Solution (Python):
N = int(input())
prev = [0,0,0]
now = [0,0,0]
for i in range(N):
    acts = list(map(int,input().split()))
    for pi in range(3):
        for ni in range(3):
            if pi == ni:
                continue
            now[ni] = max(now[ni], prev[pi]+acts[ni])
    prev = now.copy()
print(max(now))

Solution (Python):
n = int(input())
set_abc = {"a", "b", "c"}
abc_array = [{key: int(value) for key, value in zip(set_abc, input().split())} for y in range(n)]


dp = [{key: 0 for key in set_abc} for x in range(n)]
res = 0
for index in range(n):
    if index == 0:
        dp[index] = abc_array[index]
        continue
    for key, value in abc_array[index].items():
        candidate_key = set_abc - set(key)
        dp[index][key] = max(dp[index - 1][candidate_key.pop()] + value, dp[index - 1][candidate_key.pop()] + value)

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

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

cost = [a,b,c]
dp = [[0] * N, [0] * N, [0] * N]

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

dp[0][0] = cost[0][0]
dp[1][0] = cost[1][0]
dp[2][0] = cost[2][0]

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

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

Solution (Python):
INF = float("inf")

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,input_func:[input_func() for _ in range(n)]

import importlib
import_module = lambda module_name:importlib.import_module(module_name)

init_array_1dim = lambda value,n:[value]*n 
init_array_2dim = lambda value,n,m:[init_array_1dim(value,n) for _ in range(m)] 

gcd_base = lambda value1,value2:import_module('fractions').gcd(value1,value2) 
gcd = lambda lst:import_module('functools').reduce(gcd_base,lst) 
lcm_base = lambda value1,value2:(value1*value2)//gcd_base(value1,value2) 
lcm = lambda lst:import_module('functools').reduce(lcm_base,lst,1) 

permutations = lambda lst,n:import_module('itertools').permutations(lst,n) 
combinations = lambda lst,n:import_module('itertools').combinations(lst,n) 
product = lambda lst1,lst2:import_module('itertools').product(lst1,lst2) 

round = lambda value:round(value) 
ceil = lambda value:import_module('math').ceil(value) 
floor = lambda value:import_module('math').floor(value) 


init_q = lambda lst: import_module('collections').deque(lst)
q_pop = lambda q: q.popleft() 
q_push = lambda q,value:q.appendleft(value) 
q_pushlist = lambda q,lst:q.extendleft(lst) 
q_append = lambda q,value:q.append(value) 
q_appendlist = lambda q,lst:q.extend(lst) 


init_heap = lambda a:import_module('heapq').heapify(a)
heap_push = lambda a,v:import_module('heapq').heappush(a,v)
heap_pop = lambda a:import_module('heapq').heappop(a) 

def solution():
    
    N = input_int()
    abc = input_lines(N,input_ints_list)

    dp = init_array_2dim(-1,3,N)
    for i in range(N):
        if i == 0:
            dp[i][0] = abc[0][0]
            dp[i][1] = abc[0][1]
            dp[i][2] = abc[0][2]
        else:
            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-1]))
    
if __name__ == '__main__':
    solution()

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

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

Solution (Python):
n = int(input())
hya, hyb, hyc = 0, 0, 0
for _ in range(n):
    a, b, c = map(int, input().split())
    ha = a + max(hyb, hyc)
    hb = b + max(hyc, hya)
    hc = c + max(hya, hyb)
    hya =ha
    hyb =hb
    hyc =hc
print(max(ha, hb, hc))

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

Solution (Python):

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

dp = [{'a': None, 'b': None, 'c': None} for _ in range(N+1)]
dp[0]['a'] = 0
dp[0]['b'] = 0
dp[0]['c'] = 0

for i in range(1, N+1):
    dp[i]['a'] = max(dp[i-1]['b'] + A[i-1], dp[i-1]['c'] + A[i-1])
    dp[i]['b'] = max(dp[i-1]['c'] + B[i-1], dp[i-1]['a'] + B[i-1])
    dp[i]['c'] = max(dp[i-1]['a'] + C[i-1], dp[i-1]['b'] + C[i-1])

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

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


def main():
    N = int(input())
    a = [None] * N
    b = [None] * N
    c = [None] * N
    for i in range(N):
        a[i], b[i], c[i] = [Node(int(ele)) for ele in input().split()]

    a[0].dp_val = a[0].val
    b[0].dp_val = b[0].val
    c[0].dp_val = c[0].val

    for i in range(N-1):
        j = i + 1
        a[j].dp_val = max(b[i].dp_val, c[i].dp_val) + a[j].val
        b[j].dp_val = max(a[i].dp_val, c[i].dp_val) + b[j].val
        c[j].dp_val = max(a[i].dp_val, b[i].dp_val) + c[j].val

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


class Node():

    def __init__(self, val):
        self.val = val
        self.dp_val = -1


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
import sys

input = sys.stdin.readline

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

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

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

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

Solution (Python):
n = int(input())
a0, b0, c0 = map(int, input().split())
dp = [[0] * 3 for _ in range(n)]

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

Solution (Python):

def main():
    num = int(input())
    dp = [[0, 0, 0] for i in range(num)]
    dp[0] = list(map(int, input().split()))

    for i in range(1, num):
        data = 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]) + data[j]

    print(max(dp[-1]))


if __name__ == '__main__':
    main()

Solution (Python):
dp = [[0] * 3 for i in range(100010)]

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

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

print(max(dp[N]))

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

dp = [[0 for i in range(3)] for j in range(n+1)]
for i in range(3):
    dp[0][i] = li[0][i]

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

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

Solution (Python):
n = int(input())
p = [[int(_) for _ in input().split()] for __ in range(n)]
aem = [p[0][0]]; bem = [p[0][1]]; cem = [p[0][2]]
for i in range(1,n):
    atmp = p[i][0] + max(bem[-1], cem[-1])
    btmp = p[i][1] + max(aem[-1], cem[-1])
    ctmp = p[i][2] + max(aem[-1], bem[-1])
    aem.append(atmp); bem.append(btmp); cem.append(ctmp)
print(max(aem[-1], bem[-1], cem[-1]))

Solution (Python):

N = int(input())
dp = [[0] * 3 for _ in range(N)]
for i in range(N):

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

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

Solution (Python):
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
dp = [[0, 0, 0] for _ 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())
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+1)
dpb = [0] * (N+1)
dpc = [0] * (N+1)

for i in range(1, N+1):
    dpa[i] = max(dpb[i-1], dpc[i-1]) + A[i-1]
    dpb[i] = max(dpc[i-1], dpa[i-1]) + B[i-1]
    dpc[i] = max(dpa[i-1], dpb[i-1]) + C[i-1]

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

Solution (Python):



N = int(input())

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

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

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

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

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

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

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

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

li_action = list()

for _ in range(n):
    li_action.append(list(map(int, input().split())))

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


dp[0][0] = li_action[0][0]
dp[0][1] = li_action[0][1]
dp[0][2] = li_action[0][2]


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

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

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

dp = [[-1]*3 for i in range(N)]
import sys
sys.setrecursionlimit(10**9)
def dfs(i,j):
    if i == N:
        return 0
    if dp[i][j] != -1:
        return dp[i][j]
    else:
        if j==0:
            dp[i][j] = max(dfs(i+1,1)+abc[i][1], dfs(i+1,2)+abc[i][2])
        elif j==1:
            dp[i][j] = max(dfs(i+1,0)+abc[i][0], dfs(i+1,2)+abc[i][2])
        else:
            dp[i][j] = max(dfs(i+1,0)+abc[i][0], dfs(i+1,1)+abc[i][1])
        return dp[i][j]
print(max(dfs(0,0), dfs(0,1), dfs(0,2)))

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

dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0] = [vs[0][0], vs[0][1], vs[0][2]]

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

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

Solution (Python):
n=int(input())
dp=[[0for _ in range(3)]for _ in range(n)]
for i in range(n):
  a,b,c=map(int,input().split())
  if i==0:dp[i]=[a,b,c]
  else:
    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):
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N = int(stdin.readline().rstrip())
abc = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]


dp = [[-INF] * 3 for _ in range(N+10)]

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

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

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

Solution (Python):
from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N = int(stdin.readline().rstrip())
abc = [list(map(int, stdin.readline().rstrip().split())) for _ in range(N)]

abc = abc + [[-INF, -INF, -INF]]


dp = [[-INF] * 3 for _ in range(N+10)]

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

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

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

Solution (Python):
N = int(input())
hs =[list(map(int, input().split())) for i in range(N)]
a = []
b = []
c = []
for i, j, k in hs:
    a.append(i)
    b.append(j)
    c.append(k)
adp = [a[0]] + [0]*(N-1)
bdp =[b[0]] + [0]*(N-1)
cdp = [c[0]] + [0]*(N-1)
for i in range (1, N):
    adp[i] = max(bdp[i-1] + a[i], cdp[i-1]+a[i])
    bdp[i] = max(adp[i-1] + b[i], cdp[i-1]+b[i])
    cdp[i] = max(bdp[i-1] + c[i], adp[i-1]+c[i])
print(max(adp[N-1], bdp[N-1], cdp[N-1]))

Solution (Python):

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


N = int(input())

A = []
B = []
C = []
dp = [[0,0,0]]
INF = 0

for i in range(0,N):
    a,b,c = map(int,input().split(" "))
    A.append(a)
    B.append(b)
    C.append(c)
    dp.append([INF,INF,INF])

ABC = [A,B,C]


for i in range(0,N):
    for r in range(0,3):
        ls = [0,1,2]
        ls.remove(r)
        f1 = ls[0]
        f2 = ls[1]

        dp[i][r] = max(dp[i-1][f1],dp[i-1][f2]) + ABC[r][i]
    

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

Solution (Python):



def solve(N, abc):
    """
    >>> solve(3, [(10, 40, 70), (20, 50, 80), (30, 60, 90)])
    210
    """
    
    
    
    dp = [[None, None, None] for _ in range(N + 1)]
    a1, b1, c1 = abc[0]
    
    dp[1][0] = a1
    dp[1][1] = b1
    dp[1][2] = c1
    for i in range(2, N + 1):
        a, b, c = abc[i - 1]
        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)  
    return max(dp[N][0], dp[N][1], dp[N][2])



N = int(input())
abc = [tuple(map(int, input().split())) for _ in range(N)]
print(solve(N, abc))

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

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

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

Solution (Python):

N=int(input())
ha,hb,hc = map(int,input().split())

for i in range(1,N):
    a,b,c=map(int,input().split())
    ha,hb,hc = max(a+hb,a+hc),max(b+ha,b+hc),max(c+hb,c+ha)



hap=max(max(ha,hb),hc)
print(hap)

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

Solution (Python):


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

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

for i in range(1, N):
    for j in range(3):
        if j == 0:
            s, t = 1, 2
        elif j == 1:
            s, t = 0, 2
        else:
            s, t = 0, 1  
        happy[i][j] = max(abc[i][j] + happy[i-1][s],
                          abc[i][j] + happy[i-1][t])

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

Solution (Python):
import numpy as np

N = int(input())




dp = np.zeros((N + 1, 3)).astype(int)


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


print(max(dp[N]))

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


for idx,datum in enumerate(DATA):
  if idx == 0:
    prev = datum
  else:
    a,b,c = datum
    prev = a+max(prev[1],prev[2]),b+max(prev[0],prev[2]),c+max(prev[0],prev[1])

print(max(prev))

Solution (Python):
"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_c

C - Vaction
"""
INF = 100000007
import collections

def solve(troikas):
    dp = collections.defaultdict(lambda: -INF)
    for act in range(3):
        dp[(0, act)] = troikas[0][act]

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

N = int(input())
troikas = [[int(s) for s in input().split()] for _ in range(N)]
res = solve(troikas)
print(res)

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

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

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

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

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

Solution (Python):
if __name__=="__main__":
    n = int(input())
    A = [0 for i in range(n)]
    B = [0 for i in range(n)]
    C = [0 for i in range(n)]
    for i in range(n):
        A[i], B[i], C[i] = [int(i) for i in input().split(' ')]
    f = [0, 0, 0]
    for i in range(n):
        g = [0, 0, 0]
        g[0] = max(f[0], max(f[1], f[2]) + A[i])
        g[1] = max(f[1], max(f[0], f[2]) + B[i])
        g[2] = max(f[2], max(f[0], f[1]) + C[i])
        f = g
    print(max(f[0], max(f[1], f[2])))

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

print(max(dp[N]))

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


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

print(max(dp[N]))

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

dp[0] = abcs[0]


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

Solution (Python):
import sys

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

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

if N ==1:
    print(max(a, b, c))
    sys.exit()

a, b, c = map(int,input().split())
case1 = a + dp[0][1] 
case2 = a + dp[0][2] 
case3 = b + dp[0][0] 
case4 = b + dp[0][2] 
case5 = c + dp[0][0] 
case6 = c + dp[0][1]

dp[1][0] = max(case1,case2)
dp[1][1] = max(case3,case4)
dp[1][2] = max(case5,case6)

if N ==2:
    print(max(dp[1][0], dp[1][1], dp[1][2]))
    sys.exit()

for i in range (2, N):
    a, b, c = map(int,input().split())
    case1 = a + dp[i-1][1]
    case2 = a + dp[i-1][2]
    case3 = b + dp[i-1][0]
    case4 = b + dp[i-1][2]
    case5 = c + dp[i-1][0]
    case6 = c + dp[i-1][1]
    
    dp[i][0] = max(case1,case2)
    dp[i][1] = max(case3,case4)
    dp[i][2] = max(case5,case6)
    
print(max(dp[N-1][0],dp[N-1][1],dp[N-1][2]))

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

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


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


dp[0][0] = L[0][0]
dp[0][1] = L[0][1]
dp[0][2] = L[0][2]

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

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

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

dp[0][0]=L[0][0]
dp[0][1]=L[0][1]
dp[0][2]=L[0][2]

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

Solution (Python):
n=int(input())
A,B,C=[],[],[]
for i in range(n):
  a,b,c=map(int,input().split())
  A.append(a)
  B.append(b)
  C.append(c)
DP=[[0 for i in range(3)] for j 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],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[n-1][i] for i in range(3)))

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

dp = [[0 for _ in range(3)] for _ in range(N)]
dp[0] = abcList[0]
for i in range(1, N):
    for j in range(3):
        for k, element in enumerate(abcList[i]):
            if j == k:
                continue
            dp[i][k] = max(dp[i - 1][j] + element, dp[i][k])

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

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

dp = [[0]*3]*N

dp[0] = Aij[0]

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

    
    
    
    


print(max(dp[-1]))