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():
    N = int(input())
    abc = [
        list(map(int, input().split()))
        for _ in range(N)
    ]

    ans = f(N, abc)
    print(ans)


def f(N, abc):
    """
    2回連続で同じ活動(abc)を行えない

    1: a or b or c
    2:
        1-a: b or c
        1-b: c or a
        1-c: a or b

    1日目
        aをしたときの幸福最大
        bをしたときの幸福最大
        cをしたときの幸福最大
    2日目
        aをしたときの幸福最大(b, c から)
        bをしたときの幸福最大(c, a から)
        cをしたときの幸福最大(a, b から)
    """
    dp = [[None] * 3 for _ in range(N + 1)]
    dp[0] = [0, 0, 0]
    dp[1] = abc[0]

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

    ans = max(dp[N])
    return ans


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]

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

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):
    h = input().split(" ")
    a.append(int(h[0]))
    b.append(int(h[1]))
    c.append(int(h[2]))
sum_a, sum_b, sum_c = [a[0]], [b[0]], [c[0]]
for i in range(1, n):
    sum_a.append(a[i] + max(sum_b[i - 1], sum_c[i - 1]))
    sum_b.append(b[i] + max(sum_c[i - 1], sum_a[i - 1]))
    sum_c.append(c[i] + max(sum_a[i - 1], sum_b[i - 1]))
print(max(sum_a[n - 1], sum_b[n - 1], sum_c[n - 1]))

Submission status: Accepted

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())
alst = []
blst = []
clst = []
for _ in range(n):
  a, b, c = map(int, input().split())
  alst.append(a)
  blst.append(b)
  clst.append(c)

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

Submission status: Accepted

Solution code:
n = int(input())
x = [list(map(int,input().split())) for _ in range(n)]
a = 0
b = 0
c = 0
for i in range(n):
  pa = a
  pb = b
  pc = c
  X = x[i]
  a = max(pb,pc)+X[0]
  b = max(pc,pa)+X[1]
  c = max(pa,pb)+X[2]
  
print(max([a,b,c]))

Submission status: Accepted

Solution code:
N=int(input())
table=[]
for i in range(N):
    a,b,c=map(int,input().split())
    table.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=table[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(dp1[i-1]+c,dp0[i-1]+c)
print(max(dp0[N],dp1[N],dp2[N]))

Submission status: Accepted

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

dp = [[0] * 3 for _ in range(N)]
dp[0] = Happiness[0][:]
for day in range(1, N):
    dp[day][0] = max(dp[day - 1][1], dp[day - 1][2]) + Happiness[day][0]
    dp[day][1] = max(dp[day - 1][2], dp[day - 1][0]) + Happiness[day][1]
    dp[day][2] = max(dp[day - 1][0], dp[day - 1][1]) + Happiness[day][2]
print(max(dp[N - 1]))

Submission status: Accepted

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


N = int(fin())
happiness_list = tuple(tuple(int(elem) for elem in fin().split()) for _ in range(N))

dp = [0] * 3
for i in range(N):
    next_dp = [0] * 3
    for j in range(3):
        next_dp[j] = max(dp[k] + happiness_list[i][k] for k in range(3) if k != j)
    dp = next_dp
print(max(dp))

Submission status: Accepted

Solution code:
n=int(input())
dp = [[0]*3 for k in range(n+1)]
l = [[0]*3 for k in range(n+1)]
for k in range(1,n+1):
  l[k][0],l[k][1],l[k][2] = map(int,input().split())

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

Submission status: Accepted

Solution code:
import sys
def 解():
    input = sys.stdin.readline
    N = int(input())
    dp = [int(_) for  _ in input().split()]
    for _ in range(N-1):
        a,b,c = [int(_) for  _ in input().split()]
        dp = [max(dp[1]+a,dp[2]+a),max(dp[0]+b,dp[2]+b),max(dp[0]+c,dp[1]+c)]
    print(max(dp))
解()

Submission status: Accepted

Solution code:
n = int(input())
a = list([])
b = list([])
c = list([])

happy = list([0 for i in range(3)] for j in range(n))

for i in range(n):
    aa,bb,cc = list(map(int, input().split()))
    a.append(aa)
    b.append(bb)
    c.append(cc)

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

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

print(max(happy[-1]))

Submission status: Accepted

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

print(max(f[0], f[1], f[2]))

Submission status: Accepted

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


score = [[0] * N for i in range(3)] # N - 1 is used as -1
for i in range(N):
    for dst in range(3):
        tmp = abc[i][dst]
        for src in range(3):
            if dst == src: continue
            elif score[src][i - 1] + tmp > score[dst][i]:
                score[dst][i] = score[src][i - 1] + tmp

# print('#', score)
if N == 1: print(max(abc[-1]))
else: print(max((score[0][-1], score[1][-1], score[2][-1])))

Submission status: Accepted

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

dp = [[0] * (3) for _ in range(N+1)]
for i, (A, B, C) in enumerate(ABCs, 1):
    dp[i][0] = max(dp[i-1][1] + B, dp[i-1][2] + C)
    dp[i][1] = max(dp[i-1][0] + A, dp[i-1][2] + C)
    dp[i][2] = max(dp[i-1][0] + A, dp[i-1][1] + B)

print(max(dp[N]))

Submission status: Accepted

Solution code:
def amax(l):
    am = 0
    am2 = 0
    for i in range(1, len(l)):
        if l[i] > l[am]:
            am2 = am
            am = i
        elif l[i] > l[am2]:
            am2 = i
    return am, am2

def vacation(abc):
    pa, pb, pc = abc[0]
    for i in range(1, len(abc)):
        a, b, c = abc[i]
        patmp, pbtmp, pctmp = pa, pb, pc
        pa = a + max([pbtmp, pctmp])
        pb = b + max([patmp, pctmp])
        pc = c +  max([patmp, pbtmp])

    return max(pa, pb, pc)

N = int(raw_input())
abc = []
for _ in range(N):
    abc.append(map(int, raw_input().split()))

print(vacation(abc))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    m = []

    for _ in range(n):
        row = [int(s) for s in input().split()]
        m.append(row)
    
    print(solve(m))

def solve(m):
    dp = [0, 0, 0]

    for row in m:
        dp = [
            max(dp[1], dp[2]) + row[0],
            max(dp[0], dp[2]) + row[1],
            max(dp[0], dp[1]) + row[2],
        ]
    
    return max(dp)

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
da, db, dc = 0, 0, 0

N = int(input())
for i in range(N):
    a, b, c = [int(_) for _ in input().split()]
    da, db, dc = a + max(db, dc), b + max(da, dc), c + max(da, db)

print(max(da, db, dc))

Submission status: Accepted

Solution code:
N = int(input())
dp = [[0 for _ in range(3)] for _ in range(N + 1)]  # dp[何日目に][何をした] = その時の幸福度

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jan  6 20:37:21 2019

@author: Yamazaki Kenichi
"""

N = int(input())
act = [list(map(int,input().split())) for i in range(N)]
act = [0]+act
u = [0]

for i in range(1,N+1):
    if i == 1:
        u.append(act[1])
    else:
        ui = []
        ui.append(max(u[i-1][1],u[i-1][2])+act[i][0])
        ui.append(max(u[i-1][0],u[i-1][2])+act[i][1])
        ui.append(max(u[i-1][0],u[i-1][1])+act[i][2])
        u.append(ui)
    
ans= max(u[N])
print(ans)

Submission status: Accepted

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

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

for i in range(1, N + 1):

    if i == 1:
        dp[i][0] = a_list[i - 1]
        dp[i][1] = b_list[i - 1]
        dp[i][2] = c_list[i - 1]
    else:
        dp[i][0] = max(dp[i][0], dp[i - 1][1] + a_list[i - 1])
        dp[i][0] = max(dp[i][0], dp[i - 1][2] + a_list[i - 1])
        dp[i][1] = max(dp[i][1], dp[i - 1][0] + b_list[i - 1])
        dp[i][1] = max(dp[i][1], dp[i - 1][2] + b_list[i - 1])
        dp[i][2] = max(dp[i][2], dp[i - 1][0] + c_list[i - 1])
        dp[i][2] = max(dp[i][2], dp[i - 1][1] + c_list[i - 1])

print(max(dp[N]))

Submission status: Accepted

Solution code:
N = int(input())
abc = [list(map(int, input().split(' '))) for i in range(N)]
# これまでの幸福度の最大，但し前回でそれぞれa,b,cをchoice
max_value = [abc[0][0], abc[0][1], abc[0][2]]


for i in range(1, N):
    next_max_value = [0, 0, 0]
    for j in range(3):
        value = max(max_value[(j+1) % 3], max_value[(j+2) % 3])
        next_max_value[j] = value + abc[i][j]
    max_value = next_max_value
print(max(max_value))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
h = []
for _ in range(n):
    h.append(list(map(int, input().split())))
dp = [[0 for _ in range(3)] for _ in range(n)]
for day in range(n):
    if day == 0:
        for act in range(3):
            dp[day][act] = h[day][act]
    else:
        for act in range(3):
            if act == 0:
                dp[day][act] = max(dp[day-1][1], dp[day-1][2]) + h[day][act]
            elif act == 1:
                dp[day][act] = max(dp[day-1][0], dp[day-1][2]) + h[day][act]
            elif act == 2:
                dp[day][act] = max(dp[day-1][0], dp[day-1][1]) + h[day][act]
print(max(dp[n-1]))

Submission status: Accepted

Solution code:
n = int(input())
A = [0 for i in range(n)]
B = [0 for i in range(n)]
C = [0 for i in range(n)]

for i in range(n):
        A[i], B[i], C[i] = map(int, input().split())

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

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

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

Submission status: Accepted

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

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

dp[0] = happiness[0]

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

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

Submission status: Accepted

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

Submission status: Accepted

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

# dp[i][j] := i日目に行動jをとった場合の最大の幸福度。
dp = [[0, 0, 0] for i in range(N)]
dp[0] = Actions[0]

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())
a = []
for i in range(N):
  a.append(list(map(int,input().split())))
A = [a[0][0]]
B = [a[0][1]]
C = [a[0][2]]
if N == 1:
  print(max(A[0],B[0],C[0]))
else:
  for i in range(N-1):
    A.append(max(B[i],C[i])+a[i+1][0])
    B.append(max(A[i],C[i])+a[i+1][1])
    C.append(max(A[i],B[i])+a[i+1][2])
  print(max(A[N-1],B[N-1],C[N-1]))

Submission status: Accepted

Solution code:
import sys

n = int(input())
dp = [0, 0, 0]
for line in sys.stdin.readlines():
    a, b, c = map(int, line.split())
    ndp = [0, 0, 0]
    ndp[0] = max(dp[1], dp[2]) + a
    ndp[1] = max(dp[0], dp[2]) + b
    ndp[2] = max(dp[0], dp[1]) + c
    dp = ndp
print(max(dp))

Submission status: Accepted

Solution code:
import copy

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

NOW=[0,0,0]#最後にしたことそれぞれについての幸福度

NEXT=[None]*3
for i in range(N):
    NEXT[0]=max(NOW[1],NOW[2])+ABC[i][0]
    NEXT[1]=max(NOW[0],NOW[2])+ABC[i][1]
    NEXT[2]=max(NOW[1],NOW[0])+ABC[i][2]

    NOW=copy.copy(NEXT)
    #print(NOW)
        
print(max(NOW))

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))
N = int(input())
A, B, C = [0]*N, [0]*N, [0]*N

for i in range(N):
    A[i], B[i], C[i] = inpl()

DP = [[0]*3 for _ in range(N)]
DP[0] = [A[0], B[0], C[0]]

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

print(max(DP[-1]))

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

dp[0][0], dp[1][0], dp[2][0] = map(int, input().split())

for i in range(1, n):
    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

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

Submission status: Accepted

Solution code:
N = int(input())
dpa = 0
dpb = 0
dpc = 0
for i in range(N):
  a, b, c = map(int, input().split())
  xa = dpb + a
  ya = dpc + a
  xb = dpc + b
  yb = dpa + b
  xc = dpa + c
  yc = dpb + c
  dpa = xa if xa >= ya else ya
  dpb = xb if xb >= yb else yb
  dpc = xc if xc >= yc else yc
print(max(dpa, dpb, dpc))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
abc = []
for _ in range(n):
    abc.append(tuple(li()))
    
happiness = [[0]*(n+1) for _ in range(3)]

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

Submission status: Accepted

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

for i in range(1,n):
  a[i] = max(b[i-1],c[i-1]) + x[i]
  b[i] = max(c[i-1],a[i-1]) + y[i]
  c[i] = max(a[i-1],b[i-1]) + z[i]
print(max(a[-1],b[-1],c[-1]))

Submission status: Accepted

Solution code:
n = int(raw_input())
value = []
for i in xrange(n):
    a, b, c = map(int, raw_input().split())
    value.append((a, b, c))
dp1 = [0 for i in xrange(n)]
dp2 = [0 for i in xrange(n)]
dp3 = [0 for i in xrange(n)]
dp1[0] = value[0][0]
dp2[0] = value[0][1]
dp3[0] = value[0][2]
for i in xrange(1, n):
    a, b, c = value[i]
    dp1[i] = max(dp2[i-1], dp3[i-1]) + a
    dp2[i] = max(dp1[i-1], dp3[i-1]) + b
    dp3[i] = max(dp2[i-1], dp1[i-1]) + c
res = max([dp1[n-1], dp2[n-1], dp3[n-1]])
print res

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Runtime Error

Solution code:
n=int(input())
INF=float('inf')

h=[]
for _ in range(n):
  a,b,c=map(int,input().split())
  h.append([a,b,c])

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

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

Submission status: Runtime Error

Solution code:
n=int(input())
INF=float('inf')

h=[]
for _ in range(n):
  a,b,c=map(int,input().split())
  h.append(a,b,c)

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

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

Submission status: Runtime Error

Solution code:
7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

print(max(dp[N]))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
h = list(map(int, input().split()))
 
DP = [0]
for i in range(N-1):
    act = float("inf")
    for k in range(K):
        if i-k < 0 : break
        act = min(DP[-1-k] + abs(h[i-k]-h[i+1]) , act)
    DP += [act]
 
print(DP[-1])

Submission status: Runtime Error

Solution code:
#問題C
import warnings
warnings.filterwarnings('ignore')
import pandas as pd
import numpy as np

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

h = h.reshape(7,3)

dp = np.array([[0] * h.shape[1]] * h.shape[0])
dp[0,:] = h[0,:]
for i in range(1,N):
    dp[i,0] = max(dp[i-1,1],dp[i-1,2])+h[i,0]
    dp[i,1] = max(dp[i-1,0],dp[i-1,2])+h[i,1]
    dp[i,2] = max(dp[i-1,0],dp[i-1,1])+h[i,2]

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

Submission status: Runtime Error

Solution code:
N=int(input())
sys.setrecursionlimit(1000000000)

ABC=[]
for _ in range(N):
    ABC.append(list(map(int,input().split())))
from functools import lru_cache
@lru_cache(maxsize=None)
def dynam(n):
    if n>1:
        a=max(dynam(n-1)[1]+ABC[n-1][0],
              dynam(n-1)[2]+ABC[n-1][0])
        b=max(dynam(n-1)[0]+ABC[n-1][1],
              dynam(n-1)[2]+ABC[n-1][1])
        c=max(dynam(n-1)[0]+ABC[n-1][2],
              dynam(n-1)[1]+ABC[n-1][2])
        return (a,b,c)
    return tuple(ABC[0])
print(max(dynam(N)))

Submission status: Runtime Error

Solution code:
N=int(input())
ABC=[]
for _ in range(N):
    ABC.append(list(map(int,input().split())))
from functools import lru_cache
@lru_cache(maxsize=None)
def dynam(n):
    if n>1:
        a=max(dynam(n-1)[1]+ABC[n-1][0],
              dynam(n-1)[2]+ABC[n-1][0])
        b=max(dynam(n-1)[0]+ABC[n-1][1],
              dynam(n-1)[2]+ABC[n-1][1])
        c=max(dynam(n-1)[0]+ABC[n-1][2],
              dynam(n-1)[1]+ABC[n-1][2])
        return (a,b,c)
    return tuple(ABC[0])
print(max(dynam(N)))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

def dynam(n):
    if n>1:
        a=max(dynam(n-1)[1]+ABC[n-1][0],
              dynam(n-1)[2]+ABC[n-1][0])
        b=max(dynam(n-1)[0]+ABC[n-1][1],
              dynam(n-1)[2]+ABC[n-1][1])
        c=max(dynam(n-1)[0]+ABC[n-1][2],
              dynam(n-1)[1]+ABC[n-1][2])
        return (a,b,c)
    return tuple(ABC[0])
print(max(dynam(N)))

Submission status: Runtime Error

Solution code:
N=int(input())
ABC=[]
for _ in range(N):
    ABC.append(list(map(int,input().split())))
MAXlist=[]
from functools import lru_cache
@lru_cache(maxsize=None)
def dynam(n):
    if n>1:
        a=max(dynam(n-1)[1]+ABC[n-1][0],
              dynam(n-1)[2]+ABC[n-1][0])
        b=max(dynam(n-1)[0]+ABC[n-1][1],
              dynam(n-1)[2]+ABC[n-1][1])
        c=max(dynam(n-1)[0]+ABC[n-1][2],
              dynam(n-1)[1]+ABC[n-1][2])
        return (a,b,c)
    return tuple(ABC[0])
print(max(dynam(N)))

Submission status: Runtime Error

Solution code:
# C - Vacation AC
import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = []
for _ in range(N):
    a,b,c = map(int,input().split())
    A.append((a,b,c))

# 無限大の値
INF = 10**10

# DP テーブル
dp = [[0]*3 for _ in range(100010)]

# DP テーブル全体を初期化
for i in range(5):
    for j in range(3):
        dp[i][j] = 0# 最大化問題

def rec(v):
    # v-1 日目の活動 (本当は v)
    for w in range(100010):
        print(v,w)
        if dp[v][w] > 0:
       
            return dp[v]
        if v == 0:
            dp[v][w] = 0
         
            return dp[v]
        res = 0
        # v 日目の活動 (本当は v-1)
        for k in range(3):
            if w == k:
               
                continue
            res = max(res,rec(v-1)[k] + A[v-1][w]) # v-1日の活動のところに記録している？
            dp[v][w] = res # ここで kを記録しているのに w を呼び出していた
            print(v,w,k,dp[v])
    return dp[v]

rec(N)
ans = max(dp[N])
print(ans)
# w がずっと 0
# w と k の扱いが逆

Submission status: Runtime Error

Solution code:
# C - Vacation AC
N = int(input())
A = []
for _ in range(N):
    a,b,c = map(int,input().split())
    A.append((a,b,c))

# 無限大の値
INF = 10**10

# DP テーブル
dp = [[0]*3 for _ in range(5)]

# DP テーブル全体を初期化
for i in range(5):
    for j in range(3):
        dp[i][j] = 0# 最大化問題

def rec(v):
    # v-1 日目の活動 (本当は v)
    for w in range(3):
        print(v,w)
        if dp[v][w] > 0:
       
            return dp[v]
        if v == 0:
            dp[v][w] = 0
         
            return dp[v]
        res = 0
        # v 日目の活動 (本当は v-1)
        for k in range(3):
            if w == k:
               
                continue
            res = max(res,rec(v-1)[k] + A[v-1][w]) # v-1日の活動のところに記録している？
            dp[v][w] = res # ここで kを記録しているのに w を呼び出していた
            print(v,w,k,dp[v])
    return dp[v]

rec(N)
ans = max(dp[N])
print(ans)
# w がずっと 0
# w と k の扱いが逆

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<algorithm>
using namespace std;
int max(int a,int b,int c=-1)
{
    if (a>=b && a>=c)
    return a;
    else if(b>=c && b>=a)
    return b;
    else
    return c;
    
}
int main()
{
    int n;
    cin>>n;
    int l[n][3];
    int i,j;
    for(i=0;i<n;i++)
       for(j=0;j<n;j++)
          cin>>l[i][j];
    int memory[n][3];
    memory[0][0]=l[0][0];
    memory[0][1]=l[0][1];
    memory[0][2]=l[0][2];
    for(i=1;i<n;i++)
    {
        for(j=0;j<3;j++)
        {
            if (j==0)
                memory[i][j]=max(memory[i-1][1]+l[i][j],memory[i-1][2]+l[i][j]);
            else if(j==1)
                memory[i][j]=max(memory[i-1][0]+l[i][j],memory[i-1][2]+l[i][j]);
            else
                memory[i][j]=max(memory[i-1][0]+l[i][j],memory[i-1][1]+l[i][j]);
        }
    }
    cout<<max(memory[n-1][0],memory[n-1][1],memory[n-1][2])<<endl;;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> a;
vector<vector<int>> dp;
 int main(){
    long long int N ; cin>>N;
    a.resize(N,vector<int>(3));
    dp.resize(N,vector<int>(3,0));
    for (int i =0; i<N;++i){
        for (int j=0;j<3;++j){
            cin>>a[i][j];
        }
    }

    dp[0][0]=a[0][0];
    dp[0][1]=a[0][1];
    dp[0][2]=a[0][2];
    for (int i=1;i<N;++i){
        for (int j=0;j<3;j++){
            if (j==0){
               dp[i][j] = a[i][j]+max(dp[i-1][1],dp[i-1][2]); 
            }
            if (j==1){
               dp[i][j] =a[i][j]+ max(dp[i-1][0],dp[i-1][2]); 
            }
            if (j==2){
               dp[i][j] =a[i][j]+ max(dp[i-1][0],dp[i-1][1]); 
            }
        }
    }
    cout<<max({dp[N-1][0], dp[N-1][1], dp[N-1][2]});
    
    return 0;
 }

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> a;
vector<vector<int>> dp;
 int main(){
    long long int N ; cin>>N;
    a.resize(N,vector<int>(3));
    dp.resize(N,vector<int>(3,0));
    for (int i =0; i<N;++i){
        for (int j=0;j<3;++j){
            cin>>a[i][j];
        }
    }
    long int ans =0;

    dp[0][0]=a[0][0];
    dp[0][1]=a[0][1];
    dp[0][2]=a[0][2];
    for (int i=1;i<N;++i){
        for (int j=0;j<3;j++){
            if (j==0){
               dp[i][j] = a[i][j]+max(dp[i-1][1],dp[i-1][2]); 
            }
            if (j==1){
               dp[i][j] =a[i][j]+ max(dp[i-1][0],dp[i-1][2]); 
            }
            if (j==2){
               dp[i][j] =a[i][j]+ max(dp[i-1][0],dp[i-1][1]); 
            }
        }
    }
    cout<<max({dp[N-1][0], dp[N-1][1], dp[N-1][2]});
    
    return 0;
 }

Submission status: Runtime Error

Solution code:
import math


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


def chmin(a, b):
    if a <= b:
        return a
    return b


def main():
    nn = int(input())
    hh = list(map(int, input().split()))

    dp = [math.inf]*nn
    dp[0] = 0
    dp[1] = chmin(dp[1],dp[0]+abs(hh[1]-hh[0]))
    for i in range(2,nn):
        dp[i] = chmin(dp[i],dp[i-1]+abs(hh[i]-hh[i-1]))
        dp[i] = chmin(dp[i],dp[i-2]+abs(hh[i]-hh[i-2]))

    print(dp[nn-1])


main()