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

scr = [[0,0,0] for _ in range(n+1)]

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

print(max(scr[n]))

Submission status: Accepted

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

def dp(N):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(3)] for j in range(N)]
  for i in range(3): dp[0][i]=ABC[0][i]
    
  for i in range(N):
    if i != 0:
      for j in range(3):
        for k in range(3):
          if j!=k:
            dp[i][j] = max(dp[i-1][k]+ABC[i][j],dp[i][j])
    
  return max(dp[N-1][0],dp[N-1][1],dp[N-1][2])

print(dp(N))

Submission status: Accepted

Solution code:
import random

import sys
sys.setrecursionlimit(100000000)

# N = 5000
# P = [[random.randint(1,10000) for i in range(3)] for i in range(N)]
N = int(raw_input())
P = [list(map(int, raw_input().split())) for i in range(N)]
memo = {}
ACTIVITIES = set([0,1,2])
def get_point(activity, day):
    if day >= N:
        return 0
    return P[day][activity]

def get_max_vaccation_point_from_day(last_activity, day):
    if day >= N:
        return 0

    if (last_activity, day) in memo:
        return memo[last_activity, day]

    possible_activities = ACTIVITIES - set([last_activity])
    ans = max(
        get_point(activity, day) + get_max_vaccation_point_from_day(activity, day+1) for activity in possible_activities)

    memo[last_activity, day] = ans
    return ans


print get_max_vaccation_point_from_day(-1, 0)

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 isn(): return input().split() #文字列読み込み
def imn(): return map(int, 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 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 divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i: divisors.append(n//i)
    return divisors
def is_prime(n):
    if n == 1: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False 
    return True
def primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n + 1, i): is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]
def sieve_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime
def run_length_encode(s):
    count = 1
    code = []
    target = s[0]
    for i in range(1, len(s)):
        if target == s[i]: count += 1
        else:
            code.append((target, count))
            target = s[i]
            count = 1
    code.append((target, count))
    return code

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:
A=[]
n=int(input())
for i in range(n):
    B=list(int(j) for j in input().split())
    A.append(B)
dp=[[0 for i in range(3)]for k in range(n)]
#print(dp)
for i in range(n):
    for j in range(3):
        if i>0 and j==1:
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j+1])+A[i][j]
        elif i==0:
            dp[i][j]=A[i][j]
        elif j==0:
            dp[i][j]=max(dp[i-1][j+1],dp[i-1][j+2])+A[i][j]
        elif j==2:
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j-2])+A[i][j]
print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())
X = []
for i in range(0, N):
    x = list(map(int, input().split()))
    X.append(x)
dp = []
for i in range(0, N+1):
    dp.append([0, 0, 0])
for i in range(1, N+1):
    for j in range(0, 3):
        for k in range(0, 3):
            if j == k:
                continue
            else:
                dp[i][k] = max(dp[i][k], dp[i-1][j]+X[i-1][k])
print(max(dp[N]))

Submission status: Accepted

Solution code:
N = int(input())
Table = []
dp = [[0]*3 for i in range(10**6)]

for _ in range(N):
    a,b,c = map(int, input().split())
    Table.append([a,b,c])
dp[0][0] = Table[0][0]
dp[0][1] = Table[0][1]
dp[0][2] = Table[0][2]

for i in range(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[N-1][0], dp[N-1][1], dp[N-1][2]))

Submission status: Accepted

Solution code:
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]
dp = [[0, 0, 0] for _ in range(n)]
for i in range(n):
  for j in range(3):
    if i == 0:
      dp[i][j] = abc[i][j]
    else:
      for k in range(3):
        if k == j:
          continue
        dp[i][j] = max(dp[i][j], dp[i-1][k] + abc[i][j])
ans = max(dp[n-1])
print(ans)

Submission status: Accepted

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

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

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

print(max(dp[N]))

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

dp = [[0,0,0] for i in range(N)]
dp[0] = L[0]

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

Submission status: Accepted

Solution code:
N = int(input())

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
umi=[]
yama=[]
ie=[]
A=[]
N=int(input())
for i in range(N):
  a,b,c=map(int,input().split())
  umi.append(a)
  yama.append(b)
  ie.append(c)
#print("umi",umi)
#print("yama",yama)
#print("ie",ie)
DP = [[0, 0, 0] for _ in range(N+5)]
DP[0]=[umi[0],yama[0],ie[0]]
#print(DP)
for i in range(1,N):
  DP[i][0]=max((DP[i-1][1]+umi[i]),(DP[i-1][2]+umi[i]))
  DP[i][1]=max((DP[i-1][0]+yama[i]),(DP[i-1][2]+yama[i]))
  DP[i][2]=max((DP[i-1][0]+ie[i]),(DP[i-1][1]+ie[i]))

#print(DP)
print(max(DP[N-1]))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

for day in range(1, N):
    new_dp = [max(dp[1], dp[2])+ABC[day][0],
              max(dp[0], dp[2])+ABC[day][1],
              max(dp[0], dp[1])+ABC[day][2]]
    dp = new_dp
    
print(max(dp))

Submission status: Accepted

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

for i in range(n):
    #j==kの場合を除く
    for j in range(3):
        for k in range(3):
            
            if j!=k:
                dp[i+1][j]=max(dp[i+1][j],dp[i][k]+l[i][j])
                
print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

# 0-indexed
dp = [[0 for _ in range(3)] for _ in range(N)] # dp[N日目][前日にした遊び]
dp[0] = ABC[0]

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

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    val = []

    for i in range(N):
        tmp = list(map(int, input().split()))
        val.append(tmp)
    
    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] + val[i][j])
    
    print(max(*dp[N]))

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N = int(input())
dp = np.zeros((N+1,3), dtype=np.int)
X = list(map(int, input().split()))
for _ in range(3):
  dp[1][_] = X[_]
for n in range(2,N+1):
  X = list(map(int, input().split()))
  dp[n][0] = max(dp[n-1][1],dp[n-1][2]) + X[0]
  dp[n][1] = max(dp[n-1][2],dp[n-1][0]) + X[1]
  dp[n][2] = max(dp[n-1][0],dp[n-1][1]) + X[2]
print(max(dp[N]))

Submission status: Accepted

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


if __name__ == "__main__":
  main()

Submission status: Accepted

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

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

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

for i in range(N - 1):
    dp[i + 1][0] = max(dp[i][1] + 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:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import itertools#これは色々使える組み込み関数みたいなやつ
import math#数学的計算はこれでいける。普通に0.5乗しても計算可能
#w=input()
i=0
j=0
N=int(input())
#N, W=input().split()
#S=input()
#T=input()
#S_list=list(S)
#h_list=  list(map(int, input().split(" ")))
#M=int(input())
#drink_list = [list(map(int, input().split(" ")))for i in range(M)]
#print(T_list[1])
#N=int(N)
#W=int(W)
#不本意だが内包表記で二次元の空のリストを作成する

dp=[['' for i in range(3)] for j in range(N)]
a, b, c =[0]*N, [0]*N, [0]*N
#print(dp)
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split(" "))
dp[0]=a[0], b[0], c[0]
#幸福度は自然数なので必ず幸福度は増加する
#0がa,1がb,2がc
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:
N = int(input())
lst = [] 
for i in range(N):
    lst.append(list(map(int, input().split())))
dp = [[0]*3 for i in range(N)]

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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


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

dp[0][0] = data[0][0]
dp[0][1] = data[0][1]
dp[0][2] = data[0][2]


# Maintain three scores for each day, one for each activity
# 

for day in range(1,N):
    for choice in range(3):
        for prev_choice in range(3):
            if choice != prev_choice:
                dp[day][choice] = max(dp[day][choice],dp[day-1][prev_choice]+data[day][choice])
                
best = max(dp[-1][:])
                
        
    
print (best)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def vacation(costs):
    total = [0, 0, 0]
    next_total = [0, 0, 0]

    i, j, k = 0, 1, 2
    for c in costs:
        for _ in range(3):
            next_total[i] = c[i] + max(total[j], total[k])
            i, j, k = j, k, i
        total, next_total = next_total, total
    return max(total)


def main():
    n = int(input())

    costs = [None] * n
    for idx in range(n):
        costs[idx] = [int(x) for x in input().split()]

    return vacation(costs)

print(main())

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

print(max(dp[N]))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

EDPC = "https://atcoder.jp/contests/dp/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"

############### TESTCASE ###############
test = ""
#test = \
"""
3
10 40 70
20 50 80
30 60 90
ans 210
"""

"""
1
100 10 1
ans 100
"""

"""
7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1
ans 46
8, 8, 5, 8, 8, 4, 7 -> 48
8, 8, 5, 7, 8, 3, 7 -> 46
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  
n = int(input2())
a = np.array([list(map(int, input2().split())) for i in range(n)])  
########## Non_Numpy_solution ##########

arr = a
dp = [[0, 0, 0] for _ in range(n)]
dp[0] = arr[0]
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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''


def main():
    N = int(input())
    A = [0] * N
    B = [0] * N
    C = [0] * N
    for i in range(N):
        a, b, c = list(map(int, input().split()))
        A[i] = a
        B[i] = b
        C[i] = c

    happy = [[0] * 3 for i in range(N)]
    happy[0] = [A[0], B[0], C[0]]
    for i in range(1, N):
        happy[i][0] = A[i] + max(happy[i-1][1], happy[i-1][2])
        happy[i][1] = B[i] + max(happy[i-1][2], happy[i-1][0])
        happy[i][2] = C[i] + max(happy[i-1][0], happy[i-1][1])
        # print(i, happy[i-1], happy[i])
    print(max(happy[N-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
INF = 10**12
param = []
for i in range(n):
    a, b, c = map(int, input().split())
    param.append([a, b, c])

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

EDPC = "https://atcoder.jp/contests/dp/"
TDPC = "https://atcoder.jp/contests/tdpc/tasks"

################ DANGER ################
test = ""
#test = \
"""
3
10 40 70
20 50 80
30 60 90
ans 210
"""

"""
1
100 10 1
ans 100
"""

"""
7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1
ans 46
8, 8, 5, 8, 8, 4, 7 -> 48
8, 8, 5, 7, 8, 3, 7 -> 46
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  
n = int(input2())
a = np.array([list(map(int, input2().split())) for i in range(n)])  
############ Numpy_solution ############


    
    
    
########## Non_Numpy_solution ##########
arr = a
dp = [[0, 0, 0] for _ in range(n)]
dp[0] = arr[0]
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())
l=[list(map(int,input().split())) for i in range(n)]
dp=[[0,0,0] 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]+l[i-1][j])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
 
 
def main():
    N = int(input())
    A, B, C = 0, 0, 0
    for _ in range(N):
        a, b, c = abc = map(int, input().split())
        A, B, C = max(B, C) + a, max(A, C) + b, max(A, B) + c
 
    print(max(A, B, C))
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    DP = [[0]*(N+1) for _ in range(3)]
    for i in range(N):
        # 行動a[i]を選ぶ場合
        DP[0][i+1] = max(DP[1][i], DP[2][i])+a[i]
        # 行動b[i]を選ぶ場合
        DP[1][i+1] = max(DP[2][i], DP[0][i])+b[i]
        # 行動c[i]を選ぶ場合
        DP[2][i+1] = max(DP[0][i], DP[1][i])+c[i]
    print(max(DP[0][N], DP[1][N], DP[2][N]))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())
dp = []
dp.append([0] * N)
dp.append([0] * N)
dp.append([0] * N)
a, b, c = [int(x) for x in input().strip().split()]
dp[0][0] = a
dp[1][0] = b
dp[2][0] = c

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

dp = [[0, 0, 0] for _ in range(100010)]

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:
N = int(input())
a = [[0 for i in range(3)] for j in range(N)]
dp = [[0 for i in range(3)] for j in range(N)]
for i in range(N):
    a[i][0], a[i][1], a[i][2] = map(int, input().split())

for j in range(3):  # initialize dp[0]
    dp[0][j] = a[0][j]

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

Submission status: Accepted

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

for j in range(3):  # initialize dp[0]
    dp[0][j] = a[0][j]

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

Submission status: Accepted

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

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

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

ans = max(dp[n-1])

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

dp = [[0]*3 for i in range(n)]
dp[0][0], dp[0][1], dp[0][2] = map(int, input().split())

for i in range(1,n):
    l = [int(x) for x in input().split()]
    for j in range(3):
        dp[i][j] = max(dp[i-1][j-1], dp[i-1][j-2]) + l[j]

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

Submission status: Accepted

Solution code:
n = int(input())

dp = [[0]*3 for i in range(n)]
dp[0][0], dp[0][1], dp[0][2] = map(int, input().split())

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    dp = [[0] * 3 for _ in range(n)]
    for i in range(n):
        a, b, c = list(map(int, readline().split()))
        if i == 0:
            dp[i][0] = a
            dp[i][1] = b
            dp[i][2] = c
        else:
            dp[i][0] = max(dp[i-1][1] + a, dp[i-1][2] + a)
            dp[i][1] = max(dp[i-1][0] + b, dp[i-1][2] + b)
            dp[i][2] = max(dp[i-1][0] + c, dp[i-1][1] + c)
    print(max(dp[-1]))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())

h = [[0, 0, 0] for i in range(N + 1)]

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

print(max(h[N]))

Submission status: Accepted

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

N = int(input())    # 夏休みの日数
K = 3      # 活動の種類

acts = []   # ここに各日での活動の幸福度を格納
for _ in range(N):
  acts.append(list(map(int, input().split())))

# acts_chk = [[1 for _ in range(3)] for __ in range(N)]


# 配列の初期化
# i日目に活動pを行ったときの累積幸福度 : dp_list[i][p]
inf = 1e10
dp_list = [[-inf for _ in range(K)] for __ in range(N)]

# 初期値
for i in range(K):
  dp_list[0][i] = acts[0][i]

for day in range(1,N):
  for act in range(K):
    for act_possible in range(K):
      if act == act_possible:
        continue
      dp_list[day][act] = max(dp_list[day][act], dp_list[day-1][act_possible] + acts[day][act])

print(max(dp_list[-1]))