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.



Sample input:
3
10 40 70
20 50 80
30 60 90


Sample output:
210

Submission status: Accepted

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

# 初期化
dp = [[0,0,0] for i in range(N)] # (N, 3)
dp[0] = A[0]; 

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

Submission status: Accepted

Solution code:
n = int(input())
play_list = [0, 0, 0]

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

Submission status: Accepted

Solution code:
n = int(input())

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

s = [0] * 3

for a in aa:
    s = [max(s[1], s[2]) + a[0], 
        max(s[0], s[2]) + a[1],
        max(s[0], s[1]) + a[2]
    ]

print(max(s))

Submission status: Accepted

Solution code:
def solve():
    list_of_abc = read()
    result = think(list_of_abc)
    write(result)


def read():
    n = read_int(1)[0]
    list_of_abc = []
    for i in range(n):
        list_of_abc.append(read_int(3))
    return list_of_abc


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(list_of_abc):
    dp = [[0 for abc in range(3)] for n in range(len(list_of_abc))]
    dp[0][0] = list_of_abc[0][0]
    dp[0][1] = list_of_abc[0][1]
    dp[0][2] = list_of_abc[0][2]

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

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


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
A = []
B = []
C = []
for i in range(N):
    tmp_a,tmp_b,tmp_c = map(int,input().split())
    A.append(tmp_a)
    B.append(tmp_b)
    C.append(tmp_c)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    dp = [[0 for i in range(3)] for j in range(n)]

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


    print(max(dp[-1]))


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
M = [None] * N

for i in range(N):
    M[i] = [int(v) for v in input().split()]
    
S = [[0 for _ in range(3)] for _ in range(N)]
S[0][0] = M[0][0]
S[0][1] = M[0][1]
S[0][2] = M[0][2]

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

print(max(S[-1]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())

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

dp = a = [[0 for i in range(3)] for j in range(N)]
dp[0][0] = grid[0][0]
dp[0][1] = grid[0][1]
dp[0][2] = grid[0][2]


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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
abc = list(list(map(int,input().split()))for i in range(N))
DP = [[0,0,0]for i in range(N+1)]
for i in range(N):
    for j in range(3):
        DP[i+1][j] = max(DP[i][:j]+DP[i][j+1:])+abc[i][j]
print(max(DP[-1]))

Submission status: Accepted

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

dp0=[0]*n
dp1=[0]*n
dp2=[0]*n

dp0[0]=s[0][0]
dp1[0]=s[0][1]
dp2[0]=s[0][2]

for i in range(1,n):
    dp0[i]=max(dp1[i-1]+s[i][0],dp2[i-1]+s[i][0])
    dp1[i]=max(dp0[i-1]+s[i][1],dp2[i-1]+s[i][1])
    dp2[i]=max(dp0[i-1]+s[i][2],dp1[i-1]+s[i][2])

print(max(dp0[n-1],dp1[n-1],dp2[n-1]))

Submission status: Accepted

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

if N == 1:
    print(max(inputs[0]))
else:
    # dp[i]には1, 2, 3を選択した時の幸福度の最大値を入れている
    dp = [[0, 0, 0] for _ in range(N)]
    dp[0] = inputs[0]
    for i in range(N):
        dp[i][0] = max(dp[i-1][1] + inputs[i][0], dp[i-1][2] + inputs[i][0])
        dp[i][1] = max(dp[i-1][2] + inputs[i][1], dp[i-1][0] + inputs[i][1])
        dp[i][2] = max(dp[i-1][0] + inputs[i][2], dp[i-1][1] + inputs[i][2])

    print(max(dp[-1]))

Submission status: Accepted

Solution code:
def number():
    return int(input())


def space():
    return list(map(int, input().split()))


N = number()
ABC = [space() 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], dp[i-1][2]) + ABC[i-1][0]
    dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + ABC[i-1][1]
    dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + ABC[i-1][2]
print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())

tasks = []

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

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

for i in range(1,n):
    for j in range(3):
        temp = []
        for k in range(3):
            if j != k:
                temp.append(dp[i-1][k] + tasks[i][j])
        dp[i][j] = max(temp)

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
ad = []
for i in range(n):
    ad.append([int(i) for i in input().split()])

#dp[p][q]
#p = 何日目
#q = p日目にqをした時のp日目までの最大幸福度 <- どれを選んだかが問題にならない
dp = [[0,0,0]]
#ads = []
#tmp = []

for i in range(1,n+1):
    if i == 1:
        a = ad[i-1][0]
        b = ad[i-1][1]
        c = ad[i-1][2]
        dp.append([a,b,c])
    else:
        dp.append([max(dp[i-1][1] + ad[i-1][0],dp[i-1][2] + ad[i-1][0]),max(dp[i-1][0] + ad[i-1][1],dp[i-1][2] + ad[i-1][1]),max(dp[i-1][0] + ad[i-1][2],dp[i-1][1] + ad[i-1][2])])
print(max(dp[n]))

"""
for i in range(3): #最初に選んだのがi
    for j in range(1,n+1): #j日目
        if j == 1:
            dp.append(dp[j-1]+ad[j-1][i])
            former = i
        else:
            if dp[j-1]+ad[j-1][dic[former][0]] <  dp[j-1]+ad[j-1][dic[former][1]]:
                dp.append(dp[j-1]+ad[j-1][dic[former][1]])
                former = dic[former][1]
            else:
                dp.append(dp[j-1]+ad[j-1][dic[former][0]])
                former = dic[former][0]
        #print(former)
    #print(dp[1:])
    ls.append(dp[n])
    dp = [0]
print(max(ls))
"""
"""
for i in range(3):#1日目の選択
    for j in range(2):#2日目の選択
        for k in range(1,n+1): #n日目まで
            if k == 1:
                dp.append(dp[k-1]+ad[k-1][i])
            elif k == 2:
                dp.append(dp[k-1]+ad[k-1][dic[i][j]])
            else:
                if k == 3:
                    former = dic[i][j]
                if dp[k-1]+ad[k-1][dic[former][0]] <  dp[k-1]+ad[k-1][dic[former][1]]:
                    dp.append(dp[k-1]+ad[k-1][dic[former][1]])
                    former = dic[former][1]
                else:
                    dp.append(dp[k-1]+ad[k-1][dic[former][0]])
                    former = dic[former][0]
        #print(i,j)
        #print(dp)
        ls.append(dp[n])
        dp = [0]
print(max(ls))
"""
"""
#dp[p][q]
#p = 何日目
#q = p日目にqをした時のp日目までの最大幸福度
dp = [[0,-1]]
ads = []
tmp = []

former = [[-1,-1]]
dic = {0:[1,2],1:[0,2],2:[0,1]}
ls = []
for i in range(3):#最初の1つ
    for k in range(1,n+1): #n日目まで
        if k == 1:
            ads.append(dp[k-1][0]+ad[k-1][i])
            former.append([i,i])#1日目
        elif k != n:
            #次の日の候補
            alpha = dic[former[k-1][0]]
            beta  = dic[former[k-1][1]]
            former.append([alpha,beta])
            if dp[k-1] + ad[alpha] + ad[dic[alpha][0]] < dp[k-1] + ad[alpha] + ad[dic[alpha][1]]):
                ads.append()
            if dp[k-1] + ad[beta] + ad[dic[beta][0]] < dp[k-1] + ad[beta] + ad[dic[beta][1]]:

            print(dp)
            dp.append(ads)
            ads = []

            tmp = []



        #print(i,j)
        #print(dp)
        ls.append(max(dp[n]))
        dp = [[0,0]]
print(max(ls))
"""

Submission status: Accepted

Solution code:
N = int(input())
values = [[int(i) for i in input().split()] for _ in  range(N)]
dp = [values[0]]
for i in range(N-1):
  dp.append([max(dp[i][1],dp[i][2])+values[i+1][0],max(dp[i][2],dp[i][0])+values[i+1][1],max(dp[i][0],dp[i][1])+values[i+1][2]])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

N = int(input())

a = [0]*N
b = [0]*N
c = [0]*N
dp = [[0 for i in range(N)] for j in range(3)]

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

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

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

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

Submission status: Accepted

Solution code:
from copy import *
from sys import *
from math import *
import queue
from collections import defaultdict,Counter,deque

setrecursionlimit(1000000)

#dp[x][y] 最終日にyを選択した際のx日目までの最大の幸福度
def main():
	n = int(input())
	abc = [list(map(int, input().split())) for i in range(n)]
	dp = [[0,0,0]]
	for i in range(1,n+1):
		temp = []
		temp.append(max(dp[i-1][1], dp[i-1][2]) + abc[i-1][0])
		temp.append(max(dp[i-1][0], dp[i-1][2]) + abc[i-1][1])
		temp.append(max(dp[i-1][1], dp[i-1][0]) + abc[i-1][2])
		dp.append(temp)
	print(max(dp[-1]))

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	#競プロ用のQueue
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)

class Stack():
	#怯プロ用のStack
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)

main()

Submission status: Accepted

Solution code:
n = int(input())
grid = [[0 for i in range(3)] for j in range(n)]
dp = [[0 for i in range(3)] for j in range(n)]

for i in range(n):
    grid[i] = list(map(int, input().split(" ")))
    
for i in range(n):
    for j in range(3):
        if i == 0 and j == 0:
            dp[i][j] = grid[0][0]
        elif i == 0:
            dp[i][j] = max(grid[i][j], dp[i][j - 1])
        else:
            if (j == 0):
                dp[i][j] = max(grid[i][j] + dp[i-1][1], grid[i][j] + dp[i-1][2])
            elif (j == 1):
                dp[i][j] = max(grid[i][j] + dp[i-1][0], grid[i][j] + dp[i-1][2])
            else:
                dp[i][j] = max(grid[i][j] + dp[i-1][0], grid[i][j] + dp[i-1][1])
                
        
print(max(dp[n - 1][0], max(dp[n - 1][2], dp[n - 1][1])))

Submission status: Accepted

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

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

# DP[i][j] ・・・　最後にj+1番目(j=0,1,2)を選んだ時のi+1日目(i=0,1,…)の最大値
DP[0] = C[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]+C[i][j])

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

Submission status: Accepted

Solution code:

N = int(raw_input())
H = []

for _ in xrange(N):
    a, b, c = map(int, raw_input().split())
    H.append([a, b, c])

dp = [[0]*3 for __ in xrange(N)]

for i in xrange(0, N):
    for j in xrange(3):
        if i==0:
            dp[i][j] = H[0][j]
        else:
            dp[i][j] = max(dp[i-1][j-1]+H[i][j], dp[i-1][j-2]+H[i][j])

print max(dp[N-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
l=[list(map(int,input().split())) for _ in [0]*n]
dp=[[-float("inf") for _ in [0]*3] for _ in [0]*n]
for i in range(3):
    dp[0][i]=l[0][i]
for i in range(1,n):
    for j in range(3):
        dp[i][j]=max(dp[i-1][(j+1)%3]+l[i][j],dp[i-1][(j+2)%3]+l[i][j])
print(max(dp[n-1][i] for i in range(3)))

Submission status: Accepted

Solution code:
n = int(input())
dp = [[0 for _ in range(3)] for _ in range(n+1)]
abc = []

for i in range(1, n+1):
    abc.append([int(x) for x in input().split()])

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] + abc[i][k])

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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

happiness[0] = abc[0]

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
n = int(input())

fa, fb, fc = 0, 0, 0

for _ in range(n):
    a, b, c = map(int, input().split())
    fa, fb, fc = a + max(fb, fc), b + max(fa, fc), c + max(fa, fb)

print(max(fa, fb, fc))

Submission status: Accepted

Solution code:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
dp = [[0 for i in range(3)] for j in range(n)]
dp[0]= a[0]

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
for i in range(N):
        a,b,c = map(int,input().split())
        if i == 0:
                preA = a
                preB = b
                preC = c
        else:
                A = max(preB + a, preC + a)
                B = max(preA + b, preC + b)
                C = max(preA + c, preB + c)
                preA = A
                preB = B
                preC = C
print(max(preA, preB, preC))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    happiness = []
    for i in range(N):
        happiness.append([int(num) for num in input().split()])

    hap_total = [[0] * 3 for _ in range(N)]
    hap_total[0] = [happiness[0][0], happiness[0][1], happiness[0][2]]


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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

dpA = [ABC[0][0]]*N
dpB = [ABC[0][1]]*N
dpC = [ABC[0][2]]*N

for i in range(1, N):
        dpA[i] = max(dpB[i-1] + ABC[i][0], dpC[i-1] + ABC[i][0])
        dpB[i] = max(dpA[i-1] + ABC[i][1], dpC[i-1] + ABC[i][1])
        dpC[i] = max(dpA[i-1] + ABC[i][2], dpB[i-1] + ABC[i][2])
print(max(dpA[N-1], dpB[N-1], dpC[N-1]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    N = readi()
    x = readi(N, 3)
    dp = arr(N + 1, 3)
    for i in range(N):
        for j in range(3):
            dp[i + 1][j] = max(
                dp[i + 1][j], dp[i][(j + 1) % 3] + x[i][j], dp[i][(j + 2) % 3] + x[i][j]
            )
    print(max(dp[N]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    N = readi()
    x = readi(N, 3)
    dp = arr(N + 1, 3)
    for i in range(N):
        dp[i + 1][0] = max(dp[i + 1][0], dp[i][1] + x[i][0], dp[i][2] + x[i][0])
        dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + x[i][1], dp[i][2] + x[i][1])
        dp[i + 1][2] = max(dp[i + 1][2], dp[i][0] + x[i][2], dp[i][1] + x[i][2])
    print(max(dp[N]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve(N, ABCs):
    ans = [ABCs[0]]
    for i in range(1, N):
        ans.append([
            max(ans[i - 1][1], ans[i - 1][2]) + ABCs[i][0],
            max(ans[i - 1][0], ans[i - 1][2]) + ABCs[i][1],
            max(ans[i - 1][0], ans[i - 1][1]) + ABCs[i][2],
        ])
    return max(ans[-1])

if __name__ == "__main__":
    N = int(input())
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, ABCs))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
abcN = [list(map(int, input().split())) for i in range(N)]

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

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

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

Submission status: Accepted

Solution code:
MAX_VAL = 9999999999
MIN_VAL = 0
n = int(input())
abc = []
for i in range(n):
    abc.append(list(map(int, input().split())))
c0 = [[x, MIN_VAL, MIN_VAL] for x in abc[0]]
for i in range(1, n):
    c1 = [max(x) for x in c0]
    for j in range(3):
        for k in range(3):
            if j != k:
                c0[j][k] = abc[i][j] + c1[k]
            else:
                c0[j][k] = MIN_VAL
print(max([max(x) for x in c0]))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())

A = np.zeros([N, 3], dtype='int32')

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

dp = np.zeros([N+1, 3], dtype='int32')

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

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

Submission status: Accepted

Solution code:
def solve():
  N = int(input())
  
  activity = []
  for i in range(N):
    a, b, c = [int(j) for j in input().split()]
    activity.append((a, b, c))

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

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

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

solve()

Submission status: Accepted

Solution code:
n = int(input())
a, b, c = [],[],[]
dp = [[0 for i in range(3)] for j in range(n)]

for i in range(n):
    v1, v2, v3 = map(int, input().split())
    a.append(v1)
    b.append(v2)
    c.append(v3)

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-1], dp[i-1][2] + a[i-1])
    # dp[i][1] = max(dp[i-1][0] + b[i-1], dp[i-1][2] + b[i-1])
    # dp[i][2] = max(dp[i-1][0] + c[i-1], dp[i-1][1] + c[i-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("dpx: " + str(dp[n-1][0]))
# print("dpy: " + str(dp[n-1][1]))
# print("dpz: " + str(dp[n-1][2]))

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

Submission status: Accepted

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

    dp_a, dp_b, dp_c = 0, 0, 0

    for a, b, c in abc:
        ai = max(dp_b, dp_c) + a
        bi = max(dp_a, dp_c) + b
        ci = max(dp_a, dp_b) + c
        dp_a, dp_b,dp_c = ai, bi, ci

    print(max(dp_a, dp_b, dp_c))

Submission status: Accepted

Solution code:
n = int(input())

dpa, dpb, dpc = 0, 0, 0

for i in range(n):
    a, b, c = map(int, input().split())
    dpa, dpb, dpc = max(dpb, dpc) + a, max(dpa, dpc) + b, max(dpa, dpb) + c

print(max(dpa, dpb, dpc))

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(10**8)

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

l = [[None for _ in range(3)] for _ in range(N+10)]
# @lru_cache(maxsize=None)
def dp(i, use):
    if i == -1:
        return 0
    if l[i][use] != None:
        return l[i][use]
    max_num = 0
    for k in range(3):
        if k == use:
            continue
        max_num = max(max_num, dp(i-1, k)+ABC[i][use])
    l[i][use] = max_num 
    return max_num

print(max(dp(N-1, m) for m in range(3)))

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline())
values = []

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


for i in range(1,n+1):
    values = list(map(int, sys.stdin.readline().split()))
    
    if i == 1:
        dp[1] = values
        
    else:
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + values[0]
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + values[1]
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + values[2]
        
print(max(dp[n]))

Submission status: Accepted

Solution code:
N = int(input())
wa, wb, wc = [0] * 3
for a, b, c in (map(int, input().split()) for _ in range(N)):
  wa, wb, wc = a + max(wb, wc), b + max(wa, wc), c + max(wa, wb)
print(max(wa, wb, wc))

Submission status: Accepted

Solution code:
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] * (N + 1),[0] * (N + 1),[0] * (N + 1)]

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