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:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N = II()
    happiness = [[] for _ in range(N)]
    for i in range(N):
        happiness[i] = LI()

    result = [[0 for _ in range(3)] for _ in range(N)]
    result[0] = happiness[0]
    for day in range(1,N):  # 10**5   : 夏休みが 10**5 日もある！ 人生は3万日しかない。
        result[day][0] = max(result[day-1][1] + happiness[day][0], result[day-1][2] + happiness[day][0])
        result[day][1] = max(result[day-1][0] + happiness[day][1], result[day-1][2] + happiness[day][1])
        result[day][2] = max(result[day-1][0] + happiness[day][2], result[day-1][1] + happiness[day][2])

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

main()

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

Submission status: Accepted

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

from collections import defaultdict
dp = defaultdict(int)
for i in range(N):
    dp[i] = [0]*3

for i,v in enumerate(A[0]):
    dp[0][i]=v
    

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

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

Submission status: Accepted

Solution code:
import numpy as np
import sys

stdin = sys.stdin
 
sn = lambda : stdin.readline().rstrip()
an = lambda : map(int, stdin.readline().split())
ni = lambda : int(sn())

N = ni()
ABC = [list(map(int, input().split())) for i in range(N)]
dp = [[0 for i in range(3)] for j in range(N+1)]

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

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = chmax(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:
def p_c():
    N = int(input())
    before = [0] * 3

    for _ in range(N):
        abc = list(map(int, input().split()))
        for i in range(3):
            abc[i] += max(before[(i + 1) % 3], before[(i + 2) % 3])

        before = abc

    print(max(abc))


if __name__ == '__main__':
    p_c()

Submission status: Accepted

Solution code:
def p_c():
    N = int(input())
    before = [0] * 3

    for _ in range(N):
        abc = list(map(int, input().split()))
        idx, mv = max(enumerate(before), key=lambda x: x[1])
        before.pop(idx)
        for i in range(len(abc)):
            if i == idx:
                abc[i] += max(before)
            else:
                abc[i] += mv

        before = abc

    print(max(abc))


if __name__ == '__main__':
    p_c()

Submission status: Accepted

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

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

for i in range(N):
    for pre_play in range(3):
        now_hpns = three_hpnses[pre_play][i]
        for j in range(1,3):
            next_play = (pre_play+j)%3
            next_hpns = now_hpns + abc_list[next_play][i]
            three_hpnses[next_play][i+1] = max(three_hpnses[next_play][i+1], next_hpns)

print(max([hpnses[-1] for hpnses in three_hpnses]))

Submission status: Accepted

Solution code:
n = int(input())
h = []
for i in range(n):
    a,b,c = map(int,input().split())
    h.append((a,b,c))
dp = [[0 for i in range(3)] for i in range(n)]
for i in range(3):
    dp[0][i] = h[0][i]

for i in range(n-1):
    for j in range(3): #now
        for k in range(3): #pre
            if j != k:
                dp[i+1][j] = max(dp[i+1][j], dp[i][k] + h[i+1][j])
print(max(dp[n-1]))

Submission status: Accepted

Solution code:
N = int(input())
dp=[[0,0,0] for i in range(N)]
satisfy=[[int(x) for x in input().split()] for i in range(N)]
dp[0]=satisfy[0]
for i in range(N-1):
    dp[i+1][0] = dp[i][1] + satisfy[i+1][0] if dp[i][1]>dp[i][2] else dp[i][2] + satisfy[i+1][0]
    dp[i+1][1] = dp[i][0] + satisfy[i+1][1] if dp[i][0]>dp[i][2] else dp[i][2] + satisfy[i+1][1]
    dp[i+1][2] = dp[i][0] + satisfy[i+1][2] if dp[i][0]>dp[i][1] else dp[i][1] + satisfy[i+1][2]
print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

N = int(input())
dp1, dp2 = [0] * 3, [0] * 3
for i in range(1, N+1):
    p = list(map(int, input().split()))
    for j in range(3):
        for k in range(3):
            if j != k:
                dp2[j] = max(dp2[j], dp1[k]+p[j])
    dp1 = deepcopy(dp2)
print(max(dp1))

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N = int(input())
    actions = []


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

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

    for day, (a, b, c) in enumerate(actions):
        dp[day + 1][0] = max(dp[day][1], dp[day][2]) + a
        dp[day + 1][1] = max(dp[day][2], dp[day][0]) + b
        dp[day + 1][2] = max(dp[day][0], dp[day][1]) + c

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


sol()

Submission status: Accepted

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

def main():
    N = int(input())
    X = [list(map(int,input().split())) for _ in range(N)]
    dp = [[0,0,0] for _ in range(N)]
    dp[0][0] = X[0][0]
    dp[0][1] = X[0][1]
    dp[0][2] = X[0][2]
    for i in range(N-1):
        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]+X[i+1][k])

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

inf = 10**9+7
dp = [[0] * 3 for _ in range(N+10)]
dp[0] = [ABC[0][0],ABC[0][1],ABC[0][2]]

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

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

Submission status: Accepted

Solution code:
n = int(input())
# h = [int(j) for j in input().split()]
l = []
for i in range(n):
    s = [int(j) for j in input().split()]
    l.append(s)
dp0 = [0 for i in range(n)]
dp1 = [0 for i in range(n)]
dp2 = [0 for i in range(n)]
dp0[0]=l[0][0]
dp1[0]=l[0][1]
dp2[0]=l[0][2]

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

Submission status: Accepted

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

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

Submission status: Accepted

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

a,b,c = 0,1,2
dp = [[0 for _ in range(3)] for _ in range(N + 1)]

for i in range(N):
    for j in range(3):
        beforeMax = max([n for index, n in enumerate(dp[i]) if index != j])
        dp[i + 1][j] = numList[i][j] + beforeMax

print(max(dp[N]))

Submission status: Accepted

Solution code:
n = int(input())

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

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

for i in range(n):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue

            dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + score[i][k])

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

Submission status: Accepted

Solution code:
def max_points(arr):
	dp = [[0] * (len(arr[0])) for _ in range(len(arr) + 1)]

	for i in range(len(arr)):  # days
		for j in range(len(arr[0])):  # activities
			max_before = 0
			for k in range(len(arr[0])):
				if k == j:
					continue
				max_before = max(max_before, dp[i][k])
			dp[i+1][j] = arr[i][j] + max_before
	return max(dp[-1])

  
arr = [[int(x) for x in input().strip().split()]for _ in range(int(input().strip()))]
print(max_points(arr))

Submission status: Accepted

Solution code:
N = int(input())
yesterday = [0, 0, 0]

for i in range(N):
    if i == 0:
        yesterday = list(map(int, input().split()))
    else:
        tmp = [0, 0, 0]
        today = list(map(int, input().split()))

        tmp[0] = max([
            yesterday[1] + today[0],
            yesterday[2] + today[0]
        ])

        tmp[1] = max([
            yesterday[0] + today[1],
            yesterday[2] + today[1]
        ])

        tmp[2] = max([
            yesterday[0] + today[2],
            yesterday[1] + today[2]
        ])

        yesterday = tmp

print(max(yesterday))

Submission status: Accepted

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

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

dpa = [a[0]]+[0]*(n-1)
dpb = [b[0]]+[0]*(n-1)
dpc = [c[0]]+[0]*(n-1)
for i in range(1,n):
    dpa[i] = max(dpb[i-1],dpc[i-1])+a[i]
    dpb[i] = max(dpc[i-1],dpa[i-1])+b[i]
    dpc[i] = max(dpa[i-1],dpb[i-1])+c[i]

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

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

dpa = [a[0]]+[0]*(n-1)
dpb = [b[0]]+[0]*(n-1)
dpc = [c[0]]+[0]*(n-1)
for i in range(1,n):
    dpa[i] = max(dpb[i-1]+a[i],dpc[i-1]+a[i])
    dpb[i] = max(dpc[i-1]+b[i],dpa[i-1]+b[i])
    dpc[i] = max(dpa[i-1]+c[i],dpb[i-1]+c[i])

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

Submission status: Accepted

Solution code:
# AtCoder DP C
def f(A, B, C):
    n = len(A)
    a, b, c = 0, 0, 0 # last activity ending with a/b/c
    for i in range(n):
        a_ = max(b + A[i], c + A[i])
        b_ = max(a + B[i], c + B[i])
        c_ = max(a + C[i], b + C[i])
        a, b, c = a_, b_, c_
    return max(a, b, c)

assert f([10, 20, 30], [40, 50, 60], [70, 80, 90]) == 210

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

Submission status: Accepted

Solution code:
n = int(input())
activity = {'a': [0], 'b': [0], 'c': [0]}
for _ in range(n):
    a, b, c = (map(int, input().split()))
    activity['a'].append(a)
    activity['b'].append(b)
    activity['c'].append(c)

lev_of_hap = {'a': [0]*(n+1), 'b': [0]*(n+1), 'c': [0]*(n+1)}

for i in range(1, n+1):
    lev_of_hap['a'][i] = max(lev_of_hap['b'][i-1], lev_of_hap['c'][i-1]) + activity['a'][i]
    lev_of_hap['b'][i] = max(lev_of_hap['a'][i - 1], lev_of_hap['c'][i - 1]) + activity['b'][i]
    lev_of_hap['c'][i] = max(lev_of_hap['a'][i - 1], lev_of_hap['b'][i - 1]) + activity['c'][i]

ans = max(lev_of_hap['a'][n], lev_of_hap['b'][n], lev_of_hap['c'][n])
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
N = int(input())
w = np.zeros((N, 3), dtype=int)
for i in range(N):
  w[i, :] = list(map(int, input().split()))
dp = np.zeros((N+1, 3), dtype=int)
for i in range(1,N+1):
  dp[i][0] = max([dp[i][0], dp[i-1][1]+w[i-1][0], dp[i-1][2]+w[i-1][0]]) 
  dp[i][1] = max([dp[i][1], dp[i-1][2]+w[i-1][1], dp[i-1][0]+w[i-1][1]]) 
  dp[i][2] = max([dp[i][2], dp[i-1][0]+w[i-1][2], dp[i-1][1]+w[i-1][2]]) 
print(max(dp[N, :]))

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input().strip())
W = [list(map(int, input().strip().split(' '))) for _ in range(N)]
dp = [[0,0,0] for _ in range(N)] # dp[i][kind] i日目に活動[kind]をしたときの最大幸福度
dp[0] = W[0]
for i in range(1,N):
  for kind in range(3):
    dp[i][kind] = max(dp[i-1][(kind+1)%3],dp[i-1][(kind+2)%3]) + W[i][kind]

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * n
b = [0] * n
c = [0] * n
for i in range(n):
    tmp = list(map(int, input().split()))
    a[i] = tmp[0]
    b[i] = tmp[1]
    c[i] = tmp[2]

# dp[i][j]: i+1日目 j を遊んだときの幸福度の総和の最大値
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] + a[i], dp[i - 1][2] + a[i])
    dp[i][1] = max(dp[i - 1][0] + b[i], dp[i - 1][2] + b[i])
    dp[i][2] = max(dp[i - 1][0] + c[i], dp[i - 1][1] + c[i])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())
HappyList = [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 k==j:
                continue
            dp[i+1][k] = max(dp[i+1][k], dp[i][j]+HappyList[i][k])

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

Submission status: Accepted

Solution code:

N = int(input())
abc = []
for n in range(N):
	a,b,c = map(int,input().split())
	abc.append((a,b,c))
#print(abc)

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

#初期値(添字0：a,添字1：b,添字2：cとする)
dp[0][0] = siawaseList[0][0]
dp[0][1] = siawaseList[0][1]
dp[0][2] = siawaseList[0][2] 
for i in range(1,N):
    dp[i][0] = max(dp[i-1][1]+siawaseList[i][0],dp[i-1][2]+siawaseList[i][0])
    dp[i][1] = max(dp[i-1][0]+siawaseList[i][1],dp[i-1][2]+siawaseList[i][1])
    dp[i][2] = max(dp[i-1][0]+siawaseList[i][2],dp[i-1][1]+siawaseList[i][2])
print(max(dp[N-1][0],dp[N-1][1],dp[N-1][2]))

Submission status: Accepted

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

for i in range(n - 2, -1, -1):
    for j in range(2, -1, -1):
        q = -1
        if j == 0:
            arr[i][j] += max(arr[i + 1][1],arr[i+1][2])
        elif j == 2:
            arr[i][j] += max(arr[i + 1][1],arr[i+1][0])
        else:
            arr[i][j] += max(arr[i + 1][0], arr[i+1][2])

print(max(arr[0]))

Submission status: Accepted

Solution code:
N = int(input())
a = [[ int(y) for y in input().split(' ')] for x in range(N)]

h = [[0 for y in range(3)] for x in range(N)]

def max_h(i, j):
    n = [0, 0, 0]
    for k in range(3):
        if k != j:
            n[k] = h[i][k]
    return max(n)

for i in range(N):
    for j in range(3):
        if i == 0:
            h[i][j] = a[i][j]
        else:
            h[i][j] = max_h(i-1, j) + a[i][j]

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N = int(input())

h = []

for _ in range(N):
    h.append(tuple(map(int, input().split())))

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int, input().split())) for i 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:
        dp[i][k] = max(dp[i][k],dp[i-1][j]+A[i-1][k])
print(max(dp[-1]))

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

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [list(map(int, input().split()))] + [[0, 0, 0]] * (n-1)

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())
abc = [list(map(int,input().split())) for _ in range(n)]
dp =[]
for i in range(n+1):
  dp.append([0,0,0])
for j in range(0,n):
  for k in range(0,3):
    for l in range(0,3):
      if k != l:
        dp[j+1][k] = max(dp[j+1][k],dp[j][l]+abc[j][k])
print(max(dp[-1][m] for m in range(0,3)))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
x,y,z = 0,0,0 # 最後に特定アクションを行った場合の最大幸福度
for _ in range(N):
    a,b,c = map(int,input().split())
    x,y,z = max(y,z) + a, max(x,z) + b, max(x,y) + c
answer = max(x,y,z)
print(answer)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


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

    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]+hs[i][j])
    return max(dp[-1])


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]" 
    b = [int()] * (N)  # type: "List[int]" 
    c = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    print(solve(N, a, b, c))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,*l=map(int,open(0).read().split())
A=B=C=0;M=max
for i in range(n):
	A,B,C=l[3*i]+M(B,C),l[3*i+1]+M(C,A),l[3*i+2]+M(A,B)
print(M(A,B,C))

Submission status: Accepted

Solution code:
n,*l=map(int,open(0).read().split())
a=l[::3];b=l[1::3];c=l[2::3]
A,B,C=a[0],b[0],c[0]
M=max
for i in range(1,n):
	A,B,C=a[i]+M(B,C),b[i]+M(C,A),c[i]+M(A,B)
print(M(A,B,C))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

def solve(dpa, dpb, dpc, a, b, c):
    dpa[N - 1] = a[N - 1]
    dpb[N - 1] = b[N - 1]
    dpc[N - 1] = c[N - 1]
    for n in range(N - 2, -1, -1):
        dpa[n] = max(dpb[n + 1], dpc[n + 1]) + a[n]
        dpb[n] = max(dpc[n + 1], dpa[n + 1]) + b[n]
        dpc[n] = max(dpa[n + 1], dpb[n + 1]) + c[n]

nin = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
N = nin[0]
abc = nin[1: 3 * N + 1].reshape(N, 3).T
a = abc[0]
b = abc[1]
c = abc[2]
dpa = np.zeros_like(a)
dpb = np.zeros_like(b)
dpc = np.zeros_like(c)
solve(dpa, dpb, dpc, a, b, c)
print(max(dpa[0], dpb[0], dpc[0]))

Submission status: Accepted

Solution code:
N = int(input())
ABC = list(list(map(int,input().split(' '))) for i in range(N))
DP = list([0,0,0] for i in range(N+1))

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

Submission status: Accepted

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

def main():
    n = int(input())
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(n))
    dp = [[0] * 3 for _ in range(n)]
    dp[0] = A[0]
    for i in range(1, n):  # i-th day
        for j in range(3):  # today
            for k in range(3):  # yesterday
                if j != k:
                    dp[i][j] = max(dp[i][j], dp[i - 1][k] + A[i][j])
    print(max(dp[-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# dpC - Vacation
# 3 variables
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(n))
    a, b, c = A[0]
    for x, y, z in A[1:]:
        a, b, c = x + max(b, c), y + max(a, c), z + max(a, b)
    print(max(a, b, c))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# dpC - Vacation
# 3 variables
def main():
    n = int(input())
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(n))
    a, b, c = A[0]
    for x, y, z in A[1:]:
        a, b, c = x + max(b, c), y + max(a, c), z + max(a, b)
    print(max(a, b, c))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# dpC - Vacation
# 配るDP
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(n))
    dp = [[0] * 3 for _ in range(n)]
    dp[0] = A[0]
    for i in range(n - 1):  # i-th day
        for j in range(3):  # yesterday
            for k in range(3):  # today
                if j != k:
                    dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + A[i + 1][k])
    print(max(dp[-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# dpC - Vacation
# 貰うDP
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    A = tuple(tuple(map(int, input().rstrip().split())) for _ in range(n))
    dp = [[0] * 3 for _ in range(n)]
    dp[0] = A[0]
    for i in range(1, n):  # i-th day
        for j in range(3):  # yesterday
            for k in range(3):  # today
                if j != k:
                    dp[i][k] = max(dp[i][k], dp[i - 1][j] + A[i][k])
    print(max(dp[-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a, b, c = list(map(int, input().split()))

if n > 1:
    for _ in range(n-1):
        a_, b_, c_ = list(map(int, input().split()))
        a_ += max(b, c)
        b_ += max(a, c)
        c_ += max(a, b)
        a, b, c = a_, b_, c_

print(max(a, b, c))
"""
ちゃんと解いたVer
"""

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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(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]) 

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())
d = [[int(e) for e in input().split()] for i in range(n)]
f = [None for i in range(n)]
f[0] = d[0]
for i in range(1, n):
  f[i] = [max(f[i - 1][1] + d[i][0], f[i - 1][2] + d[i][0]), max(f[i - 1][0] + d[i][1], f[i - 1][2] + d[i][1]), max(f[i - 1][0] + d[i][2], f[i - 1][1] + d[i][2])]
print(max(f[n - 1]))

Submission status: Accepted

Solution code:
n = int(input())
a,b,c =map(int, input().split())
if n > 1:
    for _ in range(1, n):
        _a, _b, _c =map(int, input().split())
        _a = _a + max(b , c)
        _b = _b + max(c , a)
        _c = _c + max(a , b)
        a = _a
        b = _b
        c = _c
print(max(a,b,c))