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

Submission status: Accepted

Solution code:
def main():
  N = int(input())
  ABC = [[int(i) for i in 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[N]))

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

# inputを高速化する。
input = sys.stdin.readline

# 入力
vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]

# lst_happinessをndarrayにする。
arr_happiness_a = np.array([lst_happiness[i][0] for i in range(vacation)])
arr_happiness_b = np.array([lst_happiness[i][1] for i in range(vacation)])
arr_happiness_c = np.array([lst_happiness[i][2] for i in range(vacation)])

# DPのndarrayを作る。
dp_a = np.zeros(vacation, dtype=int)
dp_b = np.zeros(vacation, dtype=int)
dp_c = np.zeros(vacation, dtype=int)

# dpに初期値を入れる。
dp_a[0] = arr_happiness_a[0]
dp_b[0] = arr_happiness_b[0]
dp_c[0] = arr_happiness_c[0]

for i in range(1, vacation):
    dp_a[i] += max(dp_b[i-1], dp_c[i-1]) + arr_happiness_a[i]
    dp_b[i] += max(dp_a[i-1], dp_c[i-1]) + arr_happiness_b[i]
    dp_c[i] += max(dp_a[i-1], dp_b[i-1]) + arr_happiness_c[i]

ans = max(dp_a[vacation-1], dp_b[vacation-1], dp_c[vacation-1])
print(ans)

Submission status: Accepted

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)

# inputを高速化する。
input = sys.stdin.readline

# 入力
vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]

# DPテーブル
# 最大化問題なので0で初期化
dp = [[0 for i in range(3)] for j in range(vacation+1)]

# dpの最大値を更新するための関数
def chmax(a, b):
    if a > b:
        return a
    else:
        return b

# メモ化再帰の関数
def rec(i):
    # DPの値が既に更新されている場合はその値を返す
    for j in range(3):
        if dp[i][j] > 0:
            break
        
        # 再帰の終了条件
        if i == 0:
            dp[i][j] = 0
            break
        
        # i-1 を再帰
        res = 0
        for k in range(3):
            if j == k:
                continue
            res = chmax(res, rec(i-1)[k] + lst_happiness[i-1][k])
            # 結果をメモする
            dp[i][j] = res
    
    return dp[i]

ans = rec(vacation)
ans = max(ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

# inputを高速化する。
input = sys.stdin.readline

# 入力
vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]

# DPテーブル
# 最大化問題なので0で初期化
dp = [[0 for i in range(3)] for j in range(vacation+1)]

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

# dp[i-1][0] から dp[i][1] への遷移
# dp[i-1 ][0] から dp[i][2] への遷移
# dp[i-1][1] から dp[i][0] への遷移
# dp[i-1][1] から dp[i][2] への遷移
# dp[i-1][2] から dp[i][0] への遷移
# dp[i-1][2] から dp[i][1] への遷移
# 各 j (= 0, 1, 2) と各 k (= 0, 1, 2) に対して、j ≠ k ならば
# chmin(dp[i][k], dp[i-1][j] + lst_happiness[i-1][k])
for i in range(1, vacation+1):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i][k] = chmax(dp[i][k], dp[i-1][j] + lst_happiness[i-1][k])


ans = 0
for i in range(3):
    ans = chmax(ans, dp[vacation][i])

print(ans)

Submission status: Accepted

Solution code:
import sys

# inputを高速化する。
input = sys.stdin.readline

# 入力
vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]

# DPテーブル
# 最大化問題なので0で初期化
dp = [[0 for i in range(3)] for j in range(vacation+1)]

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

# dp[i][0] から dp[i + 1][1] への遷移
# dp[i][0] から dp[i + 1][2] への遷移
# dp[i][1] から dp[i + 1][0] への遷移
# dp[i][1] から dp[i + 1][2] への遷移
# dp[i][2] から dp[i + 1][0] への遷移
# dp[i][2] から dp[i + 1][1] への遷移
# 各 j (= 0, 1, 2) と各 k (= 0, 1, 2) に対して、j ≠ k ならば
# chmin(dp[i + 1][k], dp[i [j] + lst_happiness[i][k])
for i in range(vacation):
    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] + lst_happiness[i][k])


ans = 0
for i in range(3):
    ans = chmax(ans, dp[vacation][i])

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
dp = [[0,0,0] for _ 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
    continue
  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][1], dp[i - 1][0])
print(max(dp[N - 1]))

Submission status: Accepted

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

def main():
	N = int(input())
	hpp = []
	for _ in range(N):
		a, b, c = map(int, input().split())
		hpp.append((a, b, c))
			
	DP = [[-1 for _ in range(3)] for _ in range(N+1)]
	DP[0][0] = 0
	DP[0][1] = 0
	DP[0][2] = 0
	
	for i, val in enumerate(hpp):
		a, b, c = val
		DP[i+1][0] = max(DP[i][1], DP[i][2]) + a
		DP[i+1][1] = max(DP[i][0], DP[i][2]) + b
		DP[i+1][2] = max(DP[i][0], DP[i][1]) + c
	
	#print(DP)
	print(max(DP[N][2], DP[N][0], DP[N][1]))
	
if __name__ == "__main__":
	main()

Submission status: Accepted

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

Submission status: Accepted

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

dp = [[0]*3 for _ in range(100010)] 
# dp[i][j] : i日目にj番目の活動をしたときの幸福度の総和
idx = [[1,2],[2,0],[0,1]]

for i in range(3):
    dp[0][i] = a[0][i]
    
for i in range(1,N):
    for j in range(3):
        dp[i][j] = max(dp[i-1][idx[j][0]],dp[i-1][idx[j][1]])+a[i][j]
    
print(max(dp[N-1]))

Submission status: Accepted

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

n=int(input())
a,b,c=map(int,input().split())
for _ in range(n-1):
    a1, b1, c1 = map(int, input().split())
    a,b,c=a1+max(b,c),b1+max(a,c),c1+max(a,b)
print(max(a,b,c))

Submission status: Accepted

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

n=int(input())
a,b,c=map(int,input().split())
for i in range(n-1):
    a1, b1, c1 = map(int, input().split())
    a,b,c=a1+max(b,c),b1+max(a,c),c1+max(a,b)
print(max(a,b,c))

Submission status: Accepted

Solution code:
n=int(input())
a,b,c=map(int,input().split())
for i in range(n-1):
    a1, b1, c1 = map(int, input().split())
    a,b,c=a1+max(b,c),b1+max(a,c),c1+max(a,b)
print(max(a,b,c))

Submission status: Accepted

Solution code:
N = int(input())

x = y = z = 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
print(max(x, y, z))

Submission status: Accepted

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

x = y = z = 0
for a, b, c in A:
  x, y, z = max(y, z)+a, max(x,z)+b, max(x,y)+c
print(max(x, y, z))

Submission status: Accepted

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

x = y = z = 0
for a,b,c in A:
  x,y,z = max(y,z)+a,max(x,z)+b,max(x,y)+c
print(max(x,y,z))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n=int(input())
action=[list(map(int,input().split())) for _ in range(n)]
# happy[i][j] i日目にaction j を選んだ場合の幸福度の最大値
happy=[[0,0,0]for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(3):
        for k in range(3):
            if j!=k:
                happy[i][j]=max(happy[i][j],happy[i-1][k]+action[i-1][j])
# print(happy)
print(max(happy[n]))

Submission status: Accepted

Solution code:
N = int(input())
abcs = [tuple(map(int, input().split())) for i in range(N)]
dp = [[0, 0, 0] for i in range(N)]

for i, abc in enumerate(abcs):
    if i == 0:
        dp[i][0] = abc[0]
        dp[i][1] = abc[1]
        dp[i][2] = abc[2]
    else:
        dp[i][0] = max(dp[i-1][1] + abc[0], dp[i-1][2] + abc[0])
        dp[i][1] = max(dp[i-1][0] + abc[1], dp[i-1][2] + abc[1])
        dp[i][2] = max(dp[i-1][0] + abc[2], dp[i-1][1] + abc[2])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
def solve():
  N = int(input())
  ABC = [[int(i) for i in input().split()] for i in range(N)]
  dp = [[0, 0, 0] for i in range(N)]
  dp[0] = ABC[0]
  for i in range(1, N):
    dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + ABC[i][0]
    dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + ABC[i][1]
    dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + ABC[i][2]
  return max(dp[N - 1])

print(solve())

Submission status: Accepted

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

for i in range(n):
  tmp = list(map(int, input().split()))
  if i == 0:
    dp[i] = tmp
    continue
  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] + tmp[k])

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

Submission status: Accepted

Solution code:
N = int(input())
u = [[0 for i in range(3)] for j in range(N)]
for i in range(N):
    u[i] = [int(j) for j in input().split()]

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [[0, 0, 0] for _ in range(n)]
dp[0][0], dp[0][1], dp[0][2] = map(int, input().split())

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

def main():
    #raw = ["7",
    #       "6 7 8",
    #       "8 8 3",
    #       "2 5 2",
    #       "7 8 6",
    #       "4 6 8",
    #       "2 3 4",
    #       "7 5 1"]
    #N = int(raw[0])
    #data = [list(map(int, x.split())) for x in raw[1:]]
    import sys
    N = int(sys.stdin.readline()[:-1])
    data = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    #
    dp = [[0, 0, 0] for _ in range(N)]
    dp[0] = data[0]
    for i in range(1, N):
        dp[i][0] = max(dp[i-1][1:]) + data[i][0]
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + data[i][1]
        dp[i][2] = max(dp[i-1][:2]) + data[i][2]
    print(max(dp[N-1]))

main()

Submission status: Accepted

Solution code:
import math
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right
# import numpy as np

def s_inpl(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
INF = float("inf")

N = int(input())
act = []
for _ in range(N):
    act_i = inpl()
    act.append(act_i)

dp = [[0, 0, 0] 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] + act[i][j])

ans = 0
for k in range(3):
    ans = max(ans, dp[N][k])

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
L = []
for _ in range(N):
    l = list(map(int,input().split()))
    L.append(l)
dp = [[0 for _ in range(3)] for _ in range(N+1)]
#dp[その日数][最後が'a' or 'b' or 'c'] := 右を満たす最大値
for day in range(N):
    for i in range(3):
        for new in range(3):
            if i != new:
                dp[day+1][new] = max(dp[day][i]+L[day][new] ,dp[day+1][new])
ans = 0
for i in range(3):
    ans = max(ans,dp[N][i])
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

for j in range(3):
    dp[1][j] = qol[0][j]
for i in range(1, N):
    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] + qol[i][j])

print(max(dp[N]))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
H=[tuple(map(int,input().split())) for _ in range(n)]
DP=[[0]*3 for _ in range(n)]
DP[0]=H[0]
for i in range(1,n):
    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]+H[i][j])
print(max(DP[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

dp = [[0]*3 for i in range(N)]
dp[0] = src[0]
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], dp[i-1][k] + src[i][j])
print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
aa, bb, cc = [], [], []
hs = []
for i in range(n):
  a, b, c = map(int, input().split())
  hs.append({})
  hs[i]['a'] = a
  hs[i]['b'] = b
  hs[i]['c'] = c

dp = []
dp.append({})
for x in 'abc':
  dp[0][x] = 0

for i in range(1, n+1):
  dp.append({})
  for current in 'abc':
    vals = []
    for before in 'abc':
      if current == before:
        continue
      vals.append(dp[i-1][before] + hs[i-1][current])
    dp[i][current] = max(vals)

print(max(dp[n].values()))

Submission status: Accepted

Solution code:
N = int(input())
util = [[int(i) for i in input().split()] for _ in range(N)]
"""
memo = [0 for _ in range(N + 1)]
def dp(i, u, rem_i):
    if i == N:
        return u
    elif i == 0:
        ret = max(dp(i + 1, u+util[i][0], 0), dp(i + 1, u+util[i][1], 1), dp(i + 1, util[i][2], 2))
    else:
        index = list({0, 1, 2} - {rem_i})
        ret = max(dp(i + 1, u+util[i][index[0]], index[0]), dp(i + 1, u+util[i][index[1]], index[1]))
    memo[i] = ret
    print(memo)
    return ret

print(dp(0, 0, 3))
"""

memo = [{} for i in range(N)]
for i in range(3):
    memo[-1][i] = util[-1][i]
for i in range(N-2, -1, -1):
    for j in range(3):
        memo[i][j] = util[i][j] + max(memo[i+1][k] for k in range(3) if j != k)
print(max(memo[0].values()))

Submission status: Accepted

Solution code:
N = int(input())
data_ls = list()
memo_ls = [{} for i in range(N)]
for i in range(N):
    data_ls.append([int(i) for i in input().split()])
def dfs(ind, last, cnt):
    if ind == N:
        memo_ls[ind][last] = cnt
        return cnt
    if memo_ls[ind].get(last) is not None:
        return memo_ls[ind][last]
    for i in range(3):
        if i != last:
            res = max(cnt,
                      dfs(ind+1, i, cnt + data_ls[ind][i]))
    memo_ls[ind][i] = res
    return res

for i in range(3):
    memo_ls[-1][i] = data_ls[-1][i]
for ind in range(N-2,-1,-1):
    for i in range(3):
        memo_ls[ind][i] = data_ls[ind][i] + max([memo_ls[ind+1][k] for k in range(3) if i != k])
print(max(memo_ls[0].values()))

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = []
c = []
dp = []
for i in range(n):
    dp.append([0, 0, 0])
for i in range(n):
    a_i, b_i, c_i = [int(i) for i in input().split(' ')]
    a.append(a_i)
    b.append(b_i)
    c.append(c_i)

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

Submission status: Accepted

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

def main():
	N = int(input())
	plan = []
	for _ in range(N):
		a, b, c = map(int, input().split(" "))
		plan.append((a, b, c))
		
	DP = [[-1 for _ in range(3)] for _ in range(N)]
	a, b, c = plan[0]
	DP[0][0] = a
	DP[0][1] = b
	DP[0][2] = c
	
	for i in range(1, len(plan)):
		a, b, c = plan[i]
		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[-1][0], DP[-1][1], DP[-1][2]))
		
if __name__ == "__main__":
	main()

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    dp = [[0, 0, 0] for i in range(N)]
    a0, b0, c0 = [int(n) for n in input().split()]
    dp[0] = [a0, b0, c0]
    for i in range(1, N):
        li = [int(n) for n in input().split()]
        for t in range(3):
            dp[i][t] = max(dp[i-1][(t+1)%3], dp[i-1][(t+2)%3]) + li[t]
    print(max(dp[N-1]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/bin/python3

import math
import os
import random
import re
import sys



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

    dp = []
    for _ in range(n):
        dp.append([])
        for _ in range(3):
            dp[-1].append(0)

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

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

Submission status: Accepted

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

Submission status: Accepted

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

a = [0]*(N+1)
b = [0]*(N+1)
c = [0]*(N+1)

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])
#B
def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])

#C
def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return

#B
def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return

#C
def C():
    n = II()
    abc = LIR(n)
    dp = [0 for i in range(3 * n + 1)]
    dp[0] = abc[0][0]
    dp[1] = abc[0][1]
    dp[2] = abc[0][2]
    for i in range(1,n):
        dp[3 * i] = max(dp[3 * i], dp[3 * (i - 1) + 1] + abc[i][0], dp[3 * (i - 1) + 2] + abc[i][0])
        dp[3 * i + 1] = max(dp[3 * i + 1], dp[3 * (i - 1) + 2] + abc[i][1], dp[3 * (i - 1)] + abc[i][1])
        dp[3 * i + 2] = max(dp[3 * i + 2], dp[3 * (i - 1) + 1] + abc[i][2], dp[3 * (i - 1)] + abc[i][2])
    dp[3 * n] = max(dp)
    print(dp[3*n])

    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I():
    return 
#J

#K

#L

#M
#N
# O
# P
# Q
# R
# S
# T
# U
# V
# W
# X
# Y
# Z


#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
'''input
3
10 40 70
20 50 80
30 60 90
'''
n=int(input())
arr=[list(map(int,input().split())) for i in range(n)]
dp=[[0,0,0] for i in range(n+1)]
for i in range(1,n+1):
	dp[i][0]=arr[i-1][0]+max(dp[i-1][1],dp[i-1][2])
	dp[i][1]=arr[i-1][1]+max(dp[i-1][2],dp[i-1][0])
	dp[i][2]=arr[i-1][2]+max(dp[i-1][1],dp[i-1][0])
print(max(dp[n]))

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys


n = int(input())
abc = [[0 for j in range(3)] for i in range(n)]
for i in range(n):
  abc[i] = list(map(int, sys.stdin.readline().rstrip().split()))


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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_c

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

dp = []
for i in range(N):
    dp.append([- float('inf')] * 3)

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

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

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

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/dp/tasks/dp_c

def c_vacation(n):
    dp=[[0 for i in xrange(3)] for j in xrange(n)]
    dp[0][0],dp[0][1],dp[0][2]=map(int,raw_input().split())
    for i in xrange(1,n):
        a,b,c=map(int,raw_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])
n=int(input())
c_vacation(n)

Submission status: Accepted

Solution code:
# print("Input N")
N = int(input())

# Need a Nx3 array for the DP. Will store the max points after N days,
#   which ends by doing activity 0, 1, or 2.

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

# print("Input the first three activity values")
a, b, c = [int(x) for x in input().split()]
dp[0][0] = a
dp[0][1] = b
dp[0][2] = c

# Now input all the rest and update the dp array
for i in range(1, N):
    # print("Input the next three activity values")
    a, b, c = [int(x) for x in 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]))

Submission status: Accepted

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

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

print(max(dp[N]))

Submission status: Accepted

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

print(max(DP[0][N],DP[1][N],DP[2][N]))

Submission status: Accepted

Solution code:
n=int(input())
a=[[0,0,0]for i in range(n+1)]
for i in range(n):
    s,t,u=map(int,input().split())
    a[i+1][0]=max(a[i][1]+s,a[i][2]+s)
    a[i+1][1]=max(a[i][0]+t,a[i][2]+t)
    a[i+1][2]=max(a[i][1]+u,a[i][0]+u)
print(max(a[n]))