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):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    n = int(readline())
    act = []
    for _ in range(n):
        a, b, c = map(int, readline().split())
        act.append((a, b, c))

    

    dp = [[0, 0, 0] for _ in range(n)]
    for j in range(3):
        dp[0][j] = act[0][j]

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

    print(max(dp[n-1]))
if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    n = int(readline())
    act = []
    for _ in range(n):
        a, b, c = map(int, readline().split())
        act.append((a, b, c))

    

    dp = [[0, 0, 0] for _ in range(n)]
    for j in range(3):
        dp[0][j] = act[0][j]

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

    print(max(dp[n-1]))
if __name__ == '__main__':
    main()

Solution (Python):
import sys,io
from functools import lru_cache
import numpy

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n=read()
a,b,c=[0]*n,[0]*n,[0]*n
for i,line in enumerate(readlines()):
    a[i],b[i],c[i]=mp(line)
dp=[[0,0,0] for i in range(n+1)]
for k in range(1,n+1):
    one=dp[k-1][1]
    two=dp[k-1][2]
    zero=dp[k-1][0]
    dp[k][0]= one if one >= two else two
    dp[k][0]+=a[k-1]
    dp[k][1]= zero if zero >= two else two
    dp[k][1]+=b[k-1]
    dp[k][2]= one if one >= zero else zero
    dp[k][2]+=c[k-1]

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

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)








n=n0()
ABC=n3(n)
ABC

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

print(max(dp[-1]))

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)








n=n0()
ABC=n3(n)
ABC

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

print(max(dp[-1]))

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

Solution (Python):
n=int(input())
l1=[]
l2=[]
l3=[]
for i in range(n):
	l=input().split()
	u=int(l[0])
	v=int(l[1])
	w=int(l[2])
	l1.append(u)
	l2.append(v)
	l3.append(w)
dpu=[0 for i in range(n)]
dpv=[0 for i in range(n)]
dpw=[0 for i in range(n)]
dpu[0]=l1[0]
dpv[0]=l2[0]
dpw[0]=l3[0]
for i in range(1,n):
	dpu[i]=max(dpv[i-1],dpw[i-1])+l1[i]
	dpv[i]=max(dpu[i-1],dpw[i-1])+l2[i]
	dpw[i]=max(dpu[i-1],dpv[i-1])+l3[i]
print(max(dpu[-1],dpv[-1],dpw[-1]))

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

Solution (Python):
import numpy as np
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_list = [[0] * 3 for _ in range(N)]

DP_list[0] = [a[0], b[0], c[0]]

base = np.array([a,b,c]).T
for i in range(1,N):
  DP_list[i][0] = base[i][0] + max(DP_list[i-1][1], DP_list[i-1][2])
  DP_list[i][1] = base[i][1] + max(DP_list[i-1][0], DP_list[i-1][2])
  DP_list[i][2] = base[i][2] + max(DP_list[i-1][1], DP_list[i-1][0])

print(int(max(DP_list[-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] * 3 for _ in range(N)]

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

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

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

dp = [[0] * 3 for _ in range(n + 10) ]
for i in range(n):
    dp[i + 1][0] = chmax(dp[i][1] + A[i], dp[i][2] + A[i])
    dp[i + 1][1] = chmax(dp[i][0] + B[i], dp[i][2] + B[i])
    dp[i + 1][2] = chmax(dp[i][0] + C[i], dp[i][1] + C[i])

print(max(dp[n]))

Solution (Python):
from sys import stdin,stdout
inp = stdin.readline
out = stdout.write
n = int(inp())
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0] = list(map(int,inp().split()))
for i in range(1,n):
    a,b,c = map(int,inp().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][1],dp[i-1][0])+c
out(str(max(dp[n-1])))

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

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

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

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

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]
for i in range(1,N):
  for j in range(3):
    dp[i][j] = abc[i][j] + max(vv for k,vv in enumerate(dp[i-1]) if k != j)

print(max(dp[-1]))

Solution (Python):
def main():
    import sys
    n = int(input())
    a, b, c = 0, 0, 0
    for x in sys.stdin.readlines():
        aa, bb, cc = map(int, x.split())
        if a == b == c == 0:
            a, b, c = aa, bb, cc
        else:
            a, b, c = aa+max(b, c), bb+max(a, c), cc+max(a, b)

    print(max(a, b, c))

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

N = int(input())

values = [tuple(map(int, input().split(' '))) for _ in range(N)]
dp = [values[0]]
for _ in range(N - 1):
    dp.append([0, 0, 0])

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

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

Solution (Python):
import numpy as np

N = int(input())

values = np.array([list(map(int, input().split(' '))) for _ in range(N)])
dp = np.zeros(shape=(N, 3), dtype=int)

dp[0] = values[0]

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

print(np.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[N]))

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    A = [0, 0, 0]
    for _ in range(N):
        B = read_ints()
        A = [
            max(A[j]+B[i] for j in range(3) if i != j)
            for i in range(3)
        ]
    return max(A)


if __name__ == '__main__':
    print(solve())

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

Solution (Python):
n=int(input())
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
dp=[[0 for i in range(3)] for j in range(n)]
dp[0]=li[0]

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

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

Solution (Python):
"""
task statement
==============

明日から太郎君の夏休みが始まります。
太郎君は夏休みの計画を立てることにしました。
夏休みは N 日からなります。
各 i (1 \leq i \leq N) について、i 日目には太郎君は次の活動のうちひとつを選んで行います。

A: 海で泳ぐ。 幸福度 a_i を得る。
B: 山で虫取りをする。 幸福度 b_i を得る。
C: 家で宿題をする。 幸福度 c_i を得る。

太郎君は飽き性なので、2 日以上連続で同じ活動を行うことはできません。
太郎君が得る幸福度の総和の最大値を求めてください。

io_style
-------
N
a_1 b_1 c_1
a_2 b_2 c_2
:
a_N b_N c_N
"""


import sys

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

if __name__ == "__main__":
    main2()

Solution (Python):
N = int(input())
ans = list(map(int, input().split()))
for _ in range(1, N):
    a, b, c = map(int, input().split())
    tmpa, tmpb, tmpc = ans
    ans[0] = a + max(tmpb, tmpc)
    ans[1] = b + max(tmpa, tmpc)
    ans[2] = c + max(tmpa, tmpb)

print(max(ans))

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

Solution (Python):
import sys

inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))


def solve():
	n = int(inp())
	dic = read()
	for _ in range(n-1):
		arr = read()
		for i in range(3):
			
			arr[i] += max([dic[j] for j in range(3) if i != j])
		dic = arr
		
			
			
			
			
			
			
	print(max(dic))



if __name__ == "__main__":
	solve()

Solution (Python):
import sys

inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))


def solve():
	n = int(inp())
	dic = read()
	for _ in range(n-1):
		arr = read()
		for i in range(3):
			
			arr[i] += max([dic[j] for j in range(3) if i != j])
		dic = arr
		
			
			
			
			
			
			
	print(max(dic))



if __name__ == "__main__":
	solve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product

def solve():
    n = II()

    V = [[] for _ in range(n)]
    for i in range(n):
        a, b, c = MI()
        V[i] = [a, b, c]

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

    
    for i in range(1, n):

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


if __name__ == '__main__':
    solve()

Solution (Python):
import math
import bisect
from queue import Queue
from collections import deque

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

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


for i in range(n):
    if(i == 0):
        for j in range(3):
            d[i][j] = table[i][j]
    else:
        d[i][0] = table[i][0] + max(d[i-1][1], d[i-1][2])
        d[i][1] = table[i][1] + max(d[i-1][0], d[i-1][2])
        d[i][2] = table[i][2] + max(d[i-1][0], d[i-1][1])
print(max(d[n-1]))

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

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

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

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



def main():
    N = int(input().strip())
    happy_list = [[int(i) for i in input().strip().split()] for _ in range(N)]
    dp = [[None, None, None] for _ in range(N)]

    dp[0] = happy_list[0]

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

    return max(dp[-1])


if __name__ == "__main__":
    print(main())

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    dp0, dp1, dp2 = 0, 0, 0
    for _ in range(n):
        a, b, c = map(int, input().split())
        dp0, dp1, dp2 = max(dp1, dp2) + a, max(dp2, dp0) + b, max(dp0, dp1) + c
    print(max(dp0, dp1, dp2))
resolve()

Solution (Python):
import sys
rl = sys.stdin.readline
n = int(rl())
x, y, z = 0, 0, 0
for _ in range(n):
  a, b, c = map(int, rl().split())
  x, y, z = max(y, z) + a, max(x, z) + b, max(x, y) + c
print(max(x, y, z))

Solution (Python):
import sys
rl = sys.stdin.readline
n = int(rl())
x, y, z = 0, 0, 0
for _ in range(n):
  a, b, c = map(int, rl().split())
  x, y, z = max(y, z) + a, max(x, z) + b, max(x, y) + c
print(max(x, y, z))

Solution (Python):
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

n = int(rl())
li = [list(map(int, rl().split())) for _ in range(n)]
dp = [[0]*3 for _ in range(n)]
dp[0] = li[0]

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

Solution (Python):
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

n = int(rl())
li = [list(map(int, rl().split())) for _ in range(n)]
dp = np.zeros((n, 3), dtype=int)
dp[0] = li[0]

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

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

dp = [[0]*3 for _ in range(N+10)]
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][j])

print(max(dp[N]))

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

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

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

dp[0][0] = abc[0][0]
dp[0][1] = abc[0][1]
dp[0][2] = abc[0][2]

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

print(max(dp[-1]))

Solution (Python):
n = int(input())
v = []
for i in range(n):
    v.append(list(map(int,input().split(" "))))
for i in range(1,n):
    e = sorted(v[i-1][:])
    m1 = e[2]
    m2 = e[1]
    for j in range(3):
        if m1 == v[i-1][j]:
            v[i][j] += m2
        else: v[i][j] += m1
print(max(v[n-1]))

Solution (Python):
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 200010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=spf[1] = -1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]
 
def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))
 
def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))
 
def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD
 
    return (num*(pow(den,MOD-2,MOD)))%MOD
 
def flush():
    return sys.stdout.flush()
 
'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
n = int(input())
a = [arrIN() for _ in range(n)]
dp = deepcopy(a)
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])
print(max(dp[-1]))

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    ABC = [list(map(int, input().split())) for _ in range(n)]

    dp = [[0 for _ in range(3)] for _ in range(n)]
    dp[0][0] = ABC[0][0]
    dp[0][1] = ABC[0][1]
    dp[0][2] = ABC[0][2]
    
    for i in range(1, n):
        a = ABC[i][0]
        b = ABC[i][1]
        c = ABC[i][2]

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

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


if __name__ == '__main__':
    resolve()

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

Solution (Python):
import numpy as np
N=int(input())
happines=[]
dp=[[0,0,0,0,0,0] for i in range(N+1)]
for i in range(N):
    happy=list(map(int,input().split()))
    happines.append(happy)
def dp_search():
    zenkai=-1
    for i in range(N):
        if i<=N-1:
            dp[i + 1][0] = max(dp[i][2],dp[i][3])+happines[i][0]
            dp[i + 1][1] = max(dp[i][4],dp[i][5])+happines[i][0]
            dp[i + 1][2] = max(dp[i][0],dp[i][1])+happines[i][1]
            dp[i + 1][3] = max(dp[i][4],dp[i][5])+happines[i][1]
            dp[i + 1][4] = max(dp[i][0],dp[i][1])+happines[i][2]
            dp[i + 1][5] = max(dp[i][2],dp[i][3])+happines[i][2]
    print(max(dp[-1]))
dp_search()

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

Solution (Python):



n = int(input())

last = [0,0,0]
for i in range(n):
    new = list(map(int, input().split()))
    newDp = [0,0,0]
    for j in range(3):
        for k in range(3):
            if j!=k:
                newDp[j] = max(newDp[j], last[k]+new[k])
    last = newDp
print(max(last))

Solution (Python):
from collections import defaultdict
n = int(input())
d = defaultdict(list)
for i in range(n):
  d[i] = list(map(int,input().split()))
mp = [[0,0,0] for i in range(n)] 
mp[0] = d[0]
for i in range(1,n):
  mp[i][0] = max(mp[i-1][1],mp[i-1][2]) + d[i][0]
  mp[i][1] = max(mp[i-1][0],mp[i-1][2]) + d[i][1]
  mp[i][2] = max(mp[i-1][1],mp[i-1][0]) + d[i][2]
print(max(mp[n-1]))

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

Solution (Python):
import numpy as np
def dprint(*args):
  if debug:
    if len(args)==1:
      print(args[0])
    else:
      print(args)

debug = False
if debug:
  N=3
  ABC=[[10, 40, 70], [20, 50, 80], [30, 60, 90]]
else:
  N = int(input())
  ABC=[]
  for i in range(N):
    ABC.append(list(map(int,input().split())))

dprint(N,ABC)




H = np.zeros((N,3))
H[0]=ABC[0]

for j in range(1,N):
  H[j][0]=max(H[j][0], H[j-1][1]+ABC[j][0], H[j-1][2]+ABC[j][0])
  H[j][1]=max(H[j][1], H[j-1][0]+ABC[j][1], H[j-1][2]+ABC[j][1])
  H[j][2]=max(H[j][2], H[j-1][0]+ABC[j][2], H[j-1][1]+ABC[j][2])

print(int(max(H[-1])))

Solution (Python):
def vacation(mat):
    temp = [0] * 3
    dp = mat[0]
    for i in range(1, len(mat)):
        temp[0] = mat[i][0] + max(dp[1], dp[2])
        temp[1] = mat[i][1] + max(dp[0], dp[2])
        temp[2] = mat[i][2] + max(dp[0], dp[1])
        dp = temp[:]
    return max(dp)


if __name__ == '__main__':
    n = int(input())
    mat = [[0] * 3 for _ in range(n)]
    for i in range(n):
        mat[i] = list(map(int, input().split()))

    print(vacation(mat))

Solution (Python):
N = int(input())
List = [list(map(int,input().split())) for x in range(N)]
List2 = []
for n in range(N):
  if n == 0:
    List2.append(List[0])
  else:
    a = List[n][0] + max(List2[n-1][1],List2[n-1][2])
    b = List[n][1] + max(List2[n-1][0],List2[n-1][2])
    c = List[n][2] + max(List2[n-1][0],List2[n-1][1])
    List2.append([a,b,c])

print(max(List2[-1]))

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

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

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

    print(max(Happy[n]))
resolve()

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

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


main()

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


main()

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

for i in range(1,l):
    z = list(map(int,input().split()))
    x[i][0] = max(z[0]+x[i-1][1],z[0]+x[i-1][2])
    x[i][1] = max(z[1]+x[i-1][0],z[1]+x[i-1][2])
    x[i][2] = max(z[2]+x[i-1][0],z[2]+x[i-1][1])

print(max(x[-1]))

Solution (Python):
N = int(input())
l = []

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

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

for i in range(N):
    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] + l[i][k])
ans = 0
for i in range(3):
    ans = max(ans, dp[N][i])
print(ans)

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

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

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


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

print(max(dp[-1]))

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

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque 


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush




def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 10**9+7
    

    N = int(input())
    
    
    
    S = tuple(tuple(map(int, input().split())) for i in range(N)) 

    dp=[0]*3
    ndp=copy(dp)
    for i in range(N):
        a,b,c=S[i]
        ndp[0]=max(dp[1]+a,dp[2]+a)
        ndp[1]=max(dp[0]+b,dp[2]+b)
        ndp[2]=max(dp[1]+c,dp[0]+c)
        ndp,dp=dp,ndp
    print(max(dp))



if __name__ == "__main__":
    main()

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

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