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

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

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

dp[0] = li[0]

for i in range(1,n):
    for j in range(0,3):
        for k in range(0,3):
            if k != j:
                if dp[i][k] < (dp[i-1][j] + li[i][k]):
                    dp[i][k] = dp[i-1][j] + li[i][k]

  
print(max(dp[-1]))

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

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

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


for i in range(N):
    a,b,c=nums[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)
num = max(dp[-1])
if N==1:
    num = max(nums[0])
print(num)

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

Solution (Python):
N=int(input())
happy=[]
dp=[[0,0,0] for r in range(N)]
for i in range(N):
  happy.append(list(map(int,input().split())))
dp[0]=happy[0].copy()
for i in range(1,N):
  for j in range(3):
    for k in range(3):
      if j != k :
        dp[i][j]=max(dp[i-1][k]+happy[i][j],dp[i][j])
        

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

Solution (Python):
N = int(input())
a = []
b = []
c = []
for i in range(N):
    num = list(map(int, input().split(' ')))
    a.append(num[0])
    b.append(num[1])
    c.append(num[2])
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] = 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])
ans = max(dp[N -1][0], dp[N -1][1], dp[N -1][2])
print(ans)

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

dp = [ [0 for i in range(3)] for i in range(N)]
for i in range(3):
    dp[0][i] = ls[0][i]
for i in range(1,N):
    for j in range(3):
        w = [0,1,2]
        w.remove(j)
        x,y = w[0],w[1]
        dp[i][j] = max(dp[i-1][x],dp[i-1][y]) + ls[i][j]
            
print(max(dp[N-1]))

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

print(max([dp[N-1][i] for i in range(3)]))

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

print(max([dp[N-1][i] for i in range(3)]))

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

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

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

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

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

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

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

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

Solution (Python):

n = int(input())
A = list(list(map(int, input().split())) for _ in range(n))

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

for i in range(n):
    for j in range(3):
        for k in range(3):
            if j == k:
                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())

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

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

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

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

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

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

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

Solution (Python):
def main():
    N = int(input())
    acts = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        acts.append([a,b,c])
    dp = [[0] * 3 for _ in range(N + 5)]

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

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



if __name__ == "__main__":
    main()

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):
import numpy as np


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

    dp = np.zeros((n, 3), dtype='int')
    dp[0] = d[0]

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

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


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
INF=float('inf')

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

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

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

Solution (Python):





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

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

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



print(max(dp[-1]))

Solution (Python):





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

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

for i in range(N):
    if i == 0:
        dp[i][0] = abc[i][0]
        dp[i][1] = abc[i][1]
        dp[i][2] = abc[i][2]
        continue

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



print(max(dp[-1]))

Solution (Python):
'''
in
-----
7
2
9
4
5
1
6
10
'''
'''
out
-----
8
'''
from collections import defaultdict
dp = defaultdict(lambda:int(0))

N = int(input())
L = [0] * (N +2)
for i in range(0, N):
    L[i] = list(map(int, input().split()))

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

print(max(dp.values()))

Solution (Python):
import numpy as np
N = int(input())
abc = []
for i in range(N):
  abc.append([int(i) for i in input().split()])
abc.append([0,0,0])
dp = np.zeros([N+1,3])


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

Solution (Python):
d={}
for i in range(int(input())):
    d[i]={}
    a,b,c=map(int,input().split())
    if i==0:
        d[i][0]=a
        d[i][1]=b
        d[i][2]=c
    else:
        d[i][0]=max(d[i-1][1],d[i-1][2])+a
        d[i][1]=max(d[i-1][0],d[i-1][2])+b
        d[i][2]=max(d[i-1][1],d[i-1][0])+c
print(max(d[i][0],d[i][1],d[i][2]))

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

def main(n,h):
    dp = [[h[0][0],h[0][1],h[0][2]]]
    for i in range(1,n):
        cur = h[i]
        prev = dp[-1]
        temp = []
        temp.append(max(prev[1],prev[2])+cur[0])
        temp.append(max(prev[0],prev[2])+cur[1])
        temp.append(max(prev[0],prev[1])+cur[2])
        dp.append(temp)
    print(max(dp[-1]))
    
if __name__=="__main__":
    n,h = getval()
    main(n,h)

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

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

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

for i in range(n-1):
    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]+l[i+1][k])
print(max(dp[n-1]))

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

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

    print(max(dp[-1]))


if __name__ == "__main__":
    main()

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

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

    print(max(dp[-1]))


if __name__ == "__main__":
    main()

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

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

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

    print(max(dp))

main()

Solution (Python):
def i_input(): return int(input())


def i_map(): return map(int, input().split())


def i_list(): return list(i_map())


def i_row_list(N): return [i_list() for _ in range(N)]


n = i_input()
abc = i_row_list(n)
dp=[]
for i in range(n):
    dp.append([0]*3)
dp[0] = abc[0]
for i in range(n):
    if i!=0:
        for j in range(3):
            for k in range(3):
                if j!=k:
                    dp[i][k]=max(dp[i][k],dp[i-1][j]+abc[i][k])

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

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

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

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

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

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

a=[0]
b=[0]
c=[0]



dp=[[0 for i in range(3)] for j in range(n+1)]
for i in range(n):
    x,y,z=map(int,input().split())
    a.append(x)
    b.append(y)
    c.append(z)
for i in range(1,n+1):
    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]))

Solution (Python):
def li():
    return [int(x) for x in input().split()]


N = int(input())
L = []
for i in range(N):
    L.append(li())






dp = [[0]*3 for i in range(N+1)]
dp[0] = L[0]
for i in range(1, N):
    for k in range(3):
        if k == 0:
            dp[i][k] = max(dp[i][k], dp[i-1][1] + L[i][0], dp[i-1][2] + L[i][0])
        elif k == 1:
            dp[i][k] = max(dp[i][k], dp[i-1][0] + L[i][1], dp[i-1][2] + L[i][1])
        elif k == 2:
            dp[i][k] = max(dp[i][k], dp[i-1][0] + L[i][2], dp[i-1][1] + L[i][2])

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

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

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

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

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

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

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

for i in range(1, N + 1):
    a = tuple(map(int, input().split()))
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i][j] = max(dp[i][j], dp[i - 1][k] + a[j])
print(max(dp[N]))

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

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

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

Solution (Python):
''' ===============================
    -- @uthor : Kaleab Asfaw
    -- Handle : kaleabasfaw2010
    -- Bio    : High-School Student
    ==============================='''


import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b: break
            ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0; return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1; return self.buffer.readline()
    def flush(self):
        if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")



mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
	ans = 1
	for i in range(1, x+1): ans = (ans * i) % mod
	return ans
def arr2D(n, m, default=0):
	lst = []
	for i in range(n): temp = [default] * m; lst.append(temp)
	return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def rest(i):
	if i == 1: return [0, 2]
	elif i == 2: return [0, 1]
	else: return [1, 2]

def solve(n, lst):
	dp = arr2D(n+1, 3,-1)
	for i in range(1, n+1):
		for j in range(3):
			if dp[i-1][j] == -1:
				dp[i][j] = lst[i-1][j]
			else:
				for k in rest(j):
					dp[i][j] = max(dp[i-1][k] + lst[i-1][j], dp[i-1][k] + lst[i-1][j], dp[i][j])
	return max(dp[n])



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

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

Solution (Python):
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] = map(int, input().split())

DP = [[0 for j in range(3)] for i in range(n)]
DP[0][0], DP[0][1], DP[0][2] = 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][0], DP[n - 1][1], DP[n - 1][2]))

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

Solution (Python):

import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)

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

    A = [0]
    B = [0]
    C = [0]

    for i in range(N):
        a = max(B[-1], C[-1]) + abc[i][0]
        b = max(C[-1], A[-1]) + abc[i][1]
        c = max(A[-1], B[-1]) + abc[i][2]
        A.append(a)
        B.append(b)
        C.append(c)

    print(max(A[-1], B[-1], C[-1]))

if __name__ == '__main__':
    main()

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

A = [0]
B = [0]
C = [0]
for d in range(n):
    a = h[d][0] + max(B[-1],C[-1])
    b = h[d][1] + max(A[-1],C[-1])
    c = h[d][2] + max(A[-1],B[-1])
    A += [a]
    B += [b]
    C += [c]
print(max(A[-1],B[-1],C[-1]))

Solution (Python):
import sys
sys.setrecursionlimit(2000000001)
n,ar,dp = 0,0,0

def solve(d,pi):
	global n,ar,dp
	if d>=n: return 0
	if dp[d][pi]:
		
		return dp[d][pi]

	
	

	m = 0
	for j in range(3):
		if not j is pi:
			tmp = solve(d+1,j)
			
			m = max(m,ar[d][pi] + tmp)
	
	dp[d][pi] = m	

	
	
	

	return dp[d][pi]

def main():
	global n,ar,dp
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n, = I()
	ar = [[*I()] for _ in range(n)]
	dp = [[0,0,0] for _ in range(n-1)]+[ar[-1]]
	pr(max(solve(0,0),solve(0,1),solve(0,2)))
	
	

main()

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

aa = 0
bb = 0
cc = 0 

for i in range(n):
    a,b,c = map(int,input().split())
    aa,bb,cc = max(bb + a, cc + a),max(aa + b, cc + b),max(aa + c, bb + c)

print(max(aa,bb,cc))

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


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


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

print(max(dp[-1]))

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

def main():
    n = int(input())
    
    A = [0]*n
    B = [0]*n
    C = [0]*n
    
    a,b,c = map(int,input().split())
    A[0] = a
    B[0] = b
    C[0] = c
    
    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]))
    
if __name__ == '__main__':
    main()

Solution (Python):
def solve(arr,dp,N):
    dp[0][0],dp[0][1],dp[0][2]=matrix[0][0],matrix[0][1],matrix[0][2]
    for i in range(1,N):
        dp[i][0]=arr[i][0]+max(dp[i-1][1],dp[i-1][2])
        dp[i][1]=arr[i][1]+max(dp[i-1][0],dp[i-1][2])
        dp[i][2]=arr[i][2]+max(dp[i-1][0],dp[i-1][1])
    return max(dp[-1])
if __name__ == "__main__":
    N=int(input())
    matrix=[[0 for j in range(3)] for i in range(N)]
    dp=[[0 for j in range(3)] for i in range(N)]
    for i in range(N):
        matrix[i][0],matrix[i][1],matrix[i][2]=map(int,input().split())
    print(solve(matrix,dp,N))

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

def main(n,h):
    dp = [[h[0][0],h[0][1],h[0][2]]]
    for i in range(1,n):
        cur = h[i]
        prev = dp[-1]
        temp = []
        temp.append(max(prev[1],prev[2])+cur[0])
        temp.append(max(prev[0],prev[2])+cur[1])
        temp.append(max(prev[0],prev[1])+cur[2])
        dp.append(temp)
    print(max(dp[-1]))
    
if __name__=="__main__":
    n,h = getval()
    main(n,h)

Solution (Python):

def main():
    n = int(input())
    abc_list = []
    for i in range(n):
        abc_list.append(list(map(int, input().split())))
    dp = [[0] * 3 for i in range(n)]
    dp[0][0] = abc_list[0][0]
    dp[0][1] = abc_list[0][1]
    dp[0][2] = abc_list[0][2]
    
    for i in range(1, n):
        dp[i][0] = abc_list[i][0] + max(dp[i - 1][1], dp[i - 1][2])
        dp[i][1] = abc_list[i][1] + max(dp[i - 1][0], dp[i - 1][2])
        dp[i][2] = abc_list[i][2] + max(dp[i - 1][0], dp[i - 1][1])
        
    print(max(dp[-1]))
        
if __name__ == "__main__":
    main()

Solution (Python):

def main():
    n = int(input())
    abc_list = []
    for i in range(n):
        abc_list.append(list(map(int, input().split())))
    dp = [[0] * 3 for i in range(n)]
    dp[0][0] = abc_list[0][0]
    dp[0][1] = abc_list[0][1]
    dp[0][2] = abc_list[0][2]
    
    for i in range(1, n):
        dp[i][0] = abc_list[i][0] + max(dp[i - 1][1], dp[i - 1][2])
        dp[i][1] = abc_list[i][1] + max(dp[i - 1][0], dp[i - 1][2])
        dp[i][2] = abc_list[i][2] + max(dp[i - 1][0], dp[i - 1][1])
        
    print(max(dp[-1]))
        
if __name__ == "__main__":
    main()

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

N = int(readline())
dp = [[0] * 3 for i in range(N + 1)]

for i in range(N):
  works = list(map(int,readline().split()))
  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] + works[k])

print(max(dp[-1]))

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

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

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

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

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


dp[0] = l[0]

for i in range(1,n):
    for jnow in range(3):
        for jpre in nums:
            if jpre != jnow:
                dp[i][jnow] = max(dp[i][jnow],dp[i-1][jpre]+l[i][jnow])
print(max(dp[n-1]))

Solution (Python):
'''
Created on 2020/09/15

@author: harurun
'''
import sys
pin=sys.stdin.readline

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

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

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

DP = [0] * 3

for f in F:
    D = [0] * 3
    S = {0, 1, 2}
    for i in range(3):
        S.remove(i)
        for s in S:
            D[i] = max(D[i], f[i] + DP[s])
        S.add(i)
    DP = D

print(max(DP))

Solution (Python):
N = int(input())
Da = [0 for i in range(N+1)]
Db = [0 for i in range(N+1)]
Dc = [0 for i in range(N+1)]
for i in range(1, N+1):
  a, b, c = map(int, input().split())
  Da[i] = max(Db[i-1], Dc[i-1]) + a
  Db[i] = max(Da[i-1], Dc[i-1]) + b
  Dc[i] = max(Da[i-1], Db[i-1]) + c
print(max(Da[N], Db[N], Dc[N]))

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

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

grid = []

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

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

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

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

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

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

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

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

print(max(dp[-1]))

Solution (Python):
import enum


def main():
    N = int(input())
    dp = [[] for _ in range(N)]
    for i in range(N):
        abc = list(map(int, input().split()))
        if i == 0:
            dp[0] = abc
        else:
            for k, v in enumerate(abc):
                vals = []
                for j in range(3):
                    if k != j:
                        vals.append(dp[i-1][j])
                dp[i].append(v + max(vals))

    print(max(dp[-1]))


if __name__ == '__main__':
    main()

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

Solution (Python):
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)



N = inp()
a = [0] * N
b = [0] * N
c = [0] * N
for i in range(N):
    a[i], b[i], c[i] = inpl()

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

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

print(mx)

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

dp = [list([0,0,0]) 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] = arr[i][0] + max(dp[i-1][1],dp[i-1][2])
    dp[i][1] = arr[i][1] + max(dp[i-1][0],dp[i-1][2])
    dp[i][2] = arr[i][2] + max(dp[i-1][1],dp[i-1][0])
print(max(dp[-1]))

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

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

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

Solution (Python):
import sys
N = int(input())
X = [[0,0,0]] + [list(map(int, input().split())) for _ in range(N)]
A = [[0]*3 for _ in range(N+1)]
for i in range(1,N+1):
  A[i][0] = max(A[i-1][1],A[i-1][2]) + X[i][0]
  A[i][1] = max(A[i-1][0],A[i-1][2]) + X[i][1]
  A[i][2] = max(A[i-1][0],A[i-1][1]) + X[i][2]

print(max(A[N]))

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

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

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

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

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

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

print(max(dp[-1]))