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:
from sys import stdin
import numpy as np

n = int(stdin.readline().strip())
abc_lst = []

for i in range(n):
  abc = [int(x) for x in stdin.readline().strip().split()]
  abc_lst.append(abc)
  
hapiness_mat = np.zeros((n, 3))
hapiness_mat[0] = abc_lst[0]

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
abc  = [[], [], []]

for i in range(n): # DB取得方法のみ違う, 分かればどっちでもok
    tmp_1, tmp_2, tmp_3 = map(int, input().split())
    abc[0].append(tmp_1)
    abc[1].append(tmp_2)
    abc[2].append(tmp_3)
#print(abc)

dp = [[0,0,0] for _ in range(n)]
dp[0] = [abc[0][0], abc[1][0], abc[2][0]]
#print(dp)

for i in range(1, n):
    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[j][i]) # ここのDB指定方法に影響

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())
abc  = [[], [], []]

abc = [list(map(int, input().split())) for _ in range(n)] # DB取得方法のみ違う, 分かればどっちでもok
#print(abc)

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

for i in range(1, n):
    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]) # ここのDB指定方法に影響

print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N = int(readline().rstrip())
L = []
for _ in range(N):
    a, b, c = map(int, readline().split())
    L.append((a, b, c))


dp = [[0 for _ in range(3)] for _ in range(N)]
dp[0][0] = L[0][0]
dp[0][1] = L[0][1]
dp[0][2] = L[0][2]
for i in range(1, N):
    a, b, c = L[i]
    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

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

Submission status: Accepted

Solution code:
n = int(input())

da = db = dc = 0

for i in range(n):
    a, b, c = map(int, input().split())
    da, db, dc = max(db, dc) + a, max(da, dc) + b, max(da, db) + c
print(max(da, db, dc))

Submission status: Accepted

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

dp[0][0]=arr[0][0]
dp[0][1]=arr[0][1]
dp[0][2]=arr[0][2]

for i in range(1,n):
    dp[i][0]=arr[i][0]+max(dp[i-1][2],dp[i-1][1])
    dp[i][1] = arr[i][1] + max(dp[i-1][2], dp[i-1][0])
    dp[i][2] = arr[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())
a = [list(map(int,input().split())) for i in range(n)]
cost = [[0]*3 for i in range(n+1)]
for i in range(n):
    cost[i+1][0] = max(cost[i][1], cost[i][2]) + a[i][0]
    cost[i+1][1] = max(cost[i][0], cost[i][2]) + a[i][1]
    cost[i+1][2] = max(cost[i][0], cost[i][1]) + a[i][2]
print(max(cost[n]))

Submission status: Accepted

Solution code:


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

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

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    dp = [[0]*3 for i in range(N+1)]
    #dp[i][j] iまでで、j=0はaを選ぶ,j=1はbを選ぶ,j=2はcを選ぶ
    for i in range(1,N+1):
        a, b, c=map(int,input().split())
        dp[i][0] = max(dp[i-1][1]+a, dp[i-1][2]+a, dp[i][0])
        dp[i][1] = max(dp[i-1][2]+b, dp[i-1][0]+b, dp[i][1])
        dp[i][2] = max(dp[i-1][0]+c, dp[i-1][1]+c, dp[i][2])

    print(max(dp[N]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
aa = []
bb = []
cc = []
aDP = [0]*N
bDP = [0]*N
cDP = [0]*N
for i in range(N):
    a,b,c = [int(x) for x in input().split()]
    aa.append(a)
    bb.append(b)
    cc.append(c)
aDP[0] = aa[0]
bDP[0] = bb[0]
cDP[0] = cc[0]
for i in range(1,N):
    aDP[i] = max(bDP[i-1] + aa[i],cDP[i-1]+aa[i])
    bDP[i] = max(aDP[i-1] + bb[i],cDP[i-1]+bb[i])
    cDP[i] = max(bDP[i-1] + cc[i],aDP[i-1]+cc[i])
print(max(max(aDP[N-1],bDP[N-1]),cDP[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())
a= [0]+a
b= [0]+b
c= [0]+c
    
dp=[[0]*(N+1) for _ in range(3)]
for i in range(1,N+1):
    dp[0][i] = max(dp[1][i-1],dp[2][i-1])+a[i]
    dp[1][i] = max(dp[0][i-1],dp[2][i-1])+b[i]
    dp[2][i] = max(dp[0][i-1],dp[1][i-1])+c[i]
maxi=0
for k in dp:
    maxi=max(maxi,k[-1])
print(maxi)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
I = lambda : list(map(int,input().split()))

n,=I()
l=[];dp=[[0,0,0] for i in range(n)]
for i in range(n):
	l.append(I())
dp[0]=list(l[0])
for i in range(1,n):
	dp[i][0]=l[i][0]+max(dp[i-1][1],dp[i-1][2])
	dp[i][1]=l[i][1]+max(dp[i-1][0],dp[i-1][2])
	dp[i][2]=l[i][2]+max(dp[i-1][1],dp[i-1][0])
print(max(dp[n-1]))

Submission status: Accepted

Solution code:
def vacation(n, a):
  dp = [0]*3

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

    
  for i in range(1, n):
    temp = [0]*3
    for j in range(3):
      for k in range(3):
        if(j!=k):
          temp[j] = max(temp[j], dp[k]+a[i][j])
    dp = temp
  return max(dp)
    


n = int(input())
a = []
for i in range(n):
  g = list(map(int, input().split()))
  a.append(g)
print(vacation(n, a))

Submission status: Accepted

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

N = int(input())

dp = [[0, 0, 0] for i in range(N)]
dp[0] = [int(i) for i in input().split()]
for i in range(1, N):
    V = [int(i) for i in input().split()]
    dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + V[0]
    dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + V[1]
    dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + V[2]

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
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]*3 for i in range(n)]
dp[0][0] = A[0]
dp[0][1] = B[0]
dp[0][2] = C[0]

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

Submission status: Accepted

Solution code:
# key not available ""
n = int(input())
matrix = []
for _ in range(n):
    matrix.append([int(i) for i in input().split()])
dp = [[0 for i in range(3)] for j in range(n)]
for i in range(3):
    dp[0][i] = matrix[0][i]
for i in range(1,n):
    for j in range(3):
        if j == 0:
            dp[i][j] = max(dp[i-1][j+1],dp[i-1][j+2])+matrix[i][j]
        elif j == 1:
            dp[i][j] = max(dp[i-1][j+1],dp[i-1][j-1])+matrix[i][j]
        else:
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j-2]) + matrix[i][j]
print(max(dp[-1]))

Submission status: Accepted

Solution code:

def hapi(N,H):
    DP = [[0]*3 for i in range(N+1)]
    #print(H)
    for i in range(1,N+1):
        for j in range(3):
            for k in range(3):
                if j != k:
                    #print(j,k)
                    #print(H[i-1][j])
                    #print(DP[i-1][j],DP[i][k]+H[i-1][j])
                    DP[i][j] = chmax(DP[i][j],DP[i-1][k]+H[i-1][j])
    return DP

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

if __name__ == '__main__':
    N = int(input())
    H = [[0]*3 for i in range(N)]
    for i in range(N):   
        lst = list(map(int,input().split()))
        H[i] = lst
    ans = hapi(N,H)
    print(max(ans[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    n, *abc = map(int, open(0).read().split())
    dp = [0] * ((n + 1) * 3)
    a = 0
    b = 1
    c = 2
    for i in range(0, n * 3, 3):
        dp[i + a + 3] = max(dp[i + b], dp[i + c]) + abc[i + a]
        dp[i + b + 3] = max(dp[i + c], dp[i + a]) + abc[i + b]
        dp[i + c + 3] = max(dp[i + a], dp[i + b]) + abc[i + c]
        a,b,c = b,c,a
    #print(dp)
    print(max(dp[-1], dp[-2], dp[-3]))

main()

Submission status: Accepted

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

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

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

    elif j==1:
      dp[i+1][j]=max(dp[i][0],dp[i][2])+abc[i+1][j]

    else:
      dp[i+1][j]=max(dp[i][1],dp[i][0])+abc[i+1][j]

print(max(dp[n]))
#print(dp)

Submission status: Accepted

Solution code:
n = int(input())

INF = 1 << 20
dp = [[INF] * (n + 1) for _ in range(3)]

# dp初期化
for i in range(3):
    dp[i][-1] = 0

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

print(max(list(zip(*dp))[n - 1]))

Submission status: Accepted

Solution code:
def resolve():
	# 夏休みの日数
	N = int(input())
	# 日ごとの行動A,B,Cによって得られる幸福度
	ABC = [
		map(int, input().split())
		for _ in range(N)
	]
	# 今日行動A,B,Cをする事で得られる、幸福度の累計
	Va, Vb, Vc = ABC.pop()
	for _ in range(N-1):
		a, b, c = ABC.pop()
		Va, Vb, Vc = max(Vb, Vc) + a, max(Va, Vc) + b, max(Va, Vb) + c
	print(max(Va, Vb, Vc))
resolve()

Submission status: Accepted

Solution code:
def resolve():
	N = int(input())
	A, B, C = [], [], []
	for _ in range(N):
		a, b, c = map(int, input().split())
		A.append(a), B.append(b), C.append(c)
	# dp_A[i]： i日目にAを選んで得られる最大の幸福度
	dp_A = [0] * N
	dp_B = [0] * N
	dp_C = [0] * N
	dp_A[0], dp_B[0], dp_C[0] = A[0], B[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_B[i-1], dp_A[i-1]) + C[i]
	print(max(dp_A[N-1], dp_B[N-1], dp_C[N-1]))
    
resolve()

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

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

Submission status: Accepted

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

N=int(input())

abc=[]
kohuku=[]

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

    if k==0:
        kohuku.append(abc)
    else:
        tuika=[0,0,0]
        tuika[0]=max(kohuku[k-1][1],kohuku[k-1][2])+abc[0]
        tuika[1]=max(kohuku[k-1][0],kohuku[k-1][2])+abc[1]
        tuika[2]=max(kohuku[k-1][0],kohuku[k-1][1])+abc[2]
        kohuku.append(tuika)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from copy import deepcopy
n = int(input())
eff = [list(map(int, input().split())) for _ in range(n)]

dp = [[float('-inf')] * 3 for _ in range(n)]

dp[0] = deepcopy(eff[0])

for i in range(1, n):
    for yi in range(3):
        for ti in range(3):
            if yi != ti:
                dp[i][ti] = max(dp[i][ti], dp[i-1][yi] + eff[i][ti])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())

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

dp = [[float('-inf')] * 3 for _ in range(n)]

from copy import deepcopy

dp[0] = deepcopy(eff[0])

for i in range(1, n):
    for yi in range(3):
        for ti in range(3):
            if yi != ti:
                dp[i][ti] = max(dp[i][ti], dp[i-1][yi] + eff[i][ti])

print(max(dp[-1]))

Submission status: Accepted

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


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

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

print(max(dp[-1]))

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

print(max(dp[-1]))

Submission status: Accepted

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


n=int(input())
a1=[[int(i) for i in input().split()]for j in range(n)]

print(solve(n,a1))

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)]
a,b,c = abc[0]
dp[0][0] = a
dp[0][1] = b
dp[0][2] = c

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

Submission status: Accepted

Solution code:
N = int(input())

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

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

Submission status: Accepted

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)


N = int(input())
abc = int_mtx(N)

#f_inf = float("inf")
#dp = [f_inf]*N
dp = np.array([[0,0,0]]*N)

dp[0][0] = abc[0][0]
dp[0][1] = abc[0][1]
dp[0][2] = abc[0][2]

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n=int(input())

dp=list(map(int,input().split()))
for day in range(1,n):
    m=[0]*3
    day_points=list(map(int, input().split()))
    for i in range(3):
        for j in range(3):
            if i!=j:
                 m[i]=max(m[i],day_points[i]+dp[j])
    dp=m
print(max(dp))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

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

n = ni()
a = [0]*n
b = [0]*n
c = [0]*n
for i in range(n):
  a[i],b[i],c[i] = na()
dpa = [a[0]]+[0]*(n-1)
dpb = [b[0]]+[0]*(n-1)
dpc = [c[0]]+[0]*(n-1)

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

Submission status: Accepted

Solution code:
n=int(input())
abc=[]
for i in range(n):
    x=tuple(map(int,input().split()))
    abc.append(x)
dp=[[0]*n for _ in range(3)]
for i in range(3):
    dp[i][0]=abc[0][i]

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

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

Submission status: Accepted

Solution code:
import sys
def maxcost(li,n):
    dp=[[-1 for j in range(3)] for i in range(n)]
    dp[n-1][0],dp[n-1][1],dp[n-1][2]=li[n-1][0],li[n-1][1],li[n-1][2]
    for i in range(n-2,-1,-1):
        for j in range(3):
            mx=-sys.maxsize
            for k in range(3):
                if j!=k:
                    mx=max(mx,dp[i+1][k]+li[i][j])
            dp[i][j]=mx
    return max(dp[0][0],dp[0][1],dp[0][2])

n=int(input())
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
print(maxcost(li,n))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def maxcost(li,n,i,strt,dp):
    if i==(n-1):
        return li[i][strt]
    mx=-sys.maxsize
    for l in range(3):
        if l!=strt:
            if dp[i+1][l]==-1:
                cost=maxcost(li,n,i+1,l,dp)
                dp[i+1][l]=cost
            else:
                cost=dp[i+1][l]
            mx=max(mx,cost+li[i][strt])
    return mx


n=int(input())
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
dp=[[-1 for j in range(3)] for i in range(n)]
print(max(maxcost(li,n,0,0,dp),maxcost(li,n,0,1,dp),maxcost(li,n,0,2,dp)))

Submission status: Accepted

Solution code:
days = int(input())
total = [[int(happy) for happy in input().split()]]
for i in range(1, days):
    nums = [int(happy) for happy in input().split()]
    today = [max([total[i-1][1]+nums[0], total[i-1][2]+nums[0]]), max([total[i-1][0]+nums[1], total[i-1][2]+nums[1]]), max([total[i-1][0]+nums[2], total[i-1][1]+nums[2]])]
    total.append(today)
print(max(total[days-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 y in range(3):
        for t in range(3):
            if y != t:
                dp[i + 1][t] = max(dp[i + 1][t], dp[i][y] + abc[i][t])

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

Submission status: Accepted

Solution code:
def solve(n,d):
    big = float('inf')
    small = float('-inf')
    for s in range(n - 2,-1,-1):
        row = [0,0,0]
        for j in range(3):
            i = s + 1
            if j == 0:
                row[j] = max(d[i][1],d[i][2]) + d[s][j]
            elif j == 1:
                row[j] = max(d[i][0],d[i][2]) + d[s][j]
            else:
                row[j] = max(d[i][1],d[i][0]) + d[s][j]
        d[s] = row

    return max(d[0])


def main():
    t = int(input())
    board = []
    for i in range(t):
        # n = int(input())
        d = input()
        d = [int(i) for i in d.split()]
        board.append(d)
    ans = solve(t,board)
    print(ans)
        
main()

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

# ここから書き始める
n = int(input())
a = [0 for i in range(n)]
b = [0 for i in range(n)]
c = [0 for i in range(n)]
for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())
dp = [[0 for i in range(3)] for i in range(n)]
for i in range(n):
    if i == 0:
        dp[i][0] = a[i]
        dp[i][1] = b[i]
        dp[i][2] = c[i]
        continue
    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[-1]))

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for _ in range(n):
    a,b,c=map(int,input().split())
    l.append((a,b,c))
dp=[[0 for i in range(3)]for i in range(n+1)]
for i in range(1,n+1):
    dp[i][0]=l[i-1][0]+max(dp[i-1][1],dp[i-1][2])
    dp[i][1]=l[i-1][1]+max(dp[i-1][0],dp[i-1][2])
    dp[i][2]=l[i-1][2]+max(dp[i-1][0],dp[i-1][1])
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][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 range(3):
        for k in range(3):
            if j == k:
                continue
            dpp = dp[i - 1][j] + abc[i][k]
            dp[i][k] = max(dp[i][k], dpp)

print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
x,y,z = 0,0,0 #最後にやったものの幸福度最大値
for i in range(N):
  a,b,c = map(int, readline().split())
  x,y,z = max(y,z)+a,max(x,z)+b,max(x,y)+c

print(max(x,y,z))

Submission status: Accepted

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

Submission status: Accepted

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

print(max(dp[N]))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N = int(readline())
dp = [[0,0,0] for i in range(N)]
dp[0] = list(map(int,readline().split()))
for i in range(1,N):
    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][0],dp[i-1][2]) + b
    dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + c
print(max(dp[N-1]))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N = int(readline())
dp = [[0]*3 for i in range(N)]
dp[0] = list(map(int,readline().split()))
for i in range(1,N):
    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][0],dp[i-1][2]) + 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())
dp = [[0]*3 for i in range(N)]
dp[0] = list(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],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-1]))