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

Submission status: Accepted

Solution code:
from sys import stdin as I
N = int(I.readline())
H = [[None,None,None]] + [list(map(int,I.readline().split())) for i in range(N)]
DP = H[1]
for i in range(2,N+1):DP = [max(DP[1],DP[2])+H[i][0],max(DP[0],DP[2])+H[i][1],max(DP[0],DP[1])+H[i][2]]
print(max(DP))

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 i in range(n)]

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

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

Submission status: Accepted

Solution code:

n=int(input())
dp=[[0]*n,[0]*n,[0]*n]

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


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


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


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def main():
    N = I()
    abc = [[0, 0, 0]] * N
    dp = [0] * 3
    dp[0] = 0

    for i in range(N):
        abc[i] = LI()

    for i in range(N):
        dp_next = [0] * 3
        for k in range(3):
            dp_next[k] = max(dp_next[k], dp[k])
            for j in range(3):
                if j != k:
                    dp_next[j] = max(dp[k] + abc[i][j], dp_next[j])
        dp = dp_next
        # print(dp_next)

    print(max(dp))


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

Submission status: Accepted

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

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

for i in range(n):
    p,q,r = map(int,input().split())
    a.append([p,q,r])

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

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

Submission status: Accepted

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

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

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
n=int(input())
a=[[int(i) for i in input().split()]for i in range(n)]
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]+a[i-1][0],dpc[i-1]+a[i-1][0])
    dpb[i]=max(dpa[i-1]+a[i-1][1],dpc[i-1]+a[i-1][1])
    dpc[i]=max(dpa[i-1]+a[i-1][2],dpb[i-1]+a[i-1][2])

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

Submission status: Accepted

Solution code:
def chmax(a, b):
    if a < b:
        return b
    return a

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

dp = [[-float('inf') for i in range(3)] for j in range(N)]

dp[0] = H[0]

for i in range(1, N):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i][j] = chmax(dp[i][j], dp[i-1][k]+H[i][j])

print(max(dp[-1]))

Submission status: Accepted

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

    DP = [[0, 0, 0] for _ in range(N)]
    DP[0] = abc[0]

    for i in range(1, N):
        for j in range(3):
            tmp = [abc[i][j] + DP[i-1][k] for k in range(3) if k != j]
            DP[i][j] = max(tmp)

    print(max(DP[-1]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    DP = [[0, 0, 0] for _ in range(N)]
    DP[0] = abc[0]

    for i in range(1, N):
        for j in range(3):
            tmp = [abc[i][j] + DP[i-1][k] for k in range(3) if k != j]
            DP[i][j] = max(tmp)

    print(max(DP[-1]))

main()

Submission status: Accepted

Solution code:
n = int(input())
satis = []
for i in range(n):
    satis.append([int(j) for j in input().split()])
"""
dp[i][j] = 幸福度
i : 何日目終了時点(0~n)
j : 直前に選んだもの(0 : A,1 : B,2 : C)
"""
#print(satis)
dp = [[-1] * 3 for i in range(n+1)]
#print(dp)
for j in range(3):
    dp[0][j] = 0
#print(dp)
#i日目
for when in range(1,n+1):
    #選択肢
    for yesterday in range(3):
        if when != 1:
            for today in range(3):
                if today != yesterday:
                    dp[when][today] = max(dp[when][today], dp[when-1][yesterday] + satis[when-1][today])
        else:
            dp[when][yesterday] = satis[when-1][yesterday]

print(max(dp[n]))

Submission status: Accepted

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

y = [[0 for j in i] for i in x]


for i in range(len(x)):
    if i - 1 < 0:
        y[i] = [k for k in x[i]]    
        continue

    for j in range(len(x[i])):
        x_1 = max([y[i - 1][k] for k in range(len(x[i - 1])) if k != j])
        y[i][j] = x[i][j] + x_1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np
n = int(input())
abc = [input() for _ in range(n)]
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][k] for k in range(3)if k != j ]) +int(abc[i-1].split()[j])

print(max( [dp[n][i] for i in range(3)] ) )

Submission status: Accepted

Solution code:
n = int(input().strip())

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

# I.C.
a, b, c = map(int, input().strip().split())
dp[0][0]=a
dp[0][1]=b
dp[0][2]=c

for i in range(n-1):
    abc = list(map(int, input().strip().split()))
    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]+abc[j])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())

activity =[]

for i in range(n):
    array = list(map(int,input().split()))
    activity.append(array)

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

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

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

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

Submission status: Accepted

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

dp = [[0 for _ in range(3)] for _ in range(N)]
for i in range(N):
    for j in range(3):
        if i == 0:
            dp[i][j]= A[i][j]
        else:
            tmp = [0] 
            for k in range(3):
                if j !=k:
                    tmp.append(dp[i-1][k])
            dp[i][j] = max(tmp) + A[i][j]
print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())

activities = []

for i in range(N):
  activities.append([int(x) for x in input().split()])
  
memo = [[0] * N for _ in range(3)]

for day in range(N):
  for no in range(3):
    # 1日目を初期化
    if day == 0:
      memo[no][0] = activities[0][no]
      continue
    # 同じアクティビティが連続しないように
    memo[no][day] = max(
      memo[(no + 1) % 3][day - 1], 
      memo[no - 1][day - 1]
    ) + activities[day][no]
    
print(max(memo[x][N -1] for x in range(3)))

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(1,N+1):
    a,b,c = map(int,input().split())
    dp[i][0] = max(dp[i-1][1] + a,dp[i-1][2] + a)
    dp[i][1] = max(dp[i-1][2] + b,dp[i-1][0] + b)
    dp[i][2] = max(dp[i-1][0] + c,dp[i-1][1] + c)
ans = max(dp[N][0],dp[N][1],dp[N][2])
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #整数1つinput
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii())
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #文字列1つinput
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

n = ii()
arr = llint(n)
dp = [[0]*3 for _ in range(n)]
dp[0][0],dp[0][1],dp[0][2]=arr[0][0],arr[0][1],arr[0][2]
for i in range(1,n):
    for abc in [0,1,2]:
        if abc==0:
            dp[i][0] = max(arr[i][0]+dp[i-1][1],arr[i][0]+dp[i-1][2])
        elif abc==1:
            dp[i][1] = max(arr[i][1]+dp[i-1][0],arr[i][1]+dp[i-1][2])
        else:
            dp[i][2] = max(arr[i][2]+dp[i-1][1],arr[i][2]+dp[i-1][0])

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

Submission status: Accepted

Solution code:
N=int(input())
abc=[[] for _ in range(N)]

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

dp=[[0,0,0] for _ 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]+abc[i-1][k])
                

print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())

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

    dp = newDP[::]

ans = max(dp)
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[LI() for _ in range(n)]

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

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

# main()
print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
def fnSolv():
  iNum = int(input())
  naABC = np.zeros((iNum, 3), dtype = int)
  naDP  = [0]*3
  #naDP  = [10**9, 10**9, 10**9]
  for iI in range(iNum):
    naABC[iI] = list(map(int, input().split()))
  for iA, iB, iC in naABC:
    naDPa = max([naDP[1] + iA, naDP[2] + iA])
    naDPb = max([naDP[2] + iB, naDP[0] + iB])
    naDPc = max([naDP[0] + iC, naDP[1] + iC])
    naDP = [naDPa, naDPb, naDPc]
    #print(naDP)
  print(max(naDP))

if __name__ == '__main__':
  fnSolv()

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def add_mod(a,b): return (a+b) % MOD

N = iin()
abc = [iln() 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][j] = max(dp[i+1][j], dp[i][k]+abc[i][j])
print(max(dp[N]))

Submission status: Accepted

Solution code:
N = int(input())

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

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] = [a[0], b[0], c[0]]

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

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  dp = [0, 0, 0]
  
  for activities in [list(map(int, input().split())) for _ in range(n)]:
    new_dp = [0, 0, 0]
    
    for i in range(3):
      offset = dp[i]
      for j in range(3):
        if i == j: continue
          
        new_dp[j] = max(new_dp[j], offset + activities[j])
    
    dp = new_dp
  
  print(max(dp))

if __name__ == "__main__":
  main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools

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

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

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

for i in range(1, n):
	for j, k in itertools.product(range(3), range(3)):
		if j == k:
			continue
		else:
			dp[i][k] = chmax(dp[i][k], dp[i - 1][j] + ls[i][k])

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

Submission status: Accepted

Solution code:
n = int(input())

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

    if not dp:
        dp.append([a, b, c])
    else:
        dp.append([a + max(dp[-1][1], dp[-1][2]),
                   b + max(dp[-1][0], dp[-1][2]),
                   c + max(dp[-1][0], dp[-1][1])])

print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
MOD = 10**9+7

N = iin()
abc = [iln() 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][j] = max(dp[i+1][j], dp[i][k]+abc[i][j])
print(max(dp[N]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 18:19:39 2020

@author: matsui
"""

N=int(input())
dp=dict()
dp['a']=[0]*N
dp['b']=[0]*N
dp['c']=[0]*N

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

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10**7)

def max_happiness(n, data, dp, a, b, c):
  string = str(n) + str(a) + str(b) + str(c)

  if dp[string] is not None:
    return dp[string]

  if n == 0:
    if a and b:
      dp[string] = max(data[n][0], data[n][1])
      return dp[string]
    elif b and c:
      dp[string] = max(data[n][1], data[n][2])
      return dp[string]
    elif c and a:
      dp[string] = max(data[n][2], data[n][0])
      return dp[string]

  max_a = -1
  max_b = -1
  max_c = -1

  if a:
    max_a = data[n][0] + max_happiness(n-1, data, dp, a=0, b=1, c=1)
  if b:
    max_b = data[n][1] + max_happiness(n-1, data, dp, a=1, b=0, c=1)
  if c:
    max_c = data[n][2] + max_happiness(n-1, data, dp, a=1, b=1, c=0)

  dp[string] = max(max_a, max_b, max_c)
  return dp[string]

N = int(input())
data = []
dp = defaultdict(lambda: None)

for _ in range(N):
  data.append([int(num) for num in input().split()])

print(max_happiness(N-1, data, dp, a=1, b=1, c=1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
table = []
dp = [[0]*3 for i in range(N)]

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

dp[0] = table[0]
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]+table[i][j])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
def solve():
    N, *abc = map(int, open(0).read().split())
    a = abc[::3]
    b = abc[1::3]
    c = abc[2::3]
    
    dp = [[10 ** 10] * 3 for _ in range(N)]
    dp[0][0], dp[0][1], dp[0][2] = a[0], b[0], c[0]
    for i in range(1, N):
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i]
        dp[i][1] = max(dp[i - 1][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]))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
N = int(input().split()[0])
abc_list = []

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

dp_list = [dict(a=0, b=0, c=0) for _ in range(N + 1)]

for i in range(1, N + 1):
    # i日目の行動
    scores = abc_list[i - 1]
    # その日行動Aをとる場合の最適値
    dp_list[i]["a"] = scores["a"] + max(dp_list[i - 1]["b"], dp_list[i - 1]["c"])
    # その日行動Bをとる場合の最適値
    dp_list[i]["b"] = scores["b"] + max(dp_list[i - 1]["a"], dp_list[i - 1]["c"])
    # その日行動Cをとる場合の最適値
    dp_list[i]["c"] = scores["c"] + max(dp_list[i - 1]["a"], dp_list[i - 1]["b"])

ans = max(dp_list[-1].values())

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = []
B = []
C = []

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

dp_a = [None for _ in range(n)]
dp_b = [None for _ in range(n)]
dp_c = [None for _ in range(n)]

dp_a[0] = A[0]
dp_b[0] = B[0]
dp_c[0] = C[0]

for i in range(1, n):
    dp_a[i] = max([dp_b[i-1]+A[i], dp_c[i-1]+A[i]])
    dp_b[i] = max([dp_a[i-1]+B[i], dp_c[i-1]+B[i]])
    dp_c[i] = max([dp_a[i-1]+C[i], dp_b[i-1]+C[i]])

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

Submission status: Accepted

Solution code:
def solve(N, happiness):
  dp = [[0 for _ in range(3)] for _ in range(N)]
  dp[0][0] = happiness[0][0]
  dp[0][1] = happiness[0][1]
  dp[0][2] = happiness[0][2]

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

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

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

N = iin()
happiness = []
for i in range(N):
  happiness.append(iln())
solve(N, happiness)

Submission status: Accepted

Solution code:

def solver():
	N = int(input())
	action = []
	for i in range(N):
		action.append(list(map(int, input().split())))

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

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

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

solver()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#Educational DP Contest
#C-Vacation

n = int(input())
#n,m = map(int,input().split())
#lst1 = list(map(int,input().split()))

#dp table
#その選択肢を選んだときの最大値をそこに入れる[a,b,c]
dp = [[0,0,0] for _ in range(n)]
a,b,c = map(int,input().split())
dp[0] = [a,b,c]

#process1
for i in range(1,n):
    a,b,c = map(int,input().split())
    for j in range(3): #1つ前の手順で選んだものは使わない
        if j == 0: #about a
            dp[i][j] = max(dp[i-1][1],dp[i-1][2]) + a
        elif j == 1: #about b
            dp[i][j] = max(dp[i-1][0],dp[i-1][2]) + b
        else: #about c
            dp[i][j] = max(dp[i-1][0],dp[i-1][1]) + c


#output process
print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys
import numpy as np
n = int(input())

dp = list(map(int, sys.stdin.readline().split()))

for i in range(n-1):
    a, b, c = list(map(int, sys.stdin.readline().split()))
    dp0, dp1, dp2 = dp
    dp[0] = max(dp1+a,dp2+a)
    dp[1] = max(dp0+b,dp2+b)
    dp[2] = max(dp0+c,dp1+c)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
import numpy as np
n = int(input())

dp = list(map(int, input().split()))

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

Submission status: Accepted

Solution code:
N=int(input())

p=list(map(int,input().split()))

for i in range(1,N):
    add=list(map(int,input().split()))
    p0=p[0]
    p1=p[1]
    p2=p[2]
    p[0]=max(add[0]+p1,add[0]+p2)
    p[1]=max(add[1]+p2,add[1]+p0)
    p[2]=max(add[2]+p0,add[2]+p1)

print(max(p))

Submission status: Accepted

Solution code:
N=int(input())

p=list(map(int,input().split()))

for i in range(1,N):
    add=list(map(int,input().split()))
    temp=[[] for j in range(3)]
    for j in range(3):
        pnt=p[j]
        for k in range(3):
            if j==k:continue
            else:
                temp[k].append(pnt+add[k])
    for j in range(3):
        p[j]=max(temp[j])
print(max(p))

Submission status: Accepted

Solution code:
# C - Vacation
def main():
    N, *ABC = map(int, open(0).read().split())
    prev = ABC[:3]
    for abc in zip(*[iter(ABC[3:])] * 3):
        cur = [0] * 3
        for i in range(3):
            cur[i] = abc[i] + max(prev[:i] + prev[i + 1:])
        prev = cur
    print(max(prev))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# C - Vacation
def main():
    N, *ABC = map(int, open(0).read().split())
    prev = ABC[:3]
    for a, b, c in zip(*[iter(ABC[3:])] * 3):
        cur = [0] * 3
        cur[0] = max(prev[1:]) + a
        cur[1] = max(prev[0], prev[2]) + b
        cur[2] = max(prev[:2]) + c
        prev = cur
    print(max(prev))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import unittest


class TestC(unittest.TestCase):
    def test_1(self):
        self.assertEqual(
            think([[10, 40, 70], [20, 50, 80], [30, 60, 90]]),
            210
        )

    def test_2(self):
        self.assertEqual(
            think([[100, 10, 1]]),
            100
        )

    def test_3(self):
        self.assertEqual(
            think([
                [6, 7, 8], [8, 8, 3], [2, 5, 2], [7, 8, 6],
                [4, 6, 8], [2, 3, 4], [7, 5, 1]
            ]),
            46
        )


def solve():
    list_of_abc = read()
    result = think(list_of_abc)
    write(result)


def read():
    n = read_int(1)[0]
    list_of_abc = []
    for _ in range(n):
        list_of_abc.append(read_int(3))
    return list_of_abc


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(list_of_abc):
    n = len(list_of_abc)
    elems = len(list_of_abc[0])

    # dp[0 to n - 1][0 to 2]
    dp = [[0 for _ in range(elems)] for _ in range(n)]

    for i, e in enumerate(list_of_abc[0]):
        dp[0][i] = e

    for i in range(1, n):
        for todays_act in range(elems):
            for yesterdays_act in range(elems):
                if todays_act == yesterdays_act:
                    continue
                dp[i][todays_act] = max(
                        dp[i][todays_act],
                        dp[i - 1][yesterdays_act] + list_of_abc[i][todays_act]
                )

    return max(dp[n - 1])


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()