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:
def main():
    import sys
    input = sys.stdin.readline

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

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

    for i in range(N-1):
        a, b, c = ABC[i+1]

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

    print(max(dp[-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

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

    dp[0] = ABC[0]
    ind = [[1, 2], [0, 2], [0, 1]]
    for i in range(1, N):
        a, b, c = ABC[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]))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

for i in range(0,n):
    for j in range(3):
        max_list[i+1][j]=max(max_list[i][(j+1)%3]
        ,max_list[i][(j+2)%3])+satisfis[i][j]

print(max(max_list[-1]))

Submission status: Accepted

Solution code:
n = int(input())
active = [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):
        add = active[i-1][j]
        if(j==0):
            dp[i][j] = max(dp[i-1][2]+add,dp[i-1][1]+add)
        elif(j==1):
            dp[i][j] = max(dp[i-1][0]+add,dp[i-1][2]+add)
        else:
            dp[i][j] = max(dp[i-1][0]+add,dp[i-1][1]+add)

print(max(dp[-1]))

Submission status: Accepted

Solution code:
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N = I()
abc = [LI() for _ in range(N)]
dp = [[0,0,0] for _ in range(N+1)]
for i,j,k in itertools.product(range(N),[0,1,2],[0,1,2]):
    if j==k:
        continue
    if i+1<=N:
        dp[i+1][j] = max(dp[i+1][j],dp[i][k]+abc[i][j])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
t=int(input())
arr=[]
for x in range(t):
    a=list(map(int,input().split()))
    arr.append(a)
dp=[[0 for x in range(3)]for y in range(t)]
dp[0][0]=arr[0][0]
dp[0][1]=arr[0][1]
dp[0][2]=arr[0][2]
for x in range(1,t):
    dp[x][0]=arr[x][0]+max(dp[x-1][1],dp[x-1][2])
    dp[x][1]=arr[x][1]+max(dp[x-1][0],dp[x-1][2])
    dp[x][2]=arr[x][2]+max(dp[x-1][0],dp[x-1][1])



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

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(N):
    dp[i + 1][0] = max(dp[i][1] + A[i], dp[i][2] + A[i])
    dp[i + 1][1] = max(dp[i][0] + B[i], dp[i][2] + B[i])
    dp[i + 1][2] = max(dp[i][0] + C[i], dp[i][1] + C[i])
# print(dp)
ans = 0
for i in range(N + 1):
    for j in range(3):
        ans = max(ans, dp[i][j])
print(ans)

Submission status: Accepted

Solution code:
# dp array
import sys
input = sys.stdin.readline
def chmax(dp, i, k, b):
    if dp[i][k] < b:
        dp[i][k] = b
        return True
    return False
def main():
    N = int(input())
    activities = []
    for _ in range(N):
        activities.append(list(map(int, input().split())))
    dp = [[0 for _ in range(3)] for _ in range(N)]
    dp[0] = activities[0]
    for i in range(1, N):
        for j in range(3):
            for k in range(3):
                if j != k:chmax(dp, i, k, dp[i-1][j]+activities[i][k])
    print(max(dp[-1][0], dp[-1][1], dp[-1][2]))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
li1=[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][1]=max(dp[i+1][1],dp[i][0]+li1[i][1])
    dp[i+1][2]=max(dp[i+1][2],dp[i][0]+li1[i][2])
    dp[i+1][2]=max(dp[i+1][2],dp[i][1]+li1[i][2])
    dp[i+1][0]=max(dp[i+1][0],dp[i][1]+li1[i][0])
    dp[i+1][0]=max(dp[i+1][0],dp[i][2]+li1[i][0])
    dp[i+1][1]=max(dp[i+1][1],dp[i][2]+li1[i][1])
print(max(dp[-1][0],dp[-1][1],dp[-1][2]))

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=[[-10**9]*3 for _ in range(n)]
    
    for i in range(n):
        a,b,c=map(int,input().split())
        t=[a,b,c]
        if i==0:
            dp[0][0],dp[0][1],dp[0][2]=a,b,c 
        else:
            for j in range(3):
                dp[i][j]=max(dp[i-1][j-1]+t[j],dp[i-1][j-2]+t[j])
    #print(dp)

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

Submission status: Accepted

Solution code:
n=int(input())
dp=[0,0,0]
for i in range(n):
	ndp=[0,0,0]
	l=[int(x) for x in input().split()]
	for j in range(3):
		for k in range(3):
			if j!=k:
				ndp[k]=max(ndp[k],dp[j]+l[k])
	#print(ndp)
	dp=ndp
print(max(dp))

Submission status: Accepted

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

# DPテーブルは選択分拡張する
dp = [[0,0,0] for i in range(N+1)]

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # https://qiita.com/drken/items/dc53c683d6de8aeacf5a#dp-%E5%AE%9F%E8%A3%85%E3%81%AE%E9%A0%86%E5%BA%8F
    
    
    INF = 10**10  # INF+INFを計算してもオーバーフローしない範囲で大きく
    
    N = int(input())
    L=[list(map(int,input().split())) for i in range(N+1)]
    # dpテーブル dp[i][j]:=i日目にjを行なって得られる幸福度のmax
    W=3
    dp = [[-1]*3 for _ in range(N+1)]
    """
    初期化の値は，
        最小化問題：INF, 
        最大化問題：-INF（0以上の値しか取らないなら-1, あるいは0でもいいかも)
        数え上げ問題：0
        確率問題：0
        Yes/No判定問題:False
    """
    
    # 初期条件
    for j in range(W):
        dp[0][j] = 0
    
    # ループ
    for i in range(1,N+1):
        for j in range(W):
    
            """
            dp[from] の値の更新が完了していればノード from からノード to への緩和を行っていい．貰うdpであれ配るdpであれ．
            両者の違いを意識すべきケースはcf. 
            https://qiita.com/drken/items/ace3142967c4f01d42e9#%E8%B2%B0%E3%81%86-dp-%E3%81%A8%E9%85%8D%E3%82%8B-dp-%E3%81%AE%E6%AF%94%E8%BC%83
    
            # 遷移式がたくさんある場合この中でさらにforループを回したりする cf. https://atcoder.jp/contests/dp/tasks/dp_b
            """
            for k in range(W):
                if j!=k:
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+L[i-1][k])
    
    # 出力
    print(max(dp[N]))
    
    
    
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
a=[0]*N
b=[0]*N
c=[0]*N
hpa=[0]*N
hpb=[0]*N
hpc=[0]*N
hp=[0]*N

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

hpa[0]=a[0]
hpb[0]=b[0]
hpc[0]=c[0]
hp[0]=max(hpa[0],hpb[0],hpc[0])

for i in range(N-1):
    hpa[i+1]=max(hpb[i]+a[i+1],hpc[i]+a[i+1])
    hpb[i+1]=max(hpa[i]+b[i+1],hpc[i]+b[i+1])
    hpc[i+1]=max(hpa[i]+c[i+1],hpb[i]+c[i+1])
    hp[i+1]=max(hpa[i+1],hpb[i+1],hpc[i+1])

print(hp[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
ABC = [tuple(map(int, input().split())) for _ in range(N)]
dp_a = [0] * (N+1)
dp_b = [0] * (N+1)
dp_c = [0] * (N+1)

for i, (a, b, c) in enumerate(ABC):
  dp_a[i+1] = a + max(dp_b[i], dp_c[i])
  dp_b[i+1] = b + max(dp_a[i], dp_c[i])
  dp_c[i+1] = c + max(dp_a[i], dp_b[i])
print(max(dp_a[N], dp_b[N], dp_c[N]))

Submission status: Accepted

Solution code:
## coding: UTF-8
N = int(input())
l = [list(map(int, input().split())) for _ in range(N)]
dp = [[0, 0, 0] for _ in range(N)]
#print(l)
#print(dp)

dp[0] = l[0]
#print(dp)

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

Submission status: Accepted

Solution code:
N = int(input())
dpa = [0] * N
dpb = [0] * N
dpc = [0] * N

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

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

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
ac = []
for i in range(n):
    i = list(map(int,input().split()))
    ac.append(i)
dp = [[0,0,0] for _ in range(n)]
a,b,c = 0,1,2
dp[0] = ac[0][:]

for j in range(1,n):
    dp[j][a] = max(dp[j-1][b],dp[j-1][c]) + ac[j][a]
    dp[j][b] = max(dp[j-1][a],dp[j-1][c]) + ac[j][b]
    dp[j][c] = max(dp[j-1][a],dp[j-1][b]) + ac[j][c]

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

Submission status: Accepted

Solution code:
import numpy as np


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

dp = np.zeros((n, 3))
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]
ans = max(dp[-1])
print(int(ans))

Submission status: Accepted

Solution code:
import math
from math import sqrt
import sys
from collections import deque, defaultdict
from heapq import heappop,heappush
from copy import deepcopy

INF=10**18
MOD=10**9+7
MAX=10**5+7



def main():
  N=int(input())
  dp=[[0]*3 for i in range(MAX)]
  
  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+1][1]=max(dp[i][2]+b, dp[i][0]+b)
    dp[i+1][2]=max(dp[i][0]+c, dp[i][1]+c)
  print(max(dp[N]))

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import math
from math import sqrt
import sys
from collections import deque, defaultdict
from heapq import heappop,heappush
from copy import deepcopy

INF=10**18
MOD=10**9+7
MAX=10**5+7



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

if __name__=='__main__':
  main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
ac = [list(map(int, input().split())) for _ in range(N)]
# 0 -> a
# 1 -> b
# 2 -> c

se = [[1, 2], [0, 2], [0, 1]]

#dpは(happiness, latest_activity) のタプルを保持する
dp = [[0 for _ in range(3)] for i in range(N + 1)]

for i in range(N):
  for j in range(3):
    dp[i + 1][j] = max(dp[i][se[j][0]] + ac[i][j], dp[i][se[j][1]] + ac[i][j])

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

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
n = int(input())
a,b,c = [0] * n, [0] * n, [0] * n

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

Submission status: Accepted

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

pre_a = 0
pre_b = 0
pre_c = 0
res = 0
for a, b, c in activities:
    tmp_a = max(pre_b, pre_c) + a
    tmp_b = max(pre_a, pre_c) + b
    tmp_c = max(pre_b, pre_a) + c
    pre_a = tmp_a
    pre_b = tmp_b
    pre_c = tmp_c
print(max(pre_a, pre_b, pre_c))

Submission status: Accepted

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

dp = [[0, 0, 0] 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][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]))

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] * 3 for _ in range(n+1)]

for i in range(n):
    dp[i+1][0] = max(dp[i+1][0], max(dp[i][1], dp[i][2])+A[i])
    dp[i+1][1] = max(dp[i+1][1], max(dp[i][0], dp[i][2])+B[i])
    dp[i+1][2] = max(dp[i+1][2], max(dp[i][1], dp[i][0])+C[i])
print(max(dp[n]))

Submission status: Accepted

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

#print(li)

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

dp[0][0] = li[0][0]
dp[0][1] = li[0][1]
dp[0][2] = li[0][2]
#print(dp)

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

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

Submission status: Accepted

Solution code:
import numpy as np
#N,K = map(int,input().split())
N = int(input())
A,B,C = 0,0,0
for i in range(N):
  a,b,c = map(int,input().split())
  A,B,C = a+max(B,C),b+max(A,C),c+max(A,B)
print(max(A,B,C))

Submission status: Accepted

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

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

dp[0] = l[0]

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())

abc=list()
for i in range(n):
    abc.append([int(e) for e in input().split()])

A=[]
B=[]
C=[]

A.append(abc[0][0])
B.append(abc[0][1])
C.append(abc[0][2])

for i in range(1,n):
    a = abc[i][0] + max(B[-1],C[-1])
    b = abc[i][1] + max(A[-1],C[-1])
    c = abc[i][2] + max(A[-1],B[-1])
    A.append(a)
    B.append(b)
    C.append(c)

print(max(A[-1],B[-1],C[-1]))

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	n = int(input())
	pp=[0]*3
	np=[0]*3
	for i in range(n):
		a,b,c=IN()
		np[0] = max(pp[1],pp[2])+a
		np[1] = max(pp[0],pp[2])+b
		np[2] = max(pp[0],pp[1])+c
		pp=np[:]
	#b , c = IN()
	#s = input()
	print(max(pp))
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

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

DP[0][0] = A_B_C[0][0]
DP[0][1] = A_B_C[0][1]
DP[0][2] = A_B_C[0][2]
for i in range(1, N):
    for j in range(3):
        j_a = (j + 1) % 3
        j_b = (j + 2) % 3
        DP[i][j] = max(DP[i-1][j_a], DP[i-1][j_b]) + A_B_C[i][j]

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(max(n_list[-1]))

Submission status: Accepted

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

dp = [[float('inf')] * 3] * n

dp[0][0] = efforts[0][0]
dp[0][1] = efforts[0][1]
dp[0][2] = efforts[0][2]

for i in range(1, n):
    eab = dp[i-1][0] + efforts[i][1]
    eac = dp[i-1][0] + efforts[i][2]
    eba = dp[i-1][1] + efforts[i][0]
    ebc = dp[i-1][1] + efforts[i][2]
    eca = dp[i-1][2] + efforts[i][0]
    ecb = dp[i-1][2] + efforts[i][1]

    dp[i][0] = max(eba, eca)
    dp[i][1] = max(eab, ecb)
    dp[i][2] = max(eac, ebc)

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

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
dp = [[0,0,0] for _ in range(N+1)]
for i in range(1,N+1):
    a,b,c = LI()
    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]))

Submission status: Accepted

Solution code:
import numpy as np

# 何日目かは1~N 添え字は0~N-1
# dp[i][k] i日目でk番目の行動をしたときの幸福度の最大値　（k=0:A, 1:B, 2:C)
# 解答はmax(dp[N-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])

# 入力
N = int(input().strip())
h = []
for i in range(N):
    h.append(list(map(int, input().strip().split())))
H = np.array(h)

# 初期化
dp = np.zeros(N * 3, dtype=np.int).reshape(N, 3)

dp[0][0] = H[0][0]
dp[0][1] = H[0][1]
dp[0][2] = H[0][2]

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

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

Submission status: Accepted

Solution code:
#sys.stdout=open("output.txt", 'w')
#sys.stdout.write("Yes" + '\n')
#from  sys import stdin
#input=stdin.readline
#a = sorted([(n, i) for i, n in enumerate(map(int, input().split()))])
# from collections import Counter
# import sys
#s="abcdefghijklmnopqrstuvwxyz"
#n=int(input())
#n,k=map(int,input().split())
#arr=list(map(int,input().split()))
#arr=list(map(int,input().split
n=int(input())
abc=[]
for i in range(n):
    abc.append(list(map(int,input().split())))
dp=[[-1,-1,-1] for i in range(n)]


for i in range(n):
    if i==0:
        for j in range(3):
            dp[i][j]=abc[i][j]
    else:
        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][2]+abc[i][1],dp[i-1][0]+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:
N= int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
dp = [ list([0,0,0]) for i in range(N)]
for i,l in enumerate(arr):
  if i == 0:
    dp[0] = l
    continue
  dp[i] = [max(dp[i-1][1:])+l[0], max(dp[i-1][0],dp[i-1][2])+l[1],max(dp[i-1][:2])+l[2]]
print(max(dp[-1]))
#print(dp)

Submission status: Accepted

Solution code:
N = int(input())
matrix = []
for i in range(N):
    matrix.append([int(i) for i in input().split()])
ans = -float("inf")
dp = [[0 for i in range(4)] for j in range(len(matrix)+1)]
for i in range(len(matrix)-1,-1,-1):
    for j in range(len(matrix[0])-1,-1,-1):
        dp[i][j] = -float("inf")
        for k in range(3):
            if j != k:
                dp[i][j] = max(dp[i][j],dp[i+1][k]+matrix[i][j])
        ans = max(ans,dp[i][j])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May  2 20:35:42 2020

@author: Kanaru Sato
"""

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

dp = []
for i in range(n):
    dp.append([-1,-1,-1])

for i in range(n):
    if i == 0:
        for j in range(3):
            dp[0][j] = abc[0][j]
    else:
        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]

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

Submission status: Accepted

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

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

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

print(max(dp[-1]))

Submission status: Accepted

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

dp = [[0] * 3 for _ in range(n + 1)]
# dp[i][j] = (i日にjをするような場合の幸福度の最大値)

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

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

Submission status: Accepted

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

n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]
a, b, c = 0, 1, 2

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

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

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

n=int(input())
abc=[]
for i in range(0,n):
    temp=list(map(int,input().split()))
    abc.append(temp)  
dp=[["#"]*3 for i in range(0,n)]

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

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

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

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] * 3 for _ in range(n)]
dp[0] = [A[0], B[0], C[0]]

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

print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    dp = [[float("-inf")] * 3 for _ in range(N)]
    dp[0][0] = a[0]
    dp[0][1] = b[0]
    dp[0][2] = c[0]
    for i in range(1, N):
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i]
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i]
        dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i]
    print(max(dp[-1]))


# Generated by 1.1.6 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))
    solve(N, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
a = []
b = [[0]*3 for k in range(N+1)]

for j in range(N):
    a.append(list(map(int,input().split())))

b[0][0] = 0
b[0][1] = 0
b[0][2] = 0


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

print(max(b[N]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
from collections import Counter
from itertools import permutations, combinations
from fractions import gcd
#from math import gcd
from math import ceil, floor
import bisect
sys.setrecursionlimit(10 ** 6)
inf = float("inf")

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

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

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

def main():
    n = int(input())
    abc = [None] * n
    for i in range(n):
        abc[i] = tuple(map(int, input().split()))

    dp = [[0] * 3 for _ in range(n+1)]
    for i in range(n):
        for j in range(3):
            for k in range(3):
                if j != k:
                    dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + abc[i][k])
    
    ans = 0
    for j in range(3):
        ans = chmax(ans, dp[n][j])
    print(ans)

if __name__ == '__main__':
    main()