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:
#Educational DP c vacation
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]
dp = [[0, 0, 0] for _ in range(n+1)]
for i in range(n):
    dp[i+1][0] = abc[i][0] + max(dp[i][1], dp[i][2])
    dp[i+1][1] = abc[i][1] + max(dp[i][0], dp[i][2])
    dp[i+1][2] = abc[i][2] + max(dp[i][0], dp[i][1])
print(max(dp[n][0], max(dp[n][1], dp[n][2])))

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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]+vac[i][k])
print(max(dp[-1]))

Submission status: Accepted

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

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

print(max(dp[-1]))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def edu_dp_c_vacation():
    n = int(input())
    v = []
    for _ in range(n):
        v.append(list(map(int, input().split())))
    dp = [[0]*3 for _ in range(n)]
    dp[0] = v[0].copy()
    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]+v[i][j])
    print(max(dp[n-1]))
edu_dp_c_vacation()

Submission status: Accepted

Solution code:
n=int(input()) 
dp1,dp2,dp3=[0]*n,[0]*n,[0]*n
f=[]
for i in range(n):
	f.append([int(x) for x in input().split()])  
dp1[0]=f[0][0] 
dp2[0]=f[0][1] 
dp3[0]=f[0][2] 
for i in range(1,n):
	dp1[i]=f[i][0]+max(dp2[i-1],dp3[i-1]) 
	dp2[i]=f[i][1]+max(dp1[i-1],dp3[i-1])
	dp3[i]=f[i][2]+max(dp2[i-1],dp1[i-1])
print(max(dp1[-1],dp2[-1],dp3[-1]))

Submission status: Accepted

Solution code:
N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
dpa = [abc[0][0]] + [0] * N
dpb = [abc[0][1]] + [0] * N
dpc = [abc[0][2]] + [0] * N
for i in range(1, N):
    dpa[i] = max(dpb[i-1], dpc[i-1]) + abc[i][0]
    dpb[i] = max(dpa[i-1], dpc[i-1]) + abc[i][1]
    dpc[i] = max(dpa[i-1], dpb[i-1]) + abc[i][2]

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

Submission status: Accepted

Solution code:
N=int(input())
INF=10**10
dp=[[-1]*3 for i in range(N)]
for i in range(N):
  abc=list(map(int,input().split()))
  if i==0:
    dp[0][0]=abc[0]
    dp[0][1]=abc[1]
    dp[0][2]=abc[2]
    continue
  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[j])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
#dpは拡張されたdpテーブルでdp[i][j]はi日目にjの活動を選択したときに取れる最大の満足度
n = int(input())
dp = [[0]*3]*(n)
an = list(map(int,input().split()))
dp[0] = an
for i in range(1,n):
    
    a,b,c = list(map(int, input().split()))
    
    
    a_m = max(dp[i-1][1]+a, dp[i-1][2]+a)
    b_m = max(dp[i-1][0]+b, dp[i-1][2]+b)
    c_m = max(dp[i-1][0]+c, dp[i-1][1]+c) 
    dp[i] = [a_m,b_m,c_m]

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

Submission status: Accepted

Solution code:

n = int(input())
summmer = [""]*n
for i in range(n):
    summmer[i] = list(map(int,input().split()))
happy = [0]*(n+1)
for i in range(n+1):
    happy[i] = [0]*3
yesterday = -1
for i in range(1,n+1):
    happy[i][0] = max(happy[i-1][1] + summmer[i-1][0],happy[i-1][2] + summmer[i-1][0]) 
    happy[i][1] = max(happy[i-1][0] + summmer[i-1][1],happy[i-1][2] + summmer[i-1][1]) 
    happy[i][2] = max(happy[i-1][0] + summmer[i-1][2],happy[i-1][1] + summmer[i-1][2]) 
# print(happy)
print(max(happy[-1]))

Submission status: Accepted

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

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][k]+s[i][j],dp[i+1][j])
print(max(dp[n]))

Submission status: Accepted

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

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

h = h.reshape(N, 3)

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

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [[-1]*3 for _ in range(n+1)]

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

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

print(max(dp[n]))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:

n = int(input())
x = [-1]*n
for i in range(n):
    x[i] = list(map(int, input().split()))

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

for k in range(1,n):
    for j in range(3):
        ans[k][j] = max(ans[k-1][(j+1)%3], ans[k-1][(j+2)%3]) + x[k][j]

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

Submission status: Accepted

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

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

for i in range(1,N+1):
    for today in range(3):
        for yesterday in range(3):
            if today == yesterday: continue

            dp[i][today] = max(dp[i][today], dp[i-1][yesterday] + happy[i][today])

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

Submission status: Accepted

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

Submission status: Accepted

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

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

    for i in range(N):
        for j in range(3):
            for k in range(3):
                if j==k:continue
                dp[i+1][k] = max(dp[i+1][k],dp[i][j]+v[i][k])
    print(max(dp[N][i] for i in range(3)))
main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    dp = [[0] * 3 for i in range(N + 1)]
    for i in range(N):
        A = list(map(int, input().split()))
        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[k])
    return max(dp[N])

print(solve())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = []
for _ in range(N):
    a,b,c = map(int,input().split())
    A.append((a,b,c))
    
# 無限大の値
INF = 10**10

# DP テーブル (値と前に選んだ活動を保持)
# a (j = 0), b (j = 1), c (j = 2)に記録
dp = [[0]*3 for _ in range(100010)]

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

def rec(v):
    # v 日目の活動
    for w in range(3):
        # DP の値がすでに更新されていたらそのままリターン
        if dp[v][w] > 0:
            return dp[v]
        # 初期条件
        if v == 0:
            dp[v][w] = 0
            return dp[v]
        # v-1 を再帰
        res = 0
        for k in range(3):
            # 前日と活動が同じならスルー
            if w == k:
                continue
            res = max(res, rec(v-1)[k] + A[v-1][w])
            # 結果をメモして返す
            dp[v][w] = res
    return dp[v]
rec(N)
ans = max(dp[N])
print(ans)

Submission status: Accepted

Solution code:
# C - Vacation AC
N = int(input())
A = []
for _ in range(N):
    a,b,c = map(int,input().split())
    A.append((a,b,c))
    
# 無限大の値
INF = 10**10

# DP テーブル (値と前に選んだ活動を保持)
# a (j = 0), b (j = 1), c (j = 2)に記録
dp = [[0]*3 for _ in range(100010)]

# DP テーブル全体を初期化
for i in range(100010):
    for j in range(3):
        dp[i][j] = -INF# 最大化問題
        
# 初期条件
dp[0][0],dp[0][1],dp[0][2] = 0,0,0
        
# v 日目以前に (v 日目以前の幸福度最大値を求める)
for v in range(1,N+1):
    # v 日目の活動
    for w in range(3):
        # v-1 日目の活動
        for k in range(3):
            # 前日と活動が同じならスルー
            if w == k:
                continue
            # v 日目の情報は A[v-1] であることに注意
            dp[v][w] = max(dp[v][w], dp[v-1][k] + A[v-1][w])

# N 日目以前の幸福度最大値を出力
ans = max(dp[N])            
print(ans)

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# inputを高速化する。
input = sys.stdin.readline
# 入力
vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]
# DPテーブル
# 最大化問題なので0で初期化
dp = [[0 for i in range(3)] for j in range(vacation+1)]
# dpの最大値を更新するための関数
def chmax(a, b):
    if a > b:
        return a
    else:
        return b
# メモ化再帰の関数
def rec(i):
    # DPの値が既に更新されている場合はその値を返す
    for j in range(3):
        if dp[i][j] > 0:
            break
        
        # 再帰の終了条件
        if i == 0:
            dp[i][j] = 0
            break
        
        # i-1 を再帰
        res = 0
        for k in range(3):
            if j == k:
                continue
            res = chmax(res, rec(i-1)[k] + lst_happiness[i-1][k])
            # 結果をメモする
            dp[i][j] = res
    
    return dp[i]
ans = rec(vacation)
ans = max(ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
# inputを高速化する。
input = sys.stdin.readline
# 入力
vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]
# DPテーブル
# 最大化問題なので0で初期化
dp = [[0 for i in range(3)] for j in range(vacation+1)]
def chmax(a, b):
    if a > b:
        return a
    else:
        return b
# dp[i][0] から dp[i + 1][1] への遷移
# dp[i][0] から dp[i + 1][2] への遷移
# dp[i][1] から dp[i + 1][0] への遷移
# dp[i][1] から dp[i + 1][2] への遷移
# dp[i][2] から dp[i + 1][0] への遷移
# dp[i][2] から dp[i + 1][1] への遷移
# 各 j (= 0, 1, 2) と各 k (= 0, 1, 2) に対して、j ≠ k ならば
# chmin(dp[i + 1][k], dp[i [j] + lst_happiness[i][k])
for i in range(vacation):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + lst_happiness[i][k])
ans = 0
for i in range(3):
    ans = chmax(ans, dp[vacation][i])
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

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

#ステップ1
dp=[[-float('inf')] * 3 for i in range(N+1)]
#N+1行作っておくことでループを回すときにN日目だけ分けて考える必要がなくなる。

#ステップ2
dp[0]=A[0] #初日にAを実行する日の幸福度は確定している。以下同様。

#ステップ3
for i in range(N):
  for j in range(3): #i+1日目に行うアクティビティ
    for k in range(3): #i+2日目に行うアクティビティ
      if j != k: #2日連続同じアクティビティは禁止
        if dp[i+1][k] < dp[i][j] + A[i+1][k]:
          dp[i+1][k] = dp[i][j] + A[i+1][k]
        
#ステップ4
ans=max(dp[N-1])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
"""
n, k = [int(i) for i in input().split(' ')]

arr = [int(i) for i in input().split(' ')]

dp = [10**10]*n

k += 1
dp[0] = 0

for i in range(0, n):
    for j in range(1, k):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(arr[i+j]-arr[i]))

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

n = int(input())

a = [int(i) for i in input().split(' ')]

for i in range(1, n):
    new_a = [int(i) for i in input().split(' ')]
    new_a[0] = max(new_a[0]+a[1], new_a[0]+a[2])
    new_a[1] = max(new_a[1]+a[0], new_a[1]+a[2])
    new_a[2] = max(new_a[2]+a[1], new_a[2]+a[0])
    a, new_a = new_a, a

print(max(a))

Submission status: Accepted

Solution code:
# C - Vacation
N = int(input())
A = []
for _ in range(N):
    a,b,c = map(int,input().split())
    A.append((a,b,c))
    
# 無限大の値
INF = 10**10

# DP テーブル (値と前に選んだ活動を保持)
# a (j = 0), b (j = 1), c (j = 2)に記録
dp = [[0]*3 for _ in range(100010)]

# DP テーブル全体を初期化
for i in range(100010):
    for j in range(3):
        dp[i][j] = -INF# 最大化問題
        
# 初期条件
dp[0][0],dp[0][1],dp[0][2] = 0,0,0
        
# v 日目以前に (v 日目以前の幸福度最大値を求める)
for v in range(1,N+1):
    # v-1 日目の活動
    for w in range(3):
        # v 日目の活動
        for k in range(3):
            # 前日と活動が同じならスルー
            if w == k:
                continue
            # v 日目の情報は A[v-1] であることに注意
            dp[v][k] = max(dp[v][k], dp[v-1][w] + A[v-1][k])

# N 日目以前の幸福度最大値を出力
ans = max(dp[N])            
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())

# print(a)
# print(b)
# print(c)
S = [[0 for j in range(3)] for i in range(N)]
S[0][0] = a[0]
S[0][1] = b[0]
S[0][2] = c[0]

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

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

Submission status: Accepted

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

H=[]
for _ in range(n):
  a,b,c=map(int,input().split())
  H.append([a,b,c])
  
dp=[[0 for i in range(3)] for j in range(n+1)]
for i in range(1,n+1):
  dp[i][0]=max(dp[i-1][1]+H[i-1][0],dp[i-1][2]+H[i-1][0])
  dp[i][1]=max(dp[i-1][2]+H[i-1][1],dp[i-1][0]+H[i-1][1])
  dp[i][2]=max(dp[i-1][0]+H[i-1][2],dp[i-1][1]+H[i-1][2])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
a,b,c = [],[],[]
for n in range(N):
  a_,b_,c_ = map(int, input().split())
  a.append(a_)
  b.append(b_)
  c.append(c_)
do_a = [a[0]] #do a in n-th day
do_b = [b[0]] #same
do_c = [c[0]]

for day in range(1,N):
  do_a.append(a[day] + max(do_b[day-1], do_c[day-1]))
  do_b.append(b[day] + max(do_a[day-1], do_c[day-1]))
  do_c.append(c[day] + max(do_a[day-1], do_b[day-1]))
print(max(do_a[N-1],do_b[N-1], do_c[N-1]))

Submission status: Accepted

Solution code:
from itertools import permutations as P

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

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

l = tuple(P(range(3), 2))

for i in range(N):
	for j in range(6):
		a, b = l[j]

		dp[i+1][b] = max(dp[i+1][b], dp[i][a] + V[i][b])

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

Submission status: Accepted

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

print(max(dp[N]))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from copy import deepcopy


def solve(N, abc):
    dp = [[0, 0, 0] for i in range(N+1)]

    for i in range(1, N+1):
        for j in range(3):
            tmp = []
            for d in dp[i-1]:
                tmp.append(d)
            tmp.pop(j)
            dp[i][j] = max(tmp) + abc[i-1][j]

    return(max(dp[N]))


if __name__ == "__main__":
    N = int(input())
    abc = [list(map(int, input().split())) for _ in range(N)]
    print(solve(N, abc))

Submission status: Accepted

Solution code:
from copy import deepcopy


def solve(N, abc):
    dp = [[0, 0, 0] for i in range(N+1)]

    for i in range(1, N+1):
        for j in range(3):
            tmp = deepcopy(dp[i-1])
            tmp.pop(j)
            dp[i][j] = max(tmp) + abc[i-1][j]

    return(max(dp[N]))


if __name__ == "__main__":
    N = int(input())
    abc = [list(map(int, input().split())) for _ in range(N)]
    print(solve(N, abc))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

sum=[[0]*3 for _ in range(N+1)]
for i in range(1,N+1):
    sum[i][0]=max(sum[i-1][1],sum[i-1][2])+l[i][0]
    sum[i][1]=max(sum[i-1][0],sum[i-1][2])+l[i][1]
    sum[i][2]=max(sum[i-1][0],sum[i-1][1])+l[i][2]
ans=max(sum[N])
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
input=lambda : stdin.readline().strip()
from math import ceil,sqrt,factorial,gcd
from collections import deque
n=int(input())
prev=0
l=[]
for i in range(n):
	l.append(list(map(int,input().split())))
z=[[0,0,0] for i in range(n)]
z[0]=l[0]
for i in range(1,n):
	z[i][0]=l[i][0]+max(z[i-1][1],z[i-1][2])
	z[i][2]=l[i][2]+max(z[i-1][1],z[i-1][0])
	z[i][1]=l[i][1]+max(z[i-1][0],z[i-1][2])
print(max(z[-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)]

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
def maxExept(lis):
    data = [0,0,0]
    data[0] = max(lis[1],lis[2])
    data[1] = max(lis[0],lis[2])
    data[2] = max(lis[0],lis[1])
    return data
k = int(input())
grid = []
for i in range(k):
  x = list(map(int,input().split(' ')))
  grid.append(x)
for i in range(len(grid)-2,-1,-1):
    x,y,z = maxExept(grid[i+1])
    grid[i][0] +=x
    grid[i][1] +=y
    grid[i][2] +=z
print(max(grid[0]))

Submission status: Accepted

Solution code:
n=int(input())
A=[]
B=[]
C=[]
for i in range(n):
    
    a,b,c = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    
dp = [[0,0,0] for i in range(n)]

dp[0] =[A[0],B[0],C[0]]

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

Submission status: Accepted

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

a, b, c = [0], [0], [0]
for i in abc:
  aa = i[0] + max(b[-1], c[-1])
  bb = i[1] + max(c[-1], a[-1])
  cc = i[2] + max(a[-1], b[-1])
  a.append(aa)
  b.append(bb)
  c.append(cc)
print(max(a[-1], b[-1], c[-1]))

Submission status: Accepted

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

aabbcc = [[0], [0], [0]]
tmp = [0]*3
for i in abc:
  for j in range(3):
    tmp[j] = i[j] + max(aabbcc[(j+1)%3][-1], aabbcc[(j+2)%3][-1])
  for j in range(3):
    aabbcc[j].append(tmp[j])
print(max([i[-1] for i in aabbcc]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from random import randint

from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count

def isvalid(n,i):
    if i>=n or i<0:
        return False
    return True


def solve():
    n=int(inp())
    ar=[]
    for i in range(n):
        ar.append(lis())
    dp=[[-1]*3 for _ in range(n+5)]
    dp[0][0]=ar[0][0]
    dp[0][1] = ar[0][1]
    dp[0][2] = ar[0][2]
    for i in range(1,n):
        for j in range(3):
            s=0
            for k in range(3):
                if k!=j:
                    s=max(s,dp[i-1][k]+ar[i][j])
            dp[i][j]=s
    print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))




solve()

Submission status: Accepted

Solution code:
def maxPoints(a,b,c,N):
    dp = [[0]*3 for _ 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] = a[i] + max(dp[i-1][1],dp[i-1][2])
        dp[i][1] = b[i] + max(dp[i-1][0],dp[i-1][2])
        dp[i][2] = c[i] + max(dp[i-1][1],dp[i-1][0])
    
    return max(dp[N-1])

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