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


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    N = int(input())
    A = [0]
    B = [0]
    C = [0]
    for _ in range(N):
        a, b, c = map(int, input().split())
        A.append(a)
        B.append(b)
        C.append(c)
    dp = [[0 for _ in range(N + 1)] for _ in range(3)]

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

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


if __name__ == "__main__":
    main()

Solution (Python):
def q3():
    """C - Vacation"""
    N = int(input())

    dp = [[0]*N for i in range(3)]
    dp[0][0], dp[1][0], dp[2][0] = (int(i) for i in input().split())

    if N == 1:
        print(max([dp[0][0], dp[1][0], dp[2][0]]))
        return

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

    if N == 2:
        print(max([dp[0][1], dp[1][1], dp[2][1]]))
        return

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


if __name__ == '__main__':
    q3()

Solution (Python):
N = int(input())
happiness = [[0,0,0] for i in range(N)]
for i in range(N) :
	feeling = [int(i) for i in input().split()]
	for j in range(3) :
		if i != 0 :
			if j == 0 :
				happiness[i][j] = feeling[j] + max(happiness[i-1][1], happiness[i-1][2])
			elif j == 1 :
				happiness[i][j] = feeling[j] + max(happiness[i-1][0], happiness[i-1][2])
			elif j == 2 :
				happiness[i][j] = feeling[j] + max(happiness[i-1][0], happiness[i-1][1])
		else :
			happiness[i] = feeling
			break
print(max(happiness[N-1]))

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

dp = [[0,0,0] for _ in range(n)]
dp[0] = l[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] + l[i][j])

print(max(dp[-1]))

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



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


def chmax(dp,i,j, x):
	b = (dp[i][j]<x)
	if b: dp[i][j]=x
	return b


for i in range(N):
	for j in range(3):
		for k in range(3):
			if j==k: continue
			chmax(dp,i,j, H[i][j] + (dp[i-1][k] if i>0 else 0))

print( max(dp[-1]) )

Solution (Python):


def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()

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


for i in range(N):
    abc = LIST()
    if i == 0:
        DP[0] = abc
        continue
    for j in range(3):
        DP[i][j] = max(DP[i-1][(j+1)%3] + abc[j],
                       DP[i-1][(j+2)%3] + abc[j])


print(max(DP[-1]))

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

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


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

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


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

Solution (Python):

import sys
N = int(sys.stdin.readline())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]


dp = [[0,0,0] for _ in range(N)]
dp[0] = L[0].copy()
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):
n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

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

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

print(max(dp[-1]))

Solution (Python):
def main():
    N = int(input())
    DP = [[0 for i in range(3)] for j in range(N+1)]
    
    for i in range(N):
        a = list(map(int, input().split()))
        for x in range(3):
            for y in range(3):
                if x != y:
                    DP[i+1][y] = max(DP[i+1][y],DP[i][x]+a[y])
    print(max(DP[-1]))

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

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

Solution (Python):
n = int(input())
abc = [map(int,input().split()) for _ in range(n)]
a,b,c = [list(i) for i in zip(*abc)]
dp = [[0]*3 for _ in range(n+1)]
d = [0,1,2] 
for i in d:
    dp[0][i] = 0
for i in range(1,n+1):
    for j in d:
        if j%3 == 0:
            dp[i][j] = max(dp[i-1][(j+1)%3]+a[i-1],dp[i-1][(j+2)%3]+a[i-1])
        elif j%3 == 1:
            dp[i][j] = max(dp[i-1][(j+1)%3]+b[i-1],dp[i-1][(j+2)%3]+b[i-1])
        else:
            dp[i][j] = max(dp[i-1][(j+1)%3]+c[i-1],dp[i-1][(j+2)%3]+c[i-1])
ans = max(dp[n][0],dp[n][1],dp[n][2])
print(ans)

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

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

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

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

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

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

n = int(input())
dp = [[0]*3  for _ in range(n)] 
ABC = []
for _ in range(n):
    a,b,c = map(int,input().split())
    ABC.append([a,b,c])

def rec(flag,num):
    if dp[num][flag] != 0:
        return dp[num][flag]
    if num == 0:
        dp[num][flag] = ABC[num][flag]
        return dp[num][flag]
    else:
        res = 0
        if flag == 0:
            res = max(rec(1,num-1),rec(2,num-1))+ABC[num][flag]
        elif flag == 1:
            res = max(rec(0,num-1),rec(2,num-1))+ABC[num][flag]
        else:
            res = max(rec(1,num-1),rec(0,num-1))+ABC[num][flag]
        dp[num][flag] = res
        return dp[num][flag]

rec(0,n-1)
rec(1,n-1)
rec(2,n-1)

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

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

X=[0]   
for x in range(N):
    x=tuple(map(int,input().split()))
    X.append(x)

inf=float('inf')
DP=[[0,0,0]]
for i in range(N):
    DP.append([-inf,-inf,-inf])


DP[1][0]=X[1][0]
DP[1][1]=X[1][1]
DP[1][2]=X[1][2]

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


    

print(max(DP[N]))

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    HAPPY = [list(map(int, input().split())) for i in range(N)]
    dp = [[0]*3 for i 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], HAPPY[i][k] + dp[i][j])
    print(max(max(dp[N][0], dp[N][1]), dp[N][2]))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    HAPPY = [list(map(int, input().split())) for i in range(N)]
    dp = [[0]*3 for i 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], HAPPY[i][k] + dp[i][j])
    print(max(max(dp[N][0], dp[N][1]), dp[N][2]))

if __name__ == '__main__':
    main()

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

  dp = [[0] * 3 for i in range(n+1)]
  for i in range(0,n):
    for j in range(3):
      for k in range(3):
        if(j==k):
          continue
        else:
          dp[i+1][k]=max(dp[i+1][k],dp[i][j]+num_list[i][k])
  print(int(max(dp[n][0],dp[n][1],dp[n][2])))

if __name__ == '__main__':
    main()

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

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

for i in range(1,N+1):
    for p in range(3):
        for y in range(3):
            if (p!=y):
                dp[i][p]=max(dp[i][p],dp[i-1][y]+H[i][p])

print(max(dp[N]))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

print(max(a,b,c))

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

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

def chmax(x,y):
    if x>y:
        return x
    else:
        return y

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]+lst[i-1][k])
print(max(dp[n]))

Solution (Python):
import numpy as np
n=int(input())
abc=[]
for _ in range(n):
      abc.append(list(map(int,input().split())))
dp=np.zeros((n+1,3),np.int64)

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

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

Solution (Python):
from collections import defaultdict
n = int(input())
tuples = []
for i in range(n):
    a,b,c = map(int,input().split())
    tuples.append((a,b,c))
dp = [defaultdict(int) for _ in range(n+1)]
dp[0][3] = 0
for i in range(n):
    abc = tuples[i]
    for j in range(3):
        for k in dp[i].keys():
            if k != j:
                dp[i+1][j] = max(dp[i][k]+abc[j],dp[i+1][j])
print(max(dp[n].values()))

Solution (Python):
def solve():
    N = int(input())
    value = []
    for i in range(N):
        a,b,c = map(int,input().split())
        value.append([a,b,c])
    
    dp = [[0] * 3 for i in range(N)]
    dp[0][0] = value[0][0]
    dp[0][1] = value[0][1]
    dp[0][2] = value[0][2]

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

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
a=[[0],[0],[0]]
n = int(input())
for i in range(n):
    A,B,C = map(int,input().split())
    a[0].append(A)
    a[1].append(B)
    a[2].append(C)
dp = []
for j in range(n+1):
    dp.append([0,0,0])

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

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


for _ in range(n):
    c=list(map(int,input().split()))
    ndp=[0,0,0]
    for i in range(3):
        for j in range(3):
            if i!=j:
                ndp[j]=max(ndp[j],dp[i]+c[i])
    dp=ndp

print(max(dp))

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

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

for i in range(3):
    dp[0][i] = act[0][i]

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]) + act[i][j]


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

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

Solution (Python):
N = int(input())
l = []
for i in range(N):
    h = [int(x) for x in input().split()]
    l.append(h)
DP=[[0 for i in range(3)] for j in range(N+1)]
for j in range(0,N):
    for i in range(3):
        DP[j+1][i%3] = max(DP[j][(i+1)%3]+l[j][i%3], DP[j][(i+2)%3]+l[j][i%3])
print(max(DP[N][0],DP[N][1],DP[N][2]))

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

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

N = int(input())
Act = [[0,0,0]] + [list(map(int,input().split())) for _ in range(N)]
dp = [[None for _ in range(3)] for _ in range(N+1)]
dp[1][0] = Act[1][0]
dp[1][1] = Act[1][1]
dp[1][2] = Act[1][2]

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

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

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

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

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


def main():
    size = int(input())
    dp = [0] * 3
    for _ in range(size):
        z = (list(map(int, input().split())))
        newDp = [0] * 3
        for i in range(3):
            for j in range(3):
                if j != i:
                    
                    
                    newDp[j] = max(newDp[j], dp[i] + z[j])
        dp = newDp
    print(max(dp[0],dp[1],dp[2]))


if __name__ == "__main__":
    main()

Solution (Python):

import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') 
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(sys.stdin.readline()) 
def ifn(): return float(sys.stdin.readline()) 
def isn(): return sys.stdin.readline().split() 
def imn(): return map(int, sys.stdin.readline().split()) 
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) 
def fmn(): return map(float, sys.stdin.readline().split()) 
def iln(): return list(map(int, sys.stdin.readline().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, sys.stdin.readline().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()
abc = [iln() for _ in range(N)]
dp = [[0 for _ in range(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][j] = max(dp[i+1][j], dp[i][k]+abc[i][j])

print(max(dp[N]))

Solution (Python):
"""
参考 Xenous
if sortを少なくし、maxで処理
""" 

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

dp_A = [0]*(N) ;dp_A[0] =a[0] 
dp_B = [0]*(N) ;dp_B[0] =b[0] 
dp_C = [0]*(N) ;dp_C[0] =c[0] 



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

Solution (Python):
"""
参考 Xenous
if sortを少なくし、maxで処理
""" 

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

dp_A = [0]*(N) ;dp_A[0] =a[0] 
dp_B = [0]*(N) ;dp_B[0] =b[0] 
dp_C = [0]*(N) ;dp_C[0] =c[0] 



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

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

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

print(max(happy[-1]))

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

def main():
    N = int(input())
    abc = [tuple(map(int, input().split())) for _ in range(N)]
    dp = [[0] * 3 for _ in range(N+1)]
    for i in range(3):
        dp[0][i] = 0
    for i in range(1, N+1):
        for today in range(3):
            for yesterday in range(3):
                if today == yesterday:
                    continue
                dp[i][today] = max(dp[i][today], dp[i-1][yesterday] + abc[i-1][today])
    ans = 0
    for i in range(3):
        ans = max(ans, dp[N][i])
    print(ans)
if __name__ == '__main__':
    main()

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

Solution (Python):
import sys

readline = sys.stdin.readline

def main():
    N = int(input())
    DPa = [0] * N; DPb = [0] * N; DPc = [0] * N
    for i in range(N):
        a, b, c = map(int, readline().split())
        if i == 0:
            DPa[i] = a; DPb[i] = b; DPc[i] = c
        else:
            DPa[i] = max(DPb[i-1], DPc[i-1]) + a
            DPb[i] = max(DPa[i-1], DPc[i-1]) + b
            DPc[i] = max(DPa[i-1], DPb[i-1]) + c

    ans = max(DPa[N-1], DPb[N-1], DPc[N-1])
    print(ans)


if __name__ == "__main__":
    main()

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

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

DP=[[0 for j in range(3)] for k in range(n+1)]
DP[1][0]=action[0][0]
DP[1][1]=action[0][1]
DP[1][2]=action[0][2]
for l in range(1,n+1):
  DP[l][0]=DP[l-1][1]+action[l-1][0]
  DP[l][1]=DP[l-1][0]+action[l-1][1]
  DP[l][2]=DP[l-1][0]+action[l-1][2]
  if DP[l][0]<DP[l-1][2]+action[l-1][0]:
    DP[l][0]=DP[l-1][2]+action[l-1][0]
  if DP[l][1]<DP[l-1][2]+action[l-1][1]:
    DP[l][1]=DP[l-1][2]+action[l-1][1]
  if DP[l][2]<DP[l-1][1]+action[l-1][2]:
    DP[l][2]=DP[l-1][1]+action[l-1][2]
print(max(max(DP)))

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

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

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

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

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

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

Solution (Python):
if __name__ == "__main__":
    N = int(input())
    dp = [0] * 3

    for day in range(N):
        cur_activities = [int(x) for x in input().split()]

        new_dp = [0] * 3

        for i in range(3):
            for j in range(3):
                if i != j:
                    new_dp[j] = max(new_dp[j], dp[i] + cur_activities[j])

        dp = new_dp

    print(max(dp))

Solution (Python):
import sys

input=sys.stdin.readline

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

dp=[[0 for i in range(0,3)] for j in range(0,N)]
dp[0][0]=max(B[0],C[0])
dp[0][1]=max(A[0],C[0])
dp[0][2]=max(B[0],A[0])
for i in range(1,N):
    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])

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

Solution (Python):

import sys


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    dp = [[0] * 3 for _ in range(N)]
    dp[0][0] = a[0]
    dp[0][1] = b[0]
    dp[0][2] = c[0]

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

    print(max(dp[-1]))



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N)  
    b = [int()] * (N)  
    c = [int()] * (N)  
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, a, b, c)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin

def main():
    n = int(input())
    ary = [list(map(int, stdin.readline().split())) for _ in range(n)]
    dp = [[0 for _ in range(3)] for _ in range(n)]
    for k in range(n):
        for i in range(3):
            if k == 0:
                dp[k][i] = ary[k][i]
            else:
                dp[k][i] = ary[k][i] + max([dp[k-1][j] for j in range(3) if j != i])
    print(max(dp[n-1]))

if __name__ == '__main__':
    main()

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

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

Solution (Python):
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    N = int(input())
    L = [list(map(int,input().split())) for _ in range(N)]
    dp = [[0 for _ in range(3)] for _ in range(N+1)]

    for num,i in enumerate(L[0]):
        dp[0][num] = i

    for i in range(1,N):
        for dp_num,k in enumerate(dp[i-1]):
            for l_num,j in enumerate(L[i]):
                if l_num == dp_num:
                    continue
                dp[i][l_num] = max(k + j,dp[i][l_num])
    print(max(dp[N-1]))

if __name__ == "__main__":
    main()

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

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

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

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

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

ans = 0
for i in range(3):
    ans = max(ans,dp[n][i])
print(ans)

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

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

print(max(dp[-1]))

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    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)

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

    dpa[0] = A[0]
    dpb[0] = B[0]
    dpc[0] = C[0]

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

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


if __name__ == "__main__":
    main()

Solution (Python):
if __name__=='__main__':
	N=int(input())
	happiness=[]
	for i in range(N):
		cost=list(map(int,input().split()))
		happiness.append(cost)
	dp=[[0 for j in range(3)] for i 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]+happiness[i][k])
				else:
					continue
			
	print(max(dp[-1]))

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

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

print(max(dp[-1]))

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

a=[P[0][0]]*N
b=[P[0][1]]*N
c=[P[0][2]]*N

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

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

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

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

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

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

Solution (Python):
n = int(input())
abc = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[-10 ** 10 for _ in range(3)] for _ in range(n+1)]
dp[0] = [0, 0, 0]
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-1][j])

print(max(dp[n]))