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())
d=[]
for i in range(n):
    ai,bi,ci=map(int,input().split())
    d.append([ai,bi,ci])

if n==1:
    print(max(d[0][0],d[0][1],d[0][2]))
    exit()
    

ap=d[0][0]
bp=d[0][1]
cp=d[0][2]

for i in range(1,n):
    a=max(bp+d[i][0],cp+d[i][0])
    b=max(ap+d[i][1],cp+d[i][1])
    c=max(ap+d[i][2],bp+d[i][2])

    ap=a
    bp=b
    cp=c
    

print(max(a,b,c))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
A, B, C = list(map(int, input().split()))

for i in range(N-1):
    a, b, c = list(map(int, input().split()))

    a += max(B, C)
    b += max(A, C)
    c += max(A, B)

    A, B, C = a, b, c

print(max(A, B, C))

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 n in range(N):
	for j in range(3):
		for k in range(3):
			if j == k:
				continue
			dp[n + 1][j] = max([dp[n + 1][j], dp[n][k] + ABC[n][j]])
	#print(dp)
print(max(dp[N]))

Submission status: Accepted

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

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

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

Submission status: Accepted

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


if __name__ == '__main__':
    ans = c()
    print(ans)

Submission status: Accepted

Solution code:
def larger(x, y):
	if x > y: return x
	return y

N = int(input())
dpa = [0]
dpb = [0]
dpc = [0]
for i in range(0, N):
	a, b, c = map(int, input().split())
	if i == 0:
		dpa.append(a)
		dpb.append(b)
		dpc.append(c)
	else:
		newa = larger(dpb[-1], dpc[-1])+a
		newb = larger(dpa[-1], dpc[-1])+b
		newc = larger(dpa[-1], dpb[-1])+c
		dpa.append(newa)
		dpb.append(newb)
		dpc.append(newc)
print(larger(larger(dpa[-1], dpb[-1]), dpc[-1]))

Submission status: Accepted

Solution code:
n = int(input())

a,b,c = [],[],[]

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

prea, preb, prec = a[0], b[0], c[0]

for i in range(1, n):
    prea, preb, prec = max(preb, prec) + a[i], max(prea, prec) + b[i], max(preb, prea) + c[i]

print(max(prea, preb, prec))

Submission status: Accepted

Solution code:
N = int(input())

abc = [list(map(lambda x: int(x), input().split())) for _ in range(N)]

happy = [[0] * 3 for _ in range(N)]
for i in range(3):
	happy[0][i] = abc[0][i]

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

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

Submission status: Accepted

Solution code:
N = int(input())

abc = [list(map(lambda x: int(x), input().split())) for _ in range(N)]

happy = [[0] * 3 for _ in range(N)]
for i in range(3):
	happy[0][i] = abc[0][i]

for i in range(1, N):
	for j in range(3):
		for k in range(3):
			if j != k and happy[i][j] < happy[i - 1][k]:
				happy[i][j] = happy[i - 1][k]
		happy[i][j] += abc[i][j]

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

Submission status: Accepted

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

happy = [abc[0]]

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

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

Submission status: Accepted

Solution code:
N = int(input())

a_s, b_s, c_s = [], [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    a_s.append(a)
    b_s.append(b)
    c_s.append(c)

dp = [{} for _ in range(N+1)]
dp[0]["a"] = a_s[0]
dp[0]["b"] = b_s[0]
dp[0]["c"] = c_s[0]

for i in range(1, N):
    dp[i]["a"] = max(dp[i-1]["b"]+a_s[i],
                     dp[i-1]["c"]+a_s[i])
    dp[i]["b"] = max(dp[i-1]["a"]+b_s[i],
                     dp[i-1]["c"]+b_s[i])
    dp[i]["c"] = max(dp[i-1]["a"]+c_s[i],
                     dp[i-1]["b"]+c_s[i])
    # print(dp)
print(max(dp[N-1]["a"], dp[N-1]["b"], dp[N-1]["c"]))

Submission status: Accepted

Solution code:
def sub():
    N = int(input())
    buf_abc = [[int(e) for e in input().split()] for _ in range(N)]
    
    class ZeroDict(dict):
        def __missing__(self, key):
            self[key] = 0 
            return 0

    dp_table = ZeroDict()
    
    dp_table[(1, 0)] = buf_abc[0][0]
    dp_table[(1, 1)] = buf_abc[0][1]
    dp_table[(1, 2)] = buf_abc[0][2]
    for i in range(1, N):
        for j, (k,l) in enumerate([[1,2], [0,2], [0,1]]):
            candi = max(dp_table[(i, k)]+buf_abc[i][j], dp_table[(i, l)]+buf_abc[i][j])
            dp_table[(i+1,j)] = max(candi, dp_table[(i+1,j)])

    vv = [dp_table[(N, i)] for i in range(3)]
    print(max(vv))
    # tt = sorted([(k,v) for k, v in dp_table.items()])
    # for t in tt:
    #     print(t)

sub()

Submission status: Accepted

Solution code:
N = input()
act = []
new = []

for i in range(0,N):
	act.append(raw_input().split(' '))

for i in act:
	tli = []
	for j in i:
		tli.append(int(j))
	new.append(tli)

ans = []

for i in range(0,N):
	emp = [0]*3
	ans.append(emp)


for i in range(0,N):
	for j in range(0,3):
		if(i == 0):
			ans[i][j] = new[i][j]

		else:
			m = -99999	
			for x in range(0,3):
				if(x != j):
					if(m < ans[i-1][x]):
						m = ans[i-1][x]

			ans[i][j] = new[i][j] + m

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

Submission status: Accepted

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

dp = [[0 for i in range(3)] for j 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] = 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:
#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    dp = [[0 for i in range(3)] for j in range(N)]
    
    ml = list(zip(a,b,c))

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

    for i,m in enumerate(ml[1:]):
        i += 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]+m[j])

    print(max(dp[-1]))
    



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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def mi(): return map(int, input().split())


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


def main():
    N = I()
    ABC = llin(N)
    dp = [[0] * 3 for _ in range(N)]
    dp[0] = ABC[0]
    for i in range(1, N):
        for j in range(3):
            dp[i][j] = max((ABC[i][j]+dp[i - 1][k]
                            for k in range(3) if k != j))
    print(max(dp[N-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for i in range(n)]

dp = [[-1] * 3 for i in range(n)]

dp[0][0] = arr[0][0]
dp[0][1] = arr[0][1]
dp[0][2] = arr[0][2]

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

if __name__ == "__main__":
    n = int(input())
    x = range(n)
    dp = [ [0,0,0] for i in x]
    d = []
    for i in x:
        d.append(tuple(map(int,input().split())))

    dp[0][0] = max(d[0][1],d[0][2])
    dp[0][1] = max(d[0][0],d[0][2])
    dp[0][2] = max(d[0][1],d[0][0])

    for i in x:
        if i == 0:
            continue
        
        dp[i][0] = max(dp[i-1][1] + d[i][1] , dp[i-1][2] + d[i][2])
        dp[i][1] = max(dp[i-1][0] + d[i][0] , dp[i-1][2] + d[i][2])
        dp[i][2] = max(dp[i-1][1] + d[i][1] , dp[i-1][0] + d[i][0])
    print(max(dp[n-1]))

Submission status: Accepted

Solution code:
N = int(input())

dp = [[0 for _ in range(3)] for _ in range(N)]
dp[0] = list(map(int, input().split()))
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][2] + b, dp[i-1][0] + 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:
import sys
input = sys.stdin.readline

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

# dp roop
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] + arr[i][k])
print(max(dp[N]))

Submission status: Accepted

Solution code:
n = int(input())
a = [[int(j) for j in input().split()] for i in range(n)]
dp = [[0 for i in range(3)] for j in range(n+1)]
for i in range(n):
  for j in range(3):
    for k in range(3):
      if j == k:
        continue
      if dp[i+1][k] < dp[i][j]+a[i][k]:
        dp[i+1][k] = dp[i][j]+a[i][k]
ans = max(dp[n][0], dp[n][1], dp[n][2])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for i in range(n)]

dp = [[-1] * 3 for i in range(n)]

dp[0][0] = arr[0][0]
dp[0][1] = arr[0][1]
dp[0][2] = arr[0][2]

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
"""
問題
https://atcoder.jp/contests/dp/tasks/dp_c

解説
https://qiita.com/drken/items/dc53c683d6de8aeacf5a#c-%E5%95%8F%E9%A1%8C---vacation
"""
def solve():
    N = int(input())
    A, B, C = [0], [0], [0]
    for i in range(N):
        a, b, c = list(map(int, input().split()))
        A.append(a)
        B.append(b)
        C.append(c)
    
    # dp[i][j] := i日目にjを選んだときの、幸福度の最大値
    # j := 0(A), 1(B), 2(C)
    dp = [[j for j in range(3)] for i in range(N+1)]
    dp[0][0] = 0
    dp[0][1] = 0
    dp[0][2] = 0

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



if __name__ == "__main__":
    solve()

Submission status: Accepted

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

for i in range(1,N+1):
  ai,bi,ci = map(int,input().split())
  
  dp[i][0] = ai + max(dp[i-1][1],dp[i-1][2])
  dp[i][1] = bi + max(dp[i-1][0],dp[i-1][2])
  dp[i][2] = ci + max(dp[i-1][1],dp[i-1][0])
  
print(max(dp[N]))

Submission status: Accepted

Solution code:
N = int(input())
abc=[[int(i) for i in input().split()] for j in range(N)]
dp = [[0]*3 for i in range(N)]
#print(dp)
dp[0] = abc[0]
for i, h in enumerate(abc[1:], 1):
  #print(i,h)
  dp[i][0] = h[0] + max(dp[i-1][1], dp[i-1][2])
  dp[i][1] = h[1] + max(dp[i-1][2], dp[i-1][0])
  dp[i][2] = h[2] + max(dp[i-1][0], dp[i-1][1])
  #print(dp)
print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

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

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
# numpyだとTLE。よって普通の2次元リストで。
# import numpy as np

N = int(input())
# dp = np.array([ [0] * (N+1), [0] * (N+1), [0] * (N+1) ])
dp = [ [0] * (N+1), [0] * (N+1), [0] * (N+1) ]

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

#print(dp[:, N].max())
print(max(dp[0][N], dp[1][N], dp[2][N]))

Submission status: Accepted

Solution code:
n = int(input())
set_abc = {"a", "b", "c"}
abc_array = [{key: int(value) for key, value in zip(set_abc, input().split())} for y in range(n)]

# a or b or cを選んだときの報酬の最高値
dp = [{key: 0 for key in set_abc} for x in range(n)]
res = 0
for index in range(n):
    if index == 0:
        dp[index] = abc_array[index]
        continue
    for key, value in abc_array[index].items():
        candidate_key = set_abc - set(key)
        dp[index][key] = max(dp[index - 1][candidate_key.pop()] + value, dp[index - 1][candidate_key.pop()] + value)

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

Submission status: Accepted

Solution code:
N = int(input())
prev = [0,0,0]
now = [0,0,0]
for i in range(N):
    acts = list(map(int,input().split()))
    for pi in range(3):
        for ni in range(3):
            if pi == ni:
                continue
            now[ni] = max(now[ni], prev[pi]+acts[ni])
    prev = now.copy()
print(max(now))

Submission status: Accepted

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

cost = [a,b,c]
dp = [[0] * N, [0] * N, [0] * N]

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

dp[0][0] = cost[0][0]
dp[1][0] = cost[1][0]
dp[2][0] = cost[2][0]

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

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

Submission status: Accepted

Solution code:
INF = float("inf")

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
input_int = lambda:int(input())
input_ints = lambda:map(int,input().split())
input_ints_list = lambda:list(input_ints())
input_str = lambda:input()
input_strs = lambda:input().split()
input_lines = lambda n,input_func:[input_func() for _ in range(n)]

import importlib
import_module = lambda module_name:importlib.import_module(module_name)

init_array_1dim = lambda value,n:[value]*n # 1次元配列を生成
init_array_2dim = lambda value,n,m:[init_array_1dim(value,n) for _ in range(m)] # 2次元配列を生成

gcd_base = lambda value1,value2:import_module('fractions').gcd(value1,value2) # 最大公約数（2値)
gcd = lambda lst:import_module('functools').reduce(gcd_base,lst) # 最大公約数（リスト）
lcm_base = lambda value1,value2:(value1*value2)//gcd_base(value1,value2) # 最小公倍数(2値)
lcm = lambda lst:import_module('functools').reduce(lcm_base,lst,1) # 最小公倍数(リスト)

permutations = lambda lst,n:import_module('itertools').permutations(lst,n) # 順列
combinations = lambda lst,n:import_module('itertools').combinations(lst,n) # 組み合わせ
product = lambda lst1,lst2:import_module('itertools').product(lst1,lst2) # 二つのリストの直積

round = lambda value:round(value) # 四捨五入
ceil = lambda value:import_module('math').ceil(value) # 切り上げ
floor = lambda value:import_module('math').floor(value) # 切り捨て

# キュー
init_q = lambda lst: import_module('collections').deque(lst)
q_pop = lambda q: q.popleft() # 先頭から取り出し
q_push = lambda q,value:q.appendleft(value) # 先頭に追加（値）
q_pushlist = lambda q,lst:q.extendleft(lst) # 先頭に追加（リスト）
q_append = lambda q,value:q.append(value) # 末尾に追加（値）
q_appendlist = lambda q,lst:q.extend(lst) # 末尾に追加（リスト）

# プライオリティキュー
init_heap = lambda a:import_module('heapq').heapify(a)
heap_push = lambda a,v:import_module('heapq').heappush(a,v)
heap_pop = lambda a:import_module('heapq').heappop(a) # 最小値を取り出す

def solution():
    # ここに実装
    N = input_int()
    abc = input_lines(N,input_ints_list)

    dp = init_array_2dim(-1,3,N)
    for i in range(N):
        if i == 0:
            dp[i][0] = abc[0][0]
            dp[i][1] = abc[0][1]
            dp[i][2] = abc[0][2]
        else:
            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[N-1]))
    
if __name__ == '__main__':
    solution()

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
hya, hyb, hyc = 0, 0, 0
for _ in range(n):
    a, b, c = map(int, input().split())
    ha = a + max(hyb, hyc)
    hb = b + max(hyc, hya)
    hc = c + max(hya, hyb)
    hya =ha
    hyb =hb
    hyc =hc
print(max(ha, hb, hc))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# input
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': None, 'b': None, 'c': None} for _ in range(N+1)]
dp[0]['a'] = 0
dp[0]['b'] = 0
dp[0]['c'] = 0

for i in range(1, N+1):
    dp[i]['a'] = max(dp[i-1]['b'] + A[i-1], dp[i-1]['c'] + A[i-1])
    dp[i]['b'] = max(dp[i-1]['c'] + B[i-1], dp[i-1]['a'] + B[i-1])
    dp[i]['c'] = max(dp[i-1]['a'] + C[i-1], dp[i-1]['b'] + C[i-1])

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

Submission status: Accepted

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


def main():
    N = int(input())
    a = [None] * N
    b = [None] * N
    c = [None] * N
    for i in range(N):
        a[i], b[i], c[i] = [Node(int(ele)) for ele in input().split()]

    a[0].dp_val = a[0].val
    b[0].dp_val = b[0].val
    c[0].dp_val = c[0].val

    for i in range(N-1):
        j = i + 1
        a[j].dp_val = max(b[i].dp_val, c[i].dp_val) + a[j].val
        b[j].dp_val = max(a[i].dp_val, c[i].dp_val) + b[j].val
        c[j].dp_val = max(a[i].dp_val, b[i].dp_val) + c[j].val

    print(max(a[-1].dp_val, b[-1].dp_val, c[-1].dp_val))


class Node():

    def __init__(self, val):
        self.val = val
        self.dp_val = -1


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys

input = sys.stdin.readline

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

dp = np.zeros((N + 1, 3),dtype=int)

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:

def main():
    num = int(input())
    dp = [[0, 0, 0] for i in range(num)]
    dp[0] = list(map(int, input().split()))

    for i in range(1, num):
        data = list(map(int, input().split()))
        for j in range(3):
            dp[i][j] = max(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + data[j]

    print(max(dp[-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
dp = [[0] * 3 for i in range(100010)]

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

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

print(max(dp[N]))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
p = [[int(_) for _ in input().split()] for __ in range(n)]
aem = [p[0][0]]; bem = [p[0][1]]; cem = [p[0][2]]
for i in range(1,n):
    atmp = p[i][0] + max(bem[-1], cem[-1])
    btmp = p[i][1] + max(aem[-1], cem[-1])
    ctmp = p[i][2] + max(aem[-1], bem[-1])
    aem.append(atmp); bem.append(btmp); cem.append(ctmp)
print(max(aem[-1], bem[-1], cem[-1]))

Submission status: Accepted

Solution code:
#vacation
N = int(input())
dp = [[0] * 3 for _ in range(N)]
for i in range(N):

    h = list(map(int, input().split()))
    if i == 0:
        for p in range(3):
            dp[0][p] = h[p]
        continue
    dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + h[0]
    dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + h[1]
    dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + h[2]

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

Submission status: Accepted

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

print(max(dp[N]))

Submission status: Accepted

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

dpa = [0] * (N+1)
dpb = [0] * (N+1)
dpc = [0] * (N+1)

for i in range(1, N+1):
    dpa[i] = max(dpb[i-1], dpc[i-1]) + A[i-1]
    dpb[i] = max(dpc[i-1], dpa[i-1]) + B[i-1]
    dpc[i] = max(dpa[i-1], dpb[i-1]) + C[i-1]

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

N = int(input())

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

a, b, c = map(int, input().rstrip().split(' '))
dp[0][0] = a
dp[0][1] = b
dp[0][2] = c

for i in range(1, N):
    a, b, c = map(int, input().rstrip().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[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
abc = [[0]*3 for i in range(N)]
for n in range(N):
    abc[n][0], abc[n][1], abc[n][2] = map(int, input().split())

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

Submission status: Accepted

Solution code:
n = int(input())

li_action = list()

for _ in range(n):
    li_action.append(list(map(int, input().split())))

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


dp[0][0] = li_action[0][0]
dp[0][1] = li_action[0][1]
dp[0][2] = li_action[0][2]


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

Submission status: Accepted

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

Submission status: Accepted

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

dp = [[-1]*3 for i in range(N)]
import sys
sys.setrecursionlimit(10**9)
def dfs(i,j):
    if i == N:
        return 0
    if dp[i][j] != -1:
        return dp[i][j]
    else:
        if j==0:
            dp[i][j] = max(dfs(i+1,1)+abc[i][1], dfs(i+1,2)+abc[i][2])
        elif j==1:
            dp[i][j] = max(dfs(i+1,0)+abc[i][0], dfs(i+1,2)+abc[i][2])
        else:
            dp[i][j] = max(dfs(i+1,0)+abc[i][0], dfs(i+1,1)+abc[i][1])
        return dp[i][j]
print(max(dfs(0,0), dfs(0,1), dfs(0,2)))

Submission status: Accepted

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

dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0] = [vs[0][0], vs[0][1], vs[0][2]]

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

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