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 solve():
    N = int(input())
    happiness = [[0] * 3 for i in range(N)]
    for i in range(N):
        tmpa, tmpb, tmpc = map(int, input().split())
        happiness[i][0] = tmpa
        happiness[i][1] = tmpb
        happiness[i][2] = tmpc

    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][j] + happiness[i][k], dp[i+1][k])

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
nes = [list(map(int,input().split())) for i in range(N)]
A = [0]
B = [0]
C = [0]
for i in range(N) :
    a = nes[i][0] + max(B[-1],C[-1])
    b = nes[i][1] + max(A[-1],C[-1])
    c = nes[i][2] + max(B[-1],A[-1])
    A += [a]
    B += [b]
    C += [c]
print(max(A[-1],B[-1],C[-1]))

Submission status: Accepted

Solution code:
n = int(input())
data = []
a=0
b=1
c=2
dp = [[0 for i in range(3)] for j in range(n)]
for i in range(n):
    data.append(list(map(int, input().split())))

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

Submission status: Accepted

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

c = [[0 for j in range(3)] for i in range(n)]
for i in range(3):
    c[0][i]  = hh[0][i]

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

Submission status: Accepted

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista

def wakacje(): 
    N = wczytaj_liste()[0]
    punkty_za_zadania = [None]*N
    for i in range(N):
        punkty_za_zadania[i] = wczytaj_liste()
    wczoraj = [0, 0, 0]
    dzisaj = [None]*3
    for i in range(N):
        dzisaj[0] = max(wczoraj[1]+punkty_za_zadania[i][0], wczoraj[2]+punkty_za_zadania[i][0])
        dzisaj[1] = max(wczoraj[0]+punkty_za_zadania[i][1], wczoraj[2]+punkty_za_zadania[i][1])
        dzisaj[2] = max(wczoraj[0]+punkty_za_zadania[i][2], wczoraj[1]+punkty_za_zadania[i][2])
        wczoraj = dzisaj[:]
    print (max(wczoraj))
    
wakacje()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
INF = float('inf')
N = int(input())
H = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for _ in range(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] + H[i][k])

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

print(ans)

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

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

print(max(z[-1]))

Submission status: Accepted

Solution code:
n=int(input())
prev=[0,0,0]
for i in range(n):
    dp=[0,0,0]
    c=list(map(int,input().split()))
    for i in range(3):
        for j in range(3):
            if i!=j:
                dp[i]=max(dp[i],prev[j]+c[i])
    prev=dp[:]
print(max(prev))

Submission status: Accepted

Solution code:
N=int(input())
A=[]

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


for i in range(N):
    B,C, D = map(int, input().split())
    A.append([B,C, D])
#print(A)

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    dp = [[0] * 3 for _ in range(N+1)]
    for i in range(1, N+1):
        # i 日目の行動による幸福度
        happiness = [int(i) for i in input().split()]
        # i-1 日目の行動
        for j in range(3):
            # i 日目の行動
            for k in range(3):
                # i日目とi-1日目の行動が同じ場合はスキップ
                if j == k:
                    continue
                # i日目に行動kを選んだときの最大値
                dp[i][k] = max(dp[i][k], dp[i-1][j] + happiness[k])
    ans = max(dp[-1])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
ABC= [list(map(int,input().split())) for i in range(n)]
#ABC[i][j]はi回目にj=0,1,2でabcの点数が出る。
A=[0]*n
B=[0]*n
C=[0]*n
A[0],B[0],C[0]=ABC[0]
for i in range(1,n):
    A[i]=max(B[i-1],C[i-1])+ABC[i][0]
    B[i]=max(A[i-1],C[i-1])+ABC[i][1]
    C[i]=max(B[i-1],A[i-1])+ABC[i][2]
print(max(A[n-1], B[n-1],C[n-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 前日の行動と、当日の行動から最大値を求める。


N = int(input())
dp = [[0, 0, 0] for i in range(N)]
H = []


for i in range(N):
    l = list(map(int, input().split()))
    H.append(l)

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

for i in range(1, N):
    # 現在の選択肢
    for k in range(3):
        # 過去の選択肢
        for j in range(3):
            if j == k:
                continue
            else:
                dp[i][j] = max(dp[i][j], (dp[i - 1][k] + H[i][j]))
print(max(dp[N - 1]))

Submission status: Accepted

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

#dp[day][その日Aを選択した場合,Bを選択,Cを選択]=累積幸福度の最大値
dp = [[0] * 3 for _ in range(N+2)]

for i in range(1,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]

print(max(dp[N]))

Submission status: Accepted

Solution code:
import sys
import numpy as np

n = int(input())
days = []
for _ in range(n):
    day = list(map(int, input().split()))
    days.append(day)
dp = [[10000] * 3 for _ in range(n)]

# 1日目
dp[0][0] = days[0][0]
dp[0][1] = days[0][1]
dp[0][2] = days[0][2]


for d in range(1,n):
    for i in range(3):
        mx = 0
        for j in range(3):
            if i != j:
                mx = max(dp[d-1][j] + days[d][i],mx)
                # mx = max(dp[d][i], dp[d-1][j]+ days[d][i])
        dp[d][i] = mx
print(max(dp[-1]))

Submission status: Accepted

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

dp = [[0]*3 for i in range(N + 1)]
for i in range(N):
    for k in range(3):
        dp[i + 1][k] = max(dp[i + 1][k], dp[i][(k + 1) % 3] + days[i][k], dp[i][(k - 1) % 3] + days[i][k])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())
L = []

for i in range(N):
  l = list(map(int,input().split()))
  L.append(l)
  
dp = [[0,0,0] for i in range(N)]
dp[0] = [L[0][0],L[0][1],L[0][2]]

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

Submission status: Accepted

Solution code:
"""
NTC here
"""
import sys
input= sys.stdin.readline
# import t  hreading
# setrecursionlimit(10**6)
# threading.stack_size(2**26)

def iin(): return int(input())
def lin(): return list(map(int, input().split()))

# range = xrange
# input = raw_input

def main():
    n = iin()
    Q = [lin() for i in range(n)]
    ans = [[0, 0, 0] for i in range(n+1)] 
   # print(ans)
    for i in range(n-1, -1, -1):
        for j in range(3):
            ans[i][j]=Q[i][j]+max([
                ans[i+1][k] for k in range(3) if k!=j
            ])
  #  print(ans)
    print(max(ans[0]))

        



                









        
main()
#threading.Thread(target=main).start()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
 
# 入力
#A, B, X = map(int, input().split())
N = int(input())
V = []
for _ in range(N) :
  S = str(input())
  V.append(list(map(int, S.split())))

#print (V)

#N日目にA,B,C,それぞれを選んだときの最大の幸福度
dp = [[0 for _ in range(3)] for _ in range(N+1)]

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


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

Submission status: Accepted

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

dp = [[0,0,0] for _ in range(N+1)]
dp[1] = [abc[1][0], abc[1][1], abc[1][2]]
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][j]
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 = [abc[0]]  # On the first day, Taro chooses [A, B, C]
for i in range(1, N):
    ith_day = [
        max(dp[-1][1], dp[-1][2]) + abc[i][0],
        max(dp[-1][2], dp[-1][0]) + abc[i][1],
        max(dp[-1][0], dp[-1][1]) + abc[i][2],
    ]
    dp.append(ith_day)
print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys

def resolve():
        input = sys.stdin.readline
        N=int(input().rstrip())

        A=[[0] * 3 for i in range(N)]
        for i in range(N):
            A[i][:]=list(map(int,input().rstrip().split()))

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

        for i in range(1,N,1):
            for j in range(3):
                for k in range(3):
                    if(k!=j):
                        dp[i][j]=max(dp[i][j],dp[i-1][k]+A[i][j])
       
        print(max(dp[N-1]))
          
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3
10 40 70
20 50 80
30 60 90"""
        output = """210"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1
100 10 1"""
        output = """100"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1"""
        output = """46"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

dp = [[0, 0, 0] for _ in range(N)]
a, b, c = 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 = map(int, input().split())

    dp[i][0] = max(dp[i][0], dp[i - 1][1] + a, dp[i - 1][2] + a)
    dp[i][1] = max(dp[i][1], dp[i - 1][0] + b, dp[i - 1][2] + b)
    dp[i][2] = max(dp[i][2], dp[i - 1][0] + c, dp[i - 1][1] + c)

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

Submission status: Accepted

Solution code:
def main():

    n = int(input())
    # activities = [[int(x) for x in input().split()] for _ in range(n)]
    dp = [0] * 3
    # dp[i] - the total happiness such that we did activity i on the last considered day
    for day in range(n):
        new_dp = [0] * 3
        activities = [int(x) for x in input().split()]
        for i in range(3):
            for j in range(3):
                if i != j:
                    new_dp[j] = max(new_dp[j], dp[i] + activities[j])
        dp = new_dp
    print(max(dp))


main()

Submission status: Accepted

Solution code:
def main():

    n = int(input())
    activities = [[int(x) for x in input().split()] for _ in range(n)]
    dp = [0] * 3
    # dp[i] - the total happiness such that we did activity i on the last considered day
    for day in range(n):
        new_dp = [0] * 3
        for i in range(3):
            for j in range(3):
                if i != j:
                    new_dp[j] = max(new_dp[j], dp[i] + activities[day][j])
        dp = new_dp
    print(max(dp))


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

dp = []
for i in range(N):
	dp.append([0,0,0])

dp[0] = hap[0]

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

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

Submission status: Accepted

Solution code:
N = int(input())
DP = [[0]*3]*N
abc = [0] * N
for i in range(N):
    L = list(map(int,input().split()))
    abc[i] = L
for i,value in enumerate(abc):
    dp = [0]*3
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[k] = max(dp[k],DP[i-1][j] + value[k])
    DP[i] = dp
print(max(DP[-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)]
# print(dp)
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:
N = int(input())
ABC = [list(map(int,input().split())) for _ in range(N)]
hap = [[0,0,0] for _ in range(N)]
hap[0] = ABC[0]
for j in range(1,N):
  for i1,i2,i3 in [[0,1,2],[1,2,0],[2,0,1]]:
    hap[j][i2] = max(hap[j][i2], hap[j-1][i1]+ABC[j][i2])
    hap[j][i3] = max(hap[j][i3], hap[j-1][i1]+ABC[j][i3])
print(max(hap[-1][:]))

Submission status: Accepted

Solution code:
N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N)]
# dp[i][j] i日目にjをする 0:a 1:b 3:c
dp = [[0] * 3 for _ in range(N)]

# 初期化
for j in range(3):
    dp[0][j] = ABC[0][j]

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

Submission status: Accepted

Solution code:
import sys


def main(N, matrix):
    row = len(matrix)
    col = len(matrix[0])
    res = []
    for i in range(row):
        res.append([0] * col)
    for action in range(3):
        res[0][action] = matrix[0][action]

    for day in range(1, N):
        for action in range(3):
            res[day][action] = matrix[day][action]
            for prev_action in [a for a in range(3) if a != action]:
                res[day][action] = max(res[day][action], res[day-1][prev_action] + matrix[day][action])

    print max(res[N - 1])


if __name__ == '__main__':
  N, matrix = None, []
  matrix = []
  for i, line_ in enumerate(sys.stdin):
    line = line_.strip()
    if line:
        if not i:
            N = int(line.strip())
        else:
            H = map(int, line.strip().split())
            matrix.append(H)
  if N is not None and matrix:
    main(N, matrix)

Submission status: Accepted

Solution code:
def calc_happiness(h):
    n = len(h)

    states = [[None, None, None] for i in range(n)]
    states[0] = h[0]
    for i in range(1, n):
        states[i][0] = h[i][0] + max(states[i-1][1], states[i-1][2])
        states[i][1] = h[i][1] + max(states[i-1][0], states[i-1][2])
        states[i][2] = h[i][2] + max(states[i-1][0], states[i-1][1])
    return max(states[n-1][0], states[n-1][1], states[n-1][2])

if __name__ == "__main__":
    n = int(input())
    h = [[]] * n
    for day in range(n):
        h[day] = list(map(int, input().split(" ")))
    res = calc_happiness(h)
    print(res)

Submission status: Accepted

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

def vacation(n, cost):
    res = []
    for i in range(n):
        res.append([-1,-1,-1])

    for i in range(3):
        res[0][i] = cost[0][i]
        for day in range (1, n ):
            for action in range(3):
                res[day][action] = cost[day][action]
                for prev_action in range(3):
                    if prev_action == action:
                        continue
                    res[day][action] = max(res[day][action], res[day-1][prev_action] + cost[day][action])
    #print(res[0][i])
    #print(res[n-1][i])
    #print(res)
    print(max(res[n-1]))

def main():
    lines = []
    for line in sys.stdin:
        lines.append([int(i) for i in line.strip().split(' ')])
    n = lines[0][0]
    gains = lines[1:]
 
    #print(n)
    #print(gains)
    vacation(n, gains)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def solution():
    # result array for calculation for optimal cost for every stone
    res = [[-1 for x in range(3)] for y in range(n)]
    res[0] = a[0]
    for i in range(1,n):
        # going through the all days
        for j in range(3):
            # calucaltion for every possible actions, but skipping the same activity
            # picked current activity is j, let us get options from non j and get max of them
            # it will be a cost for j
            # do it for every

            #searching for best previous happines
            bph = -1
            for o in range(3):
                #skipping the same activity
                if o==j:
                    continue
                bph = max(bph, res[i-1][o])
            #print("res = {} a = {}".format(res, a))
            #print("i={} j={}".format(i, j))
            res[i][j] = max(res[i][j], bph + a[i][j])

    return max(res[-1][0],res[-1][1],res[-1][2])


if __name__ == "__main__":
    n = int(input())

    a = [[None for x in range(3)] for y in range(n)]

    for i in range(n):
        row = list(map(int, input().split(" ")))
        for j in range(3):
            a[i][j] = row[j]

    #print("n = {} a = {}".format(n, a))
    if n == 1:
        print(max(a[0][0],a[0][1],a[0][2]))
    else:
        print(solution())

Submission status: Accepted

Solution code:
def vacation(n, cost):
    res = [[0]*3 for i in range(n)]
    for i in range(3):
        res[0][i] = cost[0][i]
    for d in range(1, n):
        for a in range(3):
            res[d][a] = cost[d][a]
            for pa in range(3):
                if pa != a:
                    res[d][a] = max(res[d][a], res[d-1][pa]+cost[d][a])
    return max(res[-1])

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

    print(vacation(n, cost))

if __name__ == "__main__":
    main()

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[0][0] = abc[0][0]
dp[0][1] = abc[0][1]
dp[0][2] = abc[0][2]
#dp[j][i]はj番目でiを選んだ時の最大値
for j in range(n-1):
    dp[j+1][0] = max(dp[j][1],dp[j][2])+abc[j+1][0]
    dp[j+1][1] = max(dp[j][0],dp[j][2])+abc[j+1][1]
    dp[j+1][2] = max(dp[j][0],dp[j][1])+abc[j+1][2]
print(max(dp[n-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a=[]
b=[]
c=[]
for i in range(n):
    tmpa,tmpb,tmpc = map(int,input().split())
    a.append(tmpa)
    b.append(tmpb)
    c.append(tmpc)

#dp[i][j] : i日目にjを行った時の幸福度の最大値
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], dp[i-1][2]) + a[i-1]
    dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i-1]
    dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i-1]

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

Submission status: Accepted

Solution code:
INF = float("inf") #const
MOD = 10**9+7 #const
MAX = 510000 #const

def main():
    n = int(input())
    h = [list(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:
                    dp[i+1][k] = max(dp[i+1][k],dp[i][j]+h[i][k])

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF = int(1e10)

N = int(input())
A, B, C = [None], [None], [None]

for _ in range(N):
    a, b, c = list(map(int, input().split()))
    A.append(a)
    B.append(b)
    C.append(c)

# compute DP
DP = [[0 for _ in range(3)] for _ in range(N + 1)]
DP[1][0] = A[1]
DP[1][1] = B[1]
DP[1][2] = C[1]

# day 2 to N
for d in range(2, N + 1):
    # print(DP[d-1], DP[d])
    DP[d][0] = max(DP[d-1][1], DP[d-1][2]) + A[d]
    DP[d][1] = max(DP[d-1][0], DP[d-1][2]) + B[d]
    DP[d][2] = max(DP[d-1][0], DP[d-1][1]) + C[d]

print(max(DP[N][:]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
act = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0] * 3 for _ in range(N)]
dp[0][0] = act[0][0]
dp[0][1] = act[0][1]
dp[0][2] = act[0][2]
for i in range(N - 1):
  for j in range(3):
    dp[i + 1][j] = max(dp[i][(j + 1) % 3], dp[i][(j + 2) % 3]) + act[i + 1][j]
print(max(dp[-1]))

Submission status: Accepted

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

if len(abcList) == 1:
    print(max(abcList[0][0], abcList[0][1], abcList[0][2]))
else:
    for i in range(1, N):
        dp.append([abcList[i][0] + max(dp[i - 1][1], dp[i - 1][2]),
                   abcList[i][1] + max(dp[i - 1][0], dp[i - 1][2]),
                   abcList[i][2] + max(dp[i - 1][0], dp[i - 1][1])])
    print(max(dp[-1]))

Submission status: Accepted

Solution code:
# Vacation

N = int(input())
a,b,c = [],[],[]
for _ in range(N):
	ai,bi,ci = map(int, input().split())
	a.append(ai)
	b.append(bi)
	c.append(ci)

def mymax(a,b):
	if a>b:
		return a
	else:
		return b
		
dp = [[0]*(N+1) for _ in range(3)]

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

ans = 0
for i in range(3):
	if dp[i][N] > ans:
		ans = dp[i][N]
print(ans)

Submission status: Accepted

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

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

for i in range(1, n):
    for j in range(3):
        for k in range(3):
            if j == k:
                pass
            else:
                dp[i][j] = max(dp[i][j], dp[i - 1][k] + lst[i][j])

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

Submission status: Accepted

Solution code:
# Vacation
dp=[0,0,0]
n=int(input())
for i in range(n):
    a,b,c=map(int,input().split())
    #ｘに進める大きい方を採用しておけばいい
    dp = [max(dp[1],dp[2])+a, #aに進める選択肢のうち大きい方
          max(dp[0],dp[2])+b,
          max(dp[1],dp[0])+c]
print(max(dp))
"""
i 日目にとりうる選択肢が何通りかあって、
愚直に全探索すると O(2n)O(2n) とか O(3n)O(3n) とか O(Kn)O(Kn) とかになる場面では
「dp[ i ] := 最初の i 日間での最適解」の形の DPの検討はアリ。
"""

Submission status: Accepted

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

Dp = [[] for _ in range(n)]


for i in range(3):
    Dp[0].append(S[0][i])

for i in range(1, n):
    #当日の選択
    for j in range(3):
        #当日選んでいない2つの選択肢に基づくDp
        New_Dp = []
        #1日前の選択
        for k in range(3):
            if j==k:
                continue
            else:
                new_dp = Dp[i-1][k] + S[i][j]
                New_Dp.append(new_dp)
        dp = max(New_Dp)
        Dp[i].append(dp)

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

Submission status: Accepted

Solution code:
from sys import stdin,stdout

n = int(stdin.readline())
a = []
for i in range(n):
    x,y,z = map(int,stdin.readline().split())
    a.append([x,y,z])
dp = [[0,0,0] for i in range(n)]
dp[0] =  [a[0][0],a[0][1],a[0][2]] 
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] )
ans = max(dp[n-1])
stdout.write(str(ans))

Submission status: Accepted

Solution code:
n = int(input())
prevA, prevB, prevC = 0, 0, 0
for i in range(n):
    a,b,c = map(int, input().split())
    act_a_on_ith_day = a + max(prevB, prevC)
    act_b_on_ith_day = b + max(prevA, prevC)
    act_c_on_ith_day = c + max(prevA, prevB)
    prevA, prevB, prevC = act_a_on_ith_day, act_b_on_ith_day, act_c_on_ith_day
print(max(prevA, prevB, prevC))

Submission status: Accepted

Solution code:
N = int(input())
a = [tuple(map(int, input().split())) for i in range(N)]
#dp[i][j]=i日目にjをするときの最大
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][j] = max(dp[i+1][j], dp[i][k]+a[i][j])

print(max(dp[N]))

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

Submission status: Accepted

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

dp1 = abc[0]
dp2 = [0, 0, 0]

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

print(max(dp1))

Submission status: Accepted

Solution code:
N = int(input())
activity = [[0, 0, 0] for _ in range(10**5+10)]

for i in range(N):
    activity[i] = [int(i) for i in input().split()]

dp = [[0, 0, 0] for _ in range(10**5+10)]

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] + activity[i][k])

print(max(dp[N]))

Submission status: Accepted

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

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

for i in range(1, N):
    dp[i][0] = max(dp[i-1][1] + abc[i][0], dp[i-1][2] + abc[i][0])
    dp[i][1] = max(dp[i-1][0] + abc[i][1], dp[i-1][2] + 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())
A = [list(map(int,input().split())) for _ in range(N)]
A.insert(0,0)
dp = [[0 for _ in range(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]+A[i][j],dp[i-1][(j+2)%3]+A[i][j])
print(max(dp[N]))

Submission status: Accepted

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

N = int(input())
pa,pb,pc=0,0,0
for i in range(N):
  a,b,c=map(int,input().split())
  ta=max(pb,pc)+a
  tb=max(pa,pc)+b
  tc=max(pa,pb)+c
  pa,pb,pc=ta,tb,tc
print(max(pa,pb,pc))