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

Submission status: Accepted

Solution code:
n = int(input())
dp = [[0 for i in range(3)] for i in range(n)]
H = [list(map(int,input().split())) 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=list(map(int,input().split()))
dp=l.copy()
for i in range(n-1):

	dp1=dp.copy()
	l=list(map(int,input().split()))
	for j in range(3):
		ans=float('-inf')
		for k in range(3):
			if(j!=k):
				ans=max(ans,l[j]+dp[k])
		dp1[j]=ans
	dp=dp1.copy()
print(max(dp))

Submission status: Accepted

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

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

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
N = int(input())

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

happy[0] = [int(x) for x in input().split()]

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

ans = max(happy[N - 1])

print(ans)

Submission status: Accepted

Solution code:

n=list(map(int,input().split()))[0]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
a, b, c = [0], [0], [0]
for i in range(N):
    a_i, b_i, c_i = map(int, input().split())
    a.append(a_i)
    b.append(b_i)
    c.append(c_i)
DP = [[0 for j in range(3)] for i in range(N+1)]
for days in range(1, N+1):
    for ABC in range(3):
        if ABC == 0:
            DP[days][ABC] = max(DP[days-1][1], DP[days-1][2]) + a[days]
        elif ABC == 1:
            DP[days][ABC] = max(DP[days-1][0], DP[days-1][2]) + b[days]
        elif ABC == 2:
            DP[days][ABC] = max(DP[days-1][0], DP[days-1][1]) + c[days]
print(max(DP[N]))

Submission status: Accepted

Solution code:
def solve(n,a,b,c):
    dp = [[0]*3 for _ in range(n)]

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

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








if __name__ == '__main__':
    n = int(input())
    a = []
    b = []
    c = []
    for i in range(n):
        t1,t2,t3 = map(int,input().split())
        a.append(t1)
        b.append(t2)
        c.append(t3)

    solve(n,a,b,c)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# Input#
n = int(input())
# n, k = map(int, input().split())

memo = [[-1] * 3 for i in range(n)]
a = []
b = []
c = []


def dp(i):
    if i != 0:
        memo[i][0] = max(memo[i - 1][1], memo[i - 1][2]) + a[i]
        memo[i][1] = max(memo[i - 1][0], memo[i - 1][2]) + b[i]
        memo[i][2] = max(memo[i - 1][0], memo[i - 1][1]) + c[i]
    return max(memo[i][0], memo[i][1], memo[i][2])


for i in range(n):
    a_in, b_in, c_in = map(int, input().split())
    a.append(a_in)
    b.append(b_in)
    c.append(c_in)
    if i == 0:
        memo[0][0] = a_in
        memo[0][1] = b_in
        memo[0][2] = c_in
    else:
        ans = dp(i)


ans = dp(n - 1)

print("{}".format(ans))

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
#actions=[]
N=int(input())
actions=[[int(x) for x in input().split()] for i in range(N)]
dp=np.zeros((N,3),dtype=int)
dp[0]=actions[0]
for i in range(1,N):
  dp[i][0]=max(dp[i-1][1],dp[i-1][2])+actions[i][0]
  dp[i][1]=max(dp[i-1][0],dp[i-1][2])+actions[i][1]
  dp[i][2]=max(dp[i-1][1],dp[i-1][0])+actions[i][2]
print(max(dp[N-1]))

Submission status: Accepted

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

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

for i in range(N):
  for j in range(3):
    if i == 0:
      dp[i][j] = abc[i][j]
      continue
    op1, op2 = [(1,2),(0,2),(0,1)][j]
    dp[i][j] = max(dp[i-1][op1], dp[i-1][op2])+abc[i][j]
    
print(max(dp[-1]))

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
    a.append([int(s) for s in input().split()])
x=a[0]
for i in range(1,n):
    #print(max(x[1],x[2])+a[i][0])
    x=[max(x[1],x[2])+a[i][0],max(x[0],x[2])+a[i][1],max(x[0],x[1])+a[i][2]]
    #print(x)
print(max(x))

Submission status: Accepted

Solution code:
import math


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


def chmin(a, b):
    if a <= b:
        return a
    return b


def main():
    nn = int(input())
    arr = [list(map(int, input().split())) for l in range(nn)]
    dp = [[0] * 3 for i in range(nn+1)]

    for i in range(nn):
        for j in range(3):
            for k in range(3):
                if j == k:
                    continue
                dp[i+1][j] = chmax(dp[i+1][j],dp[i][k]+arr[i][k])

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


main()

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = []
c = []
for i in range(n):
    ai,bi,ci = [int(x) for x in input().split()]
    a.append(ai)
    b.append(bi)
    c.append(ci)

dp = []
for i in range(n):
    dp.append([-float('inf')]*3)

dp[-1][0] = a[-1]
dp[-1][1] = b[-1]
dp[-1][2] = c[-1]

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

Submission status: Accepted

Solution code:
n = int(input())
a,b,c = map(int,input().split())
for i in range(1,n):
    aa,bb,cc = map(int,input().split())
    aaa,bbb,ccc = a,b,c
    a = max(aa+bbb,aa+ccc)
    b = max(bb+ccc,bb+aaa)
    c = max(cc+aaa,cc+bbb)
print(max(a,b,c))

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

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    # sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass

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

endtime = time.time()
# print(f"Runtime of the program is {endtime - starttime}")

Submission status: Accepted

Solution code:
am = int(input())
val = [[0]*(am+5),[0]*(am+5),[0]*(am+5)]
dp = [[0]*(am+5),[0]*(am+5),[0]*(am+5)]
for i in range(am):
    A,B,C = list(map(int,input().split()))
    val[0][i] = A
    val[1][i] = B
    val[2][i] = C

for i in range(0,am):
    for g in range(3):
        for j in range(3):
            if g!=j:
                dp[g][i+1] = max(dp[g][i+1],dp[j][i]+val[g][i])

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

Submission status: Accepted

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

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

solution[0][0]=happines[0][0]
solution[0][1]=happines[0][1]
solution[0][2]=happines[0][2]

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

print(max(solution[-1]))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
a = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,3])

for i in range(1,N+1):
    for j in range(3):
        dp[i][j] = a[i-1][j]+np.maximum(dp[i-1][(1+j)%3],dp[i-1][(2+j)%3])
print(int(max(dp[N])))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#C
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 for i in range(3)] for j in range(N+1)]
dp[1][0]=a[0]
dp[1][1]=b[0]
dp[1][2]=c[0]
for i in range(2,N+1):    
    for j in range(3):
        if j==0:
            w=a[i-1]
        elif j==1:
            w=b[i-1]
        else:
            w=c[i-1]
        dp[i][j]=max(dp[i-1][(j+1)%3]+w,dp[i-1][(j+2)%3]+w)
print(max(dp[-1]))

Submission status: Accepted

Solution code:
from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
d = [0]
for i in range(n):
    d.append(gil())
dp = [[0 for _ in range(3)] for _ in range(n+1)]
for dx in range(1, n+1):
    ndp = dp[dx]
    #print(ndp)
    for i in range(3):
        for j in range(3):
            if i == j:
                continue
            ndp[i] = max(ndp[i], d[dx][i] + dp[dx-1][j])
    dp[dx] = ndp
#print(dp)
print(max(dp[-1]))

#DP tabular, setting current day dp by comparing previous days costs and finding max to
# pair current cost with prev days

Submission status: Accepted

Solution code:
from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
d = []
for i in range(n):
    d.append(gil())
dp = [[0,0,0]]
for dz in range(n):
    ndp = [0] * 3
    for i in range(3):
        for j in range(3):
            if i != j:
                ndp[i] = max(ndp[i], dp[dz][j] + d[dz][i])
    dp.append(ndp)
#print(dp)
print(max(dp[-1]))

    
# tabular approach

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
a, b, c = [], [], []
for i in range(n):
    x,y,z = gil()
    a.append(x)
    b.append(y)
    c.append(z)
    
mem = [[-1 for _ in range(3)] for _ in range(n+1)]
def rp(i, p):
    global a,b,c,n
    if i >= n:
        return 0
    if mem[i][p] != -1:
        return mem[i][p]
    av = [a[i] + rp(i+1, 0), b[i] + rp(i+1, 1), c[i] + rp(i+1, 2)]
    if p != -1:
        av[p] = 0
    ans = max(av)
    mem[i][p] = ans
    return ans
ans = rp(0, -1)
print(ans)
        
    
# on recursive mem sols, build the solution from the base case,
# ie, return 0 on basecase, and build up the solution.
# because state-cases below will not carry values from above, they only take values from below

Submission status: Accepted

Solution code:
from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
a, b, c = [], [], []
for i in range(n):
    x,y,z = gil()
    a.append(x)
    b.append(y)
    c.append(z)
    
mem = [[-1 for _ in range(3)] for _ in range(n+1)]
def rp(i, p):
    global a,b,c,n
    if i >= n:
        return 0
    if mem[i][p] != -1:
        return mem[i][p]
    av = [a[i] + rp(i+1, 0), b[i] + rp(i+1, 1), c[i] + rp(i+1, 2)]
    if p != -1:
        av[p] = 0
    ans = max(av)
    mem[i][p] = ans
    return ans
ans = rp(0, -1)
print(ans)
        
    
# on recursive mem sols, build the solution from the base case,
# ie, return 0 on basecase, and build up the solution.
# maybe because the values that come later on decide more on what you choose?

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * 3 for _ in range(n + 1)]
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 numpy as np

N = int(input())
a = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,3])

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [0, 0, 0]
for x in range(n):
    new_dp = [0]*3
    happy = [int(x) for x in input().split()]
    for y in range(3):
        for z in range(3):
            if y != z:
                new_dp[y] = max(new_dp[y], dp[z] + happy[y])
    dp = new_dp
print(max(dp[0], dp[1], dp[2]))

Submission status: Accepted

Solution code:
N = int(input())
dp = [[0]*N for _ in range(3)] #dp[k][i] i日目にactivity k を実施する

dp[0][0],dp[1][0],dp[2][0] = map(int,input().split())
for i in range(1,N):
    act= list(map(int,input().split()))
    for k in range(3):
        dp[k][i] = max(dp[(k+1)%3][i-1],dp[(k+2)%3][i-1])+act[k%3]
ans = 0
for k in range(3):
    ans = max(ans,dp[k][-1])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
a = [[int(i) for i in input().split()] for _ in range(N)]
dp = a[0]

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

Submission status: Accepted

Solution code:
N = int(input())

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

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

# 0=A,1=B, 2=C
for i in range(1, N + 1):
    if i == 1:
        dp[i][0] = abc[1][0]
        dp[i][1] = abc[1][1]
        dp[i][2] = abc[1][2]
    else:
        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[-1]))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
x = [0, 0, 0]
for _ in range(int(input())):
    a, b, c = map(int, input().split())
    a += max(x[1], x[2])
    b += max(x[0], x[2])
    c += max(x[0], x[1])
    x = [a, b, c]
print(max(x))

Submission status: Accepted

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

dp=[0,0,0]
for i in range(n):
    nextdp=[]
    for j in range(3):
        x=dp[j+1:]+dp[:j]
        nextdp.append(max(x)+l[i][j])
    dp=nextdp

print(max(dp))

Submission status: Accepted

Solution code:
n=int(input())

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

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


  
for _ in range(n):
  d=list(map(int,input().split()))
  a.append(d)
  
for x in range(n):
  for y in range(3):
    for z in range(3):
      if y!=z:
        dp[x+1][z]=max(dp[x+1][z],dp[x][y]+a[x][z])
        
print(max(dp[n][0],dp[n][1],dp[n][2]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

dp = [[0]*n for i in range(3)]
dp[0][0], dp[1][0], dp[2][0] = a[0],b[0],c[0]
for i in range(1,n):

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

Submission status: Accepted

Solution code:

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

    # initialize dp table
    dp = [[0]*3 for _ in range(N+2)]

    for i in range(N):
        for j in range(3):
            for k in range(3):
                if j == k: continue # can't seclect same choice
                tmp_cost = dp[i][j] + p_list[i][k]
                if dp[i + 1][k] < tmp_cost:
                    dp[i + 1][k] = tmp_cost

    # every chain has maximize sum
    res = 0
    for j in range(3):
        if res < dp[N][j]:
            res = dp[N][j]
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 定数
A = 0
B = 1
C = 2

# リスト
N = int(input())
a = list()
b = list()
c = list()

dp = list()

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

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


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

# N+1日目の幸福度と考えると、添え字は N

print(max(dp[N][A], dp[N][B], dp[N][C]))

Submission status: Accepted

Solution code:
import math
from decimal import *

arr = []
n = int(input())
for _ in range(n):
    arr.append(list(map(int, input().split())))
dp = [[0 for i in range(3)] for i in range(n)]
dp[0][0] = arr[0][0]
dp[0][1] = arr[0][1]
dp[0][2] = arr[0][2]
for i in range(1, n):
    for j in range(3):
        for x in range(3):
            if(x!= j):
                dp[i][j] = max(arr[i][j]+ dp[i-1][x], dp[i][j])
ans = max(dp[n-1][0], dp[n-1][1], dp[n-1][2])
print(ans)

Submission status: Accepted

Solution code:
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]
n = I()
act = [[0,0,0]] + LLI(n)
dp = [[-10**10,-10**10,-10**10] for _ in range(n+1)]
#dp[i][0]はi日目でA選ぶときの幸福度の最大値
#dp[i][1]はi日目でB選ぶときの幸福度の最大値
#dp[i][2]はi日目でC選ぶときの幸福度の最大値
#1-indexedで考えよう
dp[1] = act[1]
for i in range(2,n+1):
    dp[i][0] = max(dp[i-1][1] + act[i][0], dp[i-1][2] + act[i][0])
    dp[i][1] = max(dp[i-1][0] + act[i][1], dp[i-1][2] + act[i][1])
    dp[i][2] = max(dp[i-1][1] + act[i][2], dp[i-1][0] + act[i][2])
print(max(dp[n][0],dp[n][1],dp[n][2]))

Submission status: Accepted

Solution code:
# 解説を見た。
def main():
    days = int(input())
    happiness = [[int(x) for x in input().split()] for _ in range(days)]

    dp = [[0] * 3 for _ in range(days)]
    # dp[i][j]=(i日目に行動jをして、i日目までに得られる幸福度の和の最大値)
    dp[0] = happiness[0]
    selection = set((0, 1, 2))
    for i in range(1, days):
        for sel in selection:
            dp[i][sel] = max(
                dp[i - 1][not_sel] for not_sel in selection - set((sel,))
            ) + happiness[i][sel]
    print(max(dp[days - 1][sel] for sel in selection))


if __name__ == '__main__':
    main()

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

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

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
plans = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0] * (N + 1) for _ in range(3)]

for j in range(N):
    for i_1 in range(3):
        for i_2 in range(3):
            if i_1 == i_2:
                continue
            dp[i_2][j+1] = max(dp[i_2][j+1], dp[i_1][j] + plans[j][i_2])

ans = np.array(dp)
print(ans[:, N].max())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5 + 9)
from collections import defaultdict
dp=defaultdict(lambda:0)
n=int(input())
ar,br,cr=[0]*n,[0]*n,[0]*n

for i in range(n):
	ar[i],br[i],cr[i]=map(int,input().split())
if n==1:
	print(max(ar[0],br[0],cr[0]))
	exit()
def points(i,pv):
	if dp[(i,pv)] != 0:
		return dp[(i,pv)]
	if pv==1:
		x,y=br[i],cr[i]
		a,b=2,3
	elif pv==2:
		x,y=ar[i],cr[i]
		a,b=1,3
	else:
		x,y=ar[i],br[i]
		a,b=1,2
	if i==n-1:
		return max(x,y)
	ax=points(i+1,a)+x
	by=points(i+1,b)+y
	ans=max(by,ax)
	dp[(i,pv)]=ans
	return ans
p=points(1,1)+ar[0]
q=points(1,2)+br[0]
r=points(1,3)+cr[0]
print(max(p,q,r))

Submission status: Accepted

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

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

print(max(dp[-1]))

Submission status: Accepted

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
A = 0
B = 1
C = 2


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

dp = [[0] * 3 for i in range(N+1)]
dp[1][A] = a[1]
dp[1][B] = b[1]
dp[1][C] = c[1]

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

print(max(dp[N][A], dp[N][B], dp[N][C]))

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
number=int(input())
vacation = [list(map(int,input().rstrip().split())) for _ in range(number)]
#print(vacation)
#capable = deque([0,1,2])
#did = deque([])
#print(max(vacation[0]))
table = [[0]*3 for _ in range(number+1)]
for i in range(1,number+1):
    table[i][0] = max(table[i-1][1],table[i-1][2]) + vacation[i-1][0]
    table[i][1] = max(table[i-1][0],table[i-1][2]) + vacation[i-1][1]
    table[i][2] = max(table[i-1][0],table[i-1][1]) + vacation[i-1][2]
print(max(table[number]))

Submission status: Accepted

Solution code:
import math
n = int(input())

a = []
b = []
c = []
for _ in range(n):
	x,y,z = list(map(int,input().split()))
	a.append(x)
	b.append(y)
	c.append(z)
 
dp = [[0 for _ 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:
from pprint import pprint
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*3 for _ in range(n)]
dp[0]=l[0]
for i in range(1,n):
    for j in range(3):
        dp[i][j]=max(dp[i-1][(j+1)%3]+l[i][j],dp[i-1][(j+2)%3]+l[i][j])
print(max(dp[n-1]))
# pprint(dp)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    abc = [None] * N
    for i in range(N):
        abc[i] = tuple(map(int, input().split()))

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:


INF = float('inf')


def tc():
    n = int(input())
    a = [tuple(map(int, input().split())) for _ in range(n)]

    # dp[i][j]: max happiness on day i+1 if you do act j (a, b, c)
    dp = [[0] * 3 for _ in range(n)]
    dp[0] = a[0]

    # since from one stone you can go to many
    # try using push dp instead of pull
    for i in range(n - 1):
        dp[i + 1][0] = max(dp[i][1], dp[i][2]) + a[i + 1][0]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + a[i + 1][1]
        dp[i + 1][2] = max(dp[i][0], dp[i][1]) + a[i + 1][2]

    print(max(dp[-1]))


tc()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

dp_table = [[0] * N for j in range(3)]

a, b, c = map(int, input().split())
dp_table[0][0] = a
dp_table[1][0] = b
dp_table[2][0] = c

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

print(max(dp_table[0][N-1], dp_table[1][N-1], dp_table[2][N-1]))