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

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

print(max(dp[-1]))

Submission status: Accepted

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

for n in range(N):
  ABC.append(list(map(int, input().split())))

import numpy as np
ABC = np.array(ABC)

## 「日付」、「選択した行動」ごとの幸福度の最大値を格納するarray
hp=np.zeros((N,3),dtype=int)
hp[0] = ABC[0]

for n in range(1,N):# 日単位でのループ
  for c in range(3): # 選択肢ごとのループ
    ## n日にcを選択した場合の幸福度。つまり前日はc以外を選択している
    if c == 0:
      hp[n][0] = max(hp[n-1][1],hp[n-1][2]) + ABC[n][0]
    elif c == 1:
      hp[n][1] = max(hp[n-1][0],hp[n-1][2]) + ABC[n][1]
    elif c == 2:
      hp[n][2] = max(hp[n-1][0],hp[n-1][1]) + ABC[n][2]


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

Submission status: Accepted

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

INF=float("inf")
dpa=[-INF]*n
dpb=[-INF]*n
dpc=[-INF]*n
dpa[0]=a[0]
dpb[0]=b[0]
dpc[0]=c[0]

for i in range(1,n):
    dpa[i]=a[i]+max(dpb[i-1],dpc[i-1])
    dpb[i]=b[i]+max(dpc[i-1],dpa[i-1])
    dpc[i]=c[i]+max(dpa[i-1],dpb[i-1])
    
print(max(dpa[-1],dpb[-1],dpc[-1]))

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

INF=float("inf")
dpa=[-INF]*n
dpb=[-INF]*n
dpc=[-INF]*n
dpa[0]=a[0]
dpb[0]=b[0]
dpc[0]=c[0]

for i in range(1,n):
    dpa[i]=a[i]+max(dpb[i-1],dpc[i-1])
    dpb[i]=b[i]+max(dpc[i-1],dpa[i-1])
    dpc[i]=c[i]+max(dpa[i-1],dpb[i-1])
    
print(max(dpa[-1],dpb[-1],dpc[-1]))

Submission status: Accepted

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

INF=float("inf")
dpa=[-INF]*n
dpb=[-INF]*n
dpc=[-INF]*n
dpa[0]=a[0]
dpb[0]=b[0]
dpc[0]=c[0]

for i in range(1,n):
    dpa[i]=a[i]+max(dpb[i-1],dpc[i-1])
    dpb[i]=b[i]+max(dpc[i-1],dpa[i-1])
    dpc[i]=c[i]+max(dpa[i-1],dpb[i-1])
    
print(max(dpa[-1],dpb[-1],dpc[-1]))

Submission status: Accepted

Solution code:
# C - Vacation
n=int(input())
abc=[list(map(int,input().split())) for i in range(n)]
# i日目にjを選んだ場合の幸福度の総和をdp[i][j]とする。
dp=[[0]*3 for i in range(n+1)]
for i in range(n):
    for j in range(3):
        for k in range(3):
            if j==k:continue
            dp[i+1][k]=max(dp[i+1][k],dp[i][j]+abc[i][k])
ans=0
for i in range(3):
    ans=max(ans,dp[n][i])
print(ans)

Submission status: Accepted

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

happy_list = [[0, 0, 0] for i in range(n)]

happy_list[0][0] = mtx[0][0]
happy_list[0][1] = mtx[0][1]
happy_list[0][2] = mtx[0][2]

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

print(max(happy_list[-1]))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
ABC = np.zeros([N, 3])
for i in range(N):
    ABC[i] = list(map(int, input().split()))

dp = np.zeros([N, 3])
dp[0] = ABC[0]
for i in range(N-1):
    dp[i+1, 0] = max(dp[i, 1], dp[i, 2]) + ABC[i+1, 0]
    dp[i+1, 1] = max(dp[i, 0], dp[i, 2]) + ABC[i+1, 1]
    dp[i+1, 2] = max(dp[i, 0], dp[i, 1]) + ABC[i+1, 2]

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

Submission status: Accepted

Solution code:
def retMax(a,b):
  if a>=b:
    return a
  else:
    return b

n = int(input())
r = []
dpList = [ [0] * 3 for x in range(n)]

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

dpList[0][0] = r[0][0]  
dpList[0][1] = r[0][1]  
dpList[0][2] = r[0][2]  

for s in range(1,n):
  #b->a,c->aの最大値
  dpList[s][0] = retMax(dpList[s-1][1]+r[s][0],dpList[s-1][2]+r[s][0])
  #a->b,c->bの最大値
  dpList[s][1] = retMax(dpList[s-1][0]+r[s][1],dpList[s-1][2]+r[s][1])
  #a->c,b->cの最大値
  dpList[s][2] = retMax(dpList[s-1][0]+r[s][2],dpList[s-1][1]+r[s][2])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    vn = vk = vn_k = 1
    for i in range(1, n+1):
        vn = vn * i % modp
        if i == k:
            vk = vn
        if i == n-k:
            vn_k = vn
    return vn * get_inv(vk, modp) * get_inv(vn_k, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

def main():
    N = ii()
    sa,sb,sc = 0,0,0
    for _ in range(N):
        a,b,c=mis()
        nsa = max(sb,sc)+a
        nsb = max(sc,sa)+b
        nsc = max(sa,sb)+c
        sa,sb,sc = nsa,nsb,nsc
    print(max(sa,sb,sc))

main()

Submission status: Accepted

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

ex = [[1,2], [0,2], [0,1]]
dp = [abc[0]] + [[0]*3 for _ in range(n-1)]

for i in range(n-1):
    for j in range(3):
        dp[i+1][j] = abc[i+1][j] + max([dp[i][k] for k in ex[j]])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
# input
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
dp_a = [0] * n
dp_b = [0] * n
dp_c = [0] * 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], dp_c[i - 1]) + a[i]
  dp_b[i] = max(dp_a[i - 1], dp_c[i - 1]) + b[i]
  dp_c[i] = max(dp_a[i - 1], 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:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n = int(input())
  actions = numpy.array([[float(x) for x in input().strip().split()] for _ in range(n)]).T
  happiness = numpy.zeros((2, 3))
  for i in range(n):
    id = i%2
    happiness[id, 0] = max(happiness[id-1, 1]+actions[1, i], happiness[id-1, 2]+actions[2, i])
    happiness[id, 1] = max(happiness[id-1, 0]+actions[0, i], happiness[id-1, 2]+actions[2, i])
    happiness[id, 2] = max(happiness[id-1, 0]+actions[0, i], happiness[id-1, 1]+actions[1, i])
  print(int(max(happiness[(n-1)%2])))
  pass

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
N = int(input())
T = [list(map(int, input().split())) for i in range(N)]
dp = [[0 for i in range(3)] for j in range(N+1)]
dp[1] = T[0]
for i in range(2,N+1):
    dp[i][0] = max(dp[i-1][1]+T[i-1][0],dp[i-1][2]+T[i-1][0])
    dp[i][1] = max(dp[i-1][0]+T[i-1][1],dp[i-1][2]+T[i-1][1])
    dp[i][2] = max(dp[i-1][0]+T[i-1][2],dp[i-1][1]+T[i-1][2])
print(max(dp[-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)]
dp[0] = abc[0]
for i in range(1, n):
    for j in range(3):
        tmp = 0
        for k in range(3):
            if j != k:
               tmp = max(tmp, dp[i-1][k] + abc[i][j])
        dp[i][j] = tmp

print(max(dp[-1]))

Submission status: Accepted

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

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

Submission status: Accepted

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

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

dp_a = [0]*n
dp_b = [0]*n
dp_c = [0]*n

for i in range(n):
  if i == 0:
    dp_a[i], dp_b[i], dp_c[i] = a[i], b[i], c[i]
  else:
    dp_a[i] = max([a[i]+dp_b[i-1], a[i]+dp_c[i-1]])
    dp_b[i] = max([b[i]+dp_a[i-1], b[i]+dp_c[i-1]])
    dp_c[i] = max([c[i]+dp_b[i-1], c[i]+dp_a[i-1]])
print(max([dp_a[n-1], dp_b[n-1], dp_c[n-1]]))

Submission status: Accepted

Solution code:
N = int(input())
L = [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:
                dp[i+1][j] = max(dp[i+1][j], dp[i][k]+L[i][j])
print(max(dp[N]))

Submission status: Accepted

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

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][0] = ABC[0][0]
    dp[0][1] = ABC[0][1]
    dp[0][2] = ABC[0][2]

    for i in range(1, N):
        for j in [0, 1, 2]:
            score = max(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + ABC[i][j]
            if score > dp[i][j]:
                dp[i][j] += score

    print(max(dp[-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.readline

    n = int(readline())

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

    for i in range(1, n + 1):  # i日目の最大幸福度,1-indexed
        a, b, c = map(int, readline().split())
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a
        dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + b
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c

    print(max(dp[n]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    readline = sys.stdin.readline

    n = int(readline())

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

    for i in range(1, n + 1):  # i日目の最大幸福度,1-indexed
        a, b, c = map(int, input().split())
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a
        dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + b
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c

    print(max(dp[n]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

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

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

Submission status: Accepted

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

import numpy as np
act = np.array(act)
act = np.concatenate([[[0]*3], act])  # 0日目は0にする

# DPテーブル
dp = np.zeros([N+1, 3], dtype='int')

for i in range(1, N+1):  # 1日目からN日目までの幸福度を順番に計算する
    for j in range(3):  # i日目は海か山か家を選択する
        for k in range(3):  # i日目にjの活動をする場合、i-1日目はj以外の活動
            if k == j:
                continue
            dp[i][j] = max(dp[i][j], dp[i-1][k] + act[i][j])
            
print(np.max(dp[-1]))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
import fractions 
import functools 

def pin(type=int):
    return map(type,input().split())

INF = float("inf")

def Flog_1(N,H):
    dp=[INF for i in range(N)]
    dp[0]=0  #h1=0
    dp[1]=abs(H[1]-H[0])
    for i in range(2,N):
        hop1=dp[i-1]+abs(H[i-1]-H[i]) 
        hop2=dp[i-2]+abs(H[i-2]-H[i]) 
        #print(hop1,hop2)
        dp[i]=hop1 if hop1<hop2 else hop2
    return dp
def Flog_1_Another(N,H):
    dp=[INF for i in range(N)]
    dp[0]=0  #h1=0
    for i in range(0,N):
        for k in [1,2]:
            if i+k <N:
                dp[i+k]=min(dp[i+k],dp[i]+abs(H[i+k]-H[i]))
    return dp

def Flog_2(N,K,H):
    dp=[INF for i in range(N)]
    dp[0]=0  #h1=0,default position
    for i in range(1,N):
        temp = INF
        for k in range(1,K+1):
            if i-k < 0:break
            else:
                temp = min(temp,(dp[i-k]+abs(H[i-k]-H[i])))
                
        dp[i]=temp
    return dp
def Flog_2_Another(N,K,H):
    dp=[INF for i in range(N)]
    dp[0]=0  #h1=0
    for i in range(0,N):
        for k in range(1,K+1):
            if i+k <N:
                dp[i+k]=min(dp[i+k],dp[i]+abs(H[i+k]-H[i]))
    return dp
def Flog_2_YETAnother(N,K,H):
    if N == 1:
        return 0
    else:
        map(min,[Flog_2_YETAnother(N-i,K,H) for i in range(1,N+1)])
 
def vacation(N):
   
    dp=[[0]*3 for i in range(N)]
    dp[0]=list(pin())
    for i in range(1,N):
       
        temp=list(pin())
       
        dp[i][0]= max(dp[i-1][1],dp[i-1][2])+temp[0]
        dp[i][1]= max(dp[i-1][2],dp[i-1][0])+temp[1]
        dp[i][2]= max(dp[i-1][0],dp[i-1][1])+temp[2]
        
    return max(dp[-1])

N,=pin()
 
#output
print(vacation(N))

Submission status: Accepted

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

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 = [[0]*3 for _ in range(n)]
dp[0] = [a[0], b[0], 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][0], dp[i-1][1])

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

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

dp[0][0] = A[0]
dp[0][1] = B[0]
dp[0][2] = C[0]

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

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

Submission status: Accepted

Solution code:
n = int(input())
a=[0] * (n+1)
b=[0] * (n+1)
c=[0] * (n+1)
aux = [ [0] * 5 for _ in range(n+1)]

for i in range(1,n+1):
    a[i],b[i],c[i] = input().split()

a = [int(i) for i in a]
b = [int(i) for i in b]
c = [int(i) for i in c]

aux[1][1]=a[1]
aux[1][2]=b[1]
aux[1][3]=c[1]



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

print(max(aux[n][1],aux[n][2],aux[n][3]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
if n==1:
    a,b,c=map(int,input().split())
    print(max(a,b,c))
else:
    a=[]
    b=[]
    c=[]
    dp=[[0 for i in range(3)] for j in range(n)]
    temp=n
    i=1
    flag=0
    while n!=0:
        a,b,c=map(int,input().split())
        if n==temp:
            dp[0][0]=a
            dp[0][1]=b
            dp[0][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)
            i+=1
        n-=1

    if flag==1:
        print(max(a,b,c))
    else:
        print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))

Submission status: Accepted

Solution code:
n = int(raw_input())

mat = []
for i in range(n):
    mat.append(map(int,raw_input().split()))
    
dp = [0,0,0]

for day in range(n):
    ndp = [0,0,0]
    data = mat[day]
    
    for i in range(3):
        for j in range(3):
            if i != j:
                ndp[j] = max(ndp[j], dp[i]+data[j])
    dp = ndp
print max(dp)

Submission status: Accepted

Solution code:
n = int(input())

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

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

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

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

print(max(dp[-1]))

Submission status: Accepted

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

DP = []
for i in range(N+1):
    DP.append([0]*3)

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

# for i in range(N+1):
#     print(DP[i])
ans = max(DP[N])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

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

a, b, c = na()
dp[0][0], dp[0][1], dp[0][2] = a, b, c

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

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

Submission status: Accepted

Solution code:

N = int(input())

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

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

dp[0][0] = activity[0][0]
dp[0][1] = activity[0][1]
dp[0][2] = activity[0][2]

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

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

Submission status: Accepted

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

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [0] * N
b = [0] * N
c = [0] * N
for i in range(N):
    a[i],b[i],c[i] = [int(i) for i in 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] = 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][0],dp[i-1][1])
dp[N-1].sort()
print(dp[N-1][-1])

Submission status: Accepted

Solution code:
n = int(input())

#a_L,b_L,c_L = [],[],[]

#dp = [-1] * (10**5 +1)
# dpテーブル初期化
#dp = [[-1] * 3] * (10**5 +1) これだとダメ
dp=[[-1]*3 for _ in range(n+1)]

for i in range(3):
    dp[0][i] = 0
 
# 値のinput
w_L = [[0,0,0]]

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


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

print(max(dp[n]))

Submission status: Accepted

Solution code:
n=int(input())
ma,mb,mc=0,0,0
for _ in range(n):
  a,b,c=map(int,input().split())
  x,y,z=ma,mb,mc
  ma=a+max([y,z])
  mb=b+max([z,x])
  mc=c+max([x,y])
print(max([ma,mb,mc]))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

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

Submission status: Accepted

Solution code:
N = int(input())
scores = []
for i in range(N):
  scores.append(list(map(int, input().split())))
D = scores[0]
for day in range(1, N):
  D = [max(D[:i] + D[i+1:]) + scores[day][i] for i in range(len(D))]

print(max(D))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
abc = [[int(x) for x in input().split()] for _ in range(N)]
dp = [0,0,0] * N

for i in range(N):
  if i == 0:
    dp[0] = abc[0]
    continue

  dp[i] = [abc[i][0]+max(dp[i-1][1],dp[i-1][2]), \
           abc[i][1]+max(dp[i-1][0],dp[i-1][2]), \
           abc[i][2]+max(dp[i-1][0],dp[i-1][1])]
  
print(max(dp[N-1]))

Submission status: Accepted

Solution code:
n=int(input())
x,y,z=0,0,0
for _ in range(n):
  a,b,c=map(int,input().split())
  x,y,z=a+max(y,z),b+max(z,x),c+max(x,y)
print(max(x,y,z))

Submission status: Accepted

Solution code:
import sys
 
stdin = sys.stdin
 
mod = 1000000007
inf = 1 << 60
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()
 
n = ni()
 
abc = [na() for i in range(n)]
dp = [3 * [0] for i 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(n - 1):
    for j in range(3):
        for k in range(3):
            if k != j:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][k] + abc[i + 1][j])
 
ans = max(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve(n, ABC):
    dp = [[0] * n for _ in range(3)]
    dp[0][0], dp[1][0], dp[2][0] = ABC[0]
    for i in range(1, n):
        for j in range(3):
            dp[j][i] = max(dp[(j + 1) % 3][i - 1], dp[(j + 2) % 3][i - 1]) + ABC[i][j]
    return max(dp[0][n - 1], dp[1][n - 1], dp[2][n - 1])

_n = int(input())
_ABC = [list(map(int, input().split())) for _ in range(_n)]
print(solve(_n, _ABC))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left
INF = float('inf')

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.readline
    N = int(readline())
    ABC = (map(int, readline().split()) for _ in range(N))
    x, y, z = 0, 0, 0
    for a, b, c in ABC:
        x, y, z = a + max(y, z), b + max(x, z), c + max(x, y)

    return max(x, y, z)


if __name__ == "__main__":
    answer = solve()
    print(answer)

Submission status: Accepted

Solution code:
N = int(input())

A_list = [0] * N
B_list = [0] * N
C_list = [0] * N

for i in range(N):
    a, b, c = map(int, input().split())
    A_list[i] = a
    B_list[i] = b
    C_list[i] = c

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

def main():
    N = int(input())
    act = np.array([[int(item) for item in input().split()] for _ in range(N)])

    dp = np.zeros((2, 3), dtype='int64')
    selector = np.array([[0,1,1], [1,0,1], [1,1,0]])

    for i in range(0,N):
        # print(dp[i%2]*selector)
        # print(np.max(dp[i%2]*selector, axis=1))
        dp[i%2^1] = np.max(dp[i%2]*selector, axis=1) + act[i]
        # print(dp)

    print(max(dp[N%2]))

main()

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
  line1 = [int(i) for i in input().split()]
  A.append(line1)
mem = [[0] * 3 for i in range(N)]
mem[0][0] = A[0][0]
mem[0][1] = A[0][1]
mem[0][2] = A[0][2]
for i in range(1, N):
  mem[i][0] = max(mem[i-1][1], mem[i-1][2]) + A[i][0]
  mem[i][1] = max(mem[i-1][0], mem[i-1][2]) + A[i][1]
  mem[i][2] = max(mem[i-1][0], mem[i-1][1]) + A[i][2]
print("%s" % max(mem[N-1]))

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)]  # 初期化　[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]] for n = 4
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:
N = int(input())
Y = []
for _ in range(N):
    Y.append(list(map(int, input().split())))  # Y = [[3, 9, 7], [10, 3, 2]]
dp = [[0] * 3 for _ in range(N)]  # 初期化
dp[0] = Y[0]  # 初期化

# A, B, C の3パターン以外にも対応
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] + Y[i+1][j])
print(max(dp[N-1]))

Submission status: Accepted

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

last = -1

dp = [[None]*3 for i in range(n)]
dp[0] = [0,0,0]
# print(dp)

#dp[i][j] := i日目に行動jを選択したときの幸福度の総和の最大値

for i in range(n+1):
    if i == 0:
        continue
    if i == 1:
        dp[i-1][0] = ABCs[i-1][0]
        dp[i-1][1] = ABCs[i-1][1]
        dp[i-1][2] = ABCs[i-1][2]
        continue
    for j in range(3):

        actions = ABCs[i-1]

        # j以外の選択の中で，最大の幸福をもっているやつ + j
    
        dp[i-1][j] = max([dp[i-2][k] for k in range(3) if k != j]) + ABCs[i-1][j]

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