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())
score=[[]for i in range(n)]
for i in range(n):
    x,y,z=map(int,input().split())
    score[i]=(x,y,z)
dp=[[0]*3 for i in range(n+1)]

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
a,b,c = list(map(int,input().split()))
dpa = a
dpb = b
dpc = c
for i in range(1,N):
    dpap = dpa
    dpbp = dpb
    dpcp = dpc
    a,b,c = list(map(int,input().split()))
    dpa = max(dpbp + a, dpcp + a)
    dpb = max(dpap + b, dpcp + b)
    dpc = max(dpap + c, dpbp + c)
print(max(dpa,dpb,dpc))

Submission status: Accepted

Solution code:
N = int(input())
dp = [[0 for _ in range(3)] for i in range(N)]
a,b,c = list(map(int,input().split()))
dpa = a
dpb = b
dpc = c
for i in range(1,N):
    dpap = dpa
    dpbp = dpb
    dpcp = dpc
    a,b,c = list(map(int,input().split()))
    dpa = max(dpbp + a, dpcp + a)
    dpb = max(dpap + b, dpcp + b)
    dpc = max(dpap + c, dpbp + c)
print(max(dpa,dpb,dpc))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
l1=[[] for i in range(N)]
for i in range(N):
    l=list(map(int,input().split()))
    for j in range(len(l)):
        l1[i].append(l[j])
l2=[[] for i in range(N)]
for j in l1[0]:
    l2[0].append(j)
for j in range(1,N):
    l2[j].append(l1[j][0]+max(l2[j-1][1],l2[j-1][2]))
    l2[j].append(l1[j][1]+max(l2[j-1][0],l2[j-1][2]))
    l2[j].append(l1[j][2]+max(l2[j-1][0],l2[j-1][1]))
#print(l2)
print(max(l2[N-1][0],l2[N-1][1],l2[N-1][2]))

Submission status: Accepted

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

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def chmax(a, b):
  if a > b:
    return a
  else:
    return b
n = int(input())
h = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*3 for _ in range(n)]
dp[0] = h[0]
for i in range(n-1):
  for j in range(3):
    for k in range(3):
      if j == k:
        continue
      else:
        dp[i+1][j] = chmax(dp[i+1][j], dp[i][k] + h[i+1][j]) 
      
print(max(dp[n-1]))

Submission status: Accepted

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

N = int(input())

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

# dp[i + 1][j]: i日目までの活動履歴のうち、最終日であるi日目にjを選んだ場合の幸福度の最大値

inf = float("inf")
n_pattern = 3
dp = [[-inf for _ in range(n_pattern)] for i in range(N + 1)]

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

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
n = int(input())

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

f = [[0, 0, 0] for i in range(0, n)]

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

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

Submission status: Accepted

Solution code:
from itertools import permutations
N = int(input())
dp = [[0]*3 for i in range(N)]
dp[0] = list(map(int, input().split()))
for i in range(1,N):
    li = list(map(int, input().split()))
    for x, y in permutations([0,1,2], 2):
        dp[i][x] = max(dp[i][x],dp[i-1][y]+li[x])
print(max(dp[N-1]))

Submission status: Accepted

Solution code:
def zeros(h,*w): return [[0] * w[0]  for _ in range(h)] if w else [[0] * h  for _ in range(h)]

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

dp = zeros(n+1,3)

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

ans = max( dp[n] )

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#c
n=int(input())
N=100100
happy=[[0]*3 for i in range(N)]
dp=[[0]*3 for i in range(N)]
for i in range(1,n+1):
    x,y,z=map(int,input().split())
    happy[i][0]=x
    happy[i][1]=y
    happy[i][2]=z
ans=0
for i in range(1,n+1):
    for place in range(3):
        for place_y in range(3):
            if place==place_y:
                continue
            else:
                dp[i][place]=max(dp[i][place],dp[i-1][place_y]+happy[i][place])

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

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 10**9 +7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]





n = val()
l = []
for i in range(n):l.append(li())
dp = [[0]*3 for i in range(n)]
dp[0] = l[0][:]
for i in range(1,n):
    for j in range(3):
        dp[i][j] = l[i][j] + max(dp[i-1][j-1],dp[i-1][j-2])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inp_list(): return list(map(int, sys.stdin.readline().split()))


def lcm(x, y): return (x * y) // gcd(x, y)


N = inp()
# a = np.zeros((N, 3), dtype=int)
a = [0] * N

for i in range(N):
    a[i] = inp_list()

# dp[i + 1][j]: i日目までの活動で、i日目に活動 j (0: A, 1: B, 2:C) を選んだときの i + 1 日目の幸福の最大値
# dp = np.zeros((N + 1, 3), dtype=int)
dp = [[0] * 3 for _ in range(N + 1)]
for i in range(N):
    for j in range(3): # i 日目の活動
        for k in range(3): # i + 1 日目の活動
            if j == k: continue
            dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + a[i][k])

ans = 0
for i in range(3):
    ans = max(ans, dp[N][i]) # N 日目を終了したときの幸福度 => dp[N][] (N + 1 番目)

# print(a)
# print(dp)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

n = len(happiness)

for i in range(1, n):
    for j in range(3):
        cur = float("-inf")
        for k in range(3):
            if j != k:
                cur = max(happiness[i - 1][k], cur)
        happiness[i][j] += cur
# print(happiness)
print(max(happiness[-1]))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
M = np.zeros((N, 3), dtype='int32')
for i in range(N):
    M[i, 0:3] = list(map(int, input().split()))
H = np.zeros((N, 3), dtype='int32')
H[N - 1, 0] = M[N - 1, 0]
H[N - 1, 1] = M[N - 1, 1]
H[N - 1, 2] = M[N - 1, 2]
for i in range(1, N):
    current_index = N - 1 - i
    H[current_index, 0] = max(M[current_index, 0] +
                              H[current_index + 1, 1], M[current_index, 0] + H[current_index + 1, 2])
    H[current_index, 1] = max(M[current_index, 1] +
                              H[current_index + 1, 0], M[current_index, 1] + H[current_index + 1, 2])
    H[current_index, 2] = max(M[current_index, 2] +
                              H[current_index + 1, 0], M[current_index, 2] + H[current_index + 1, 1])
print(max(H[0, :]))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N = INT()
abc = [LIST() for _ in range(N)]

dp = [[0]*3 for _ in range(N+1)]
for i in range(1, N+1):
	for j in range(3):
		dp[i][j] = max(dp[i-1][(j-1)%3]+abc[i-1][(j-1)%3], dp[i-1][(j+1)%3]+abc[i-1][(j+1)%3])
print(max(dp[N]))

Submission status: Accepted

Solution code:
# 埋める配列
# dp[i][j] : i日目にjに行くときのi日目までの幸福の総和の最大値

# 計算方法
# dp[0][j] = 0
# dp[i][j] = max(dp[i - 1][k] + 増える幸福度)
# j != k となるようにする

# 埋める順序
# iは小さい順jは好きな順

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

dp = [[0 for j in range(3)] for i in range(N + 1)]
#print(dp)

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][j])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())
A, B, C = 0, 0, 0
for _ in range(n):
  a, b, c = map(int, input().split())
  A, B, C = a + max(B, C), b + max(C, A), c + max(A, B)
print(max(A, B, C))

Submission status: Accepted

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x = []
    for _ in range(n):
        a, b, c = map(int, input().split())
        x.append((a, b, c))
    dp0 = [0]*(n+1)
    dp1 = [0]*(n+1)
    dp2 = [0]*(n+1)
    for i in range(1,n+1):
        a, b, c = x[i-1]
        dp0[i] = max(dp1[i-1]+a, dp2[i-1]+a)
        dp1[i] = max(dp0[i-1]+b, dp2[i-1]+b)
        dp2[i] = max(dp0[i-1]+c, dp1[i-1]+c)
    print(max(dp0[n], dp1[n], dp2[n]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x = []
    for _ in range(n):
        a, b, c = map(int, input().split())
        x.append([a, b, c])
    dp = [[0] * 3 for _ in range(n)]
    # i日目の幸福度dp[i-1]
    # まず1日目の幸福度を設定
    dp[0] = [x[0][l] for l in range(3)]
    for i in range(1,n):
        for j in range(3):
            dp[i][j] = max([dp[i-1][k]+x[i][j] for k in range(3) if k != j]+[dp[i][j]])
    print(max(dp[n-1]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# C - Vacation
import numpy as np

N = int(input())
value = np.zeros((N, 3))
for i in range(N):
    value[i, :] = list(map(int, input().split()))
value = value.tolist()

dp = [0]*3

for a, b, c in value:
    dp = [max(dp[1], dp[2])+a, max(dp[0], dp[2])+b, max(dp[0], dp[1])+c]
    
print(int(max(dp)))

Submission status: Accepted

Solution code:
N = int(input())
ans = 0
happy = [[0]*3 for _ in range(N)]
dp = [[0]*3 for _ in range(N+1)]
for i in range(N):
    happy[i][0], happy[i][1], happy[i][2] = map(int, input().split())

for i in range(1, N+1):
    for place in range(3):
        for yes in range(3):
            if place == yes:
                continue
            dp[i][place] = max(dp[i][place], dp[i-1][yes] + happy[i-1][place])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
h = []
for i in range(N):
    abc = [int(x) for x in input().split()]
    h.append(abc)
aDP = [0]*N
bDP = [0]*N
cDP = [0]*N
aDP[0] = h[0][0]
bDP[0] = h[0][1]
cDP[0] = h[0][2]
for i in range(1,N):
    aDP[i] = h[i][0] + max(bDP[i-1],cDP[i-1])
    bDP[i] = h[i][1] + max(aDP[i-1],cDP[i-1])
    cDP[i] = h[i][2] + max(bDP[i-1],aDP[i-1])
print(max(aDP[N-1],bDP[N-1],cDP[N-1]))

Submission status: Accepted

Solution code:
N = int(input())
h = []
for i in range(N):
    abc = [int(x) for x in input().split()]
    h.append(abc)
aDP = [0]*N
bDP = [0]*N
cDP = [0]*N
aDP[0] = h[0][0]
bDP[0] = h[0][1]
cDP[0] = h[0][2]
for i in range(1,N):
    aDP[i] = h[i][0] + max(bDP[i-1],cDP[i-1])
    bDP[i] = h[i][1] + max(aDP[i-1],cDP[i-1])
    cDP[i] = h[i][2] + max(bDP[i-1],aDP[i-1])
print(max(aDP[N-1],bDP[N-1],cDP[N-1]))
#pythonだととおらないのでpypyで通す

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

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 = [(0,0,0)]*(N+1)
    for i in range(1,N+1):
        A = max(dp[i-1][1],dp[i-1][2])+a[i-1]
        B = max(dp[i-1][0],dp[i-1][2])+b[i-1]
        C = max(dp[i-1][0],dp[i-1][1])+c[i-1]
        dp[i]=(A,B,C)
    print(max(dp[-1]))
    return


# 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())
abc = []
for i in range(N):
    abc.append(list(map(int, input().split())))
    
happy = [abc[0]]
for i in range(1,N):
    tmp = happy[i-1]
    max_happy = max(tmp)
    max_happy_index = tmp.index(max_happy)
    
    #最大値が2つある場合
    tmp.remove(max_happy)
    if max(tmp)==max_happy:
        max_happy_index = -1
        
    happy_i = [0,0,0]
    for j in range(3):
        if j==max_happy_index:
            happy_i[j] = max(tmp) + abc[i][j]
        else:
            happy_i[j] = max_happy + abc[i][j]
    happy.append(happy_i)

print(max(happy[-1]))

Submission status: Accepted

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

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

Submission status: Accepted

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

#後者が前者よりも大きい時に更新→DPテーブルを-infに初期化
def chmax(a,b):
    if(a< b):
        return b
    else:
        return a

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

#日数
for i in range(n):
    #前の手
    for late_day in range(3):
        for next_day in range(3):
            if late_day != next_day:
                dp[i][next_day] = chmax(dp[i][next_day], dp[i-1][late_day] + a[i][next_day])

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

Submission status: Accepted

Solution code:
N = int(input())
a, b, c = map(int, input().split())
dp_a = [a]
dp_b = [b]
dp_c = [c]

for _ in range(N-1):
    a, b, c = map(int, input().split())
    former_a, former_b, former_c = dp_a[-1], dp_b[-1], dp_c[-1]
    dp_a.append(max(former_b+a, former_c+a))
    dp_b.append(max(former_c+b, former_a+b))
    dp_c.append(max(former_a+c, former_b+c))

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

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
a = [tuple(int(i) for i in 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):
    for j in range(3):
        comp = []
        for k in range(3):
            if k==j:
                continue
            comp.append(dp[i-1][k] + a[i][j])

        dp[i][j] = max(comp)
print(max(dp[n-1]))

Submission status: Accepted

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

#output
import numpy as np
d = np.array((a, b, c))

dp = np.zeros((3, N), int)
dp[:, 0] = d[:, 0]

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [[-float('Inf')] * 3 for _ in range(N+1)]
dp[0] = [0, 0, 0]

for i in range(1, 1+N):
    for frm_action in range(3):
        for to_action in range(3):
            if frm_action == to_action:
                dp[i][to_action] = max(dp[i][to_action], dp[i-1][frm_action])
            else:
                dp[i][to_action] = max(
                    dp[i][to_action], dp[i-1][frm_action] + A[i-1][to_action])

# print(*dp, sep='\n')
print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())

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

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

print(max(res[n]))

Submission status: Accepted

Solution code:
n=int(input())
a,b,c = map(int,input().split())
aa=[a]
bb=[b]
cc=[c]
for i in range(1,n):
    x=aa[-1]
    y=bb[-1]
    z=cc[-1]
    a,b,c = map(int,input().split())
    aa.append(max(a+y,a+z))
    bb.append(max(b+x,b+z))
    cc.append(max(c+x,c+y))

print(max(aa[-1],bb[-1],cc[-1]))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())
a, b, c = 0, 0, 0
for n in range(N):
    an, bn, cn = map(int, input().split())
    a, b, c = an + max(b, c), bn + max(c, a), cn + max(a, b)
print(max(a, b, c))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
    a.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 k ==j:continue
            dp[i+1][j]=max(dp[i][k]+a[i][j],dp[i+1][j])
ans=max(dp[n][i] for i in range(3))
print(ans)

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

Submission status: Accepted

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

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


submit()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

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

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

dp[0][0]=pit[0][0]
dp[0][1]=pit[0][1]
dp[0][2]=pit[0][2]

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

print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

# dp[i][0] := i日目に0をやった時で最大の幸福度
# 0: a, 1: b, 2: c
# dp[i][0] = max(dp[i - 1][1], dp[i - 1][2])

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

# print('dp', dp)
ans = max(dp[-1])
print(ans)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

dp = []
for _ in range(n):
    dp.append([0,0,0])

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


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

Submission status: Accepted

Solution code:
n=int(input())
a=[[int(i) for i in input().split()] for j in range(n)]
dp=[[0 for i in range(3)] for j in range(n+1)]
for day in range(1,n+1):
    for i in range(3):
        for j in range(3):
            if i!=j:
                dp[day][j]=max(dp[day][j],dp[day-1][i]+a[day-1][j])
print(max(dp[n]))

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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[N - 1]))

Submission status: Accepted

Solution code:
# coding:utf-8
import numpy as np
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
dp = [[0 for i in range(3)] for j in range(n+1)]

#後者が前者よりも大きい時に更新→DPテーブルを-infに初期化
def chmax(a,b):
    if(a< b):
        return b
    else:
        return a

def main():
    #参照するdpテーブルの番号
    for i in range(n):
        #過去にどの手を出しているか
        for j in range(3):
            #次の遷移先
            for k in range(3):
                if (j == k):
                    continue
                else:
                    dp[i+1][k] = chmax(dp[i+1][k], dp[i][j]+ a[i][k])

    res = 0
    for i in range(3):
        res = chmax(res, dp[n][i])

    print(res)

if __name__ == '__main__' :
    main()

Submission status: Accepted

Solution code:
N = int(input())
la, lb, lc = [0] * 3

for i in range(N):
    a, b, c = [int(x) for x in input().split()]
    aa = a + max(lb, lc)
    bb = b + max(lc, la)
    cc = c + max(lb, la)
    la = aa
    lb = bb
    lc = cc

print(max(la, lb, lc))