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:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    ABC=[tuple(map(int,input().split())) for i in range(n)]
    dp=[[0,0,0]for _ in range(n+1)] #i日目にjをするときの幸福度の総和
    for i in range(n):
        ni=i+1
        dp[ni][0]=max(dp[i][1],dp[i][2])+ABC[ni-1][0]
        dp[ni][1]=max(dp[i][0],dp[i][2])+ABC[ni-1][1]
        dp[ni][2]=max(dp[i][0],dp[i][1])+ABC[ni-1][2]
    print(max(dp[n]))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_c

n = int(input())

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

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

for i in range(1, n):
    act = acts[i]
    m = [0] * 3
    # i implies curr day
    # j implies prev day
    for i in range(3): 
        temp = []
        for j in range(3):
            if i != j:
                temp.append(act[i] + dp[j])
        m[i] = max(temp)
    dp = m
print(max(dp))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  a=[]
  b=[]
  c=[]
  for _ in range(n):
    x,y,z=LI()
    a.append(x)
    b.append(y)
    c.append(z)

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

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

# main()
print(main())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N = I()
A = [LI() for _ in range(N)]
dp = [[0]*3 for _ in range(N)]
dp[0] = A[0]
for i,j,k in itertools.product(range(1,N),[0,1,2],[0,1,2]):
    if j==k:
        continue
    dp[i][j] = max(dp[i][j],dp[i-1][k]+A[i][j])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())
h = [list(map(int, input().split())) for _ in range(N)] #1-index

def chmax(a,b):
    if a >= b:
        return a
    else:
        return b
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
            dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + h[i][k])

print(max(dp[N]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import bisect
import numpy as np

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

dp = np.ones((N, 3))*-float("inf")

dp[0] = ABC[0]

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

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

Submission status: Accepted

Solution code:
n=int(input())
l=[[None for i in range(3) ] for i in range(n)]
for i in range(n):
    a,b,c=list(map(int,input().split()))
    l[i][0]=a
    l[i][1]=b
    l[i][2]=c
l1=[[None for i in range(3) ] for i in range(n)]
a=l1[0][0]=l[0][0]
b=l1[0][1]=l[0][1]
c=l1[0][2]=l[0][2]
q=max(a,b,c)
for i in range(1,n):
    a=l1[i][0]=l[i][0]+max(l1[i-1][1],l1[i-1][2])
    b=l1[i][1]=l[i][1]+max(l1[i-1][0],l1[i-1][2])
    c=l1[i][2]=l[i][2]+max(l1[i-1][1],l1[i-1][0])
    if q<max(a,b,c):
        q=max(a,b,c)
print(q)

Submission status: Accepted

Solution code:
n=int(input())
ll=[]
for i in range(n):
    l=list(map(int,input().split()))
    ll.append(l)
dp=[[0]*3 for i in range(n)]
dp[0]=ll[0]

for i in range(1,n):
    for j in range(3):
        if(j==0):
            dp[i][j]=ll[i][j]+max(dp[i-1][1],dp[i-1][2])
        if(j==1):
            dp[i][j]=ll[i][j]+max(dp[i-1][0],dp[i-1][2])
        if(j==2):
            dp[i][j]=ll[i][j]+max(dp[i-1][1],dp[i-1][0])
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, 0, 0] for _ in range(100010)]

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = max(dp[i+1][k], dp[i][j] + a[i][k])
print(max(dp[N]))
#配るDP
# dp[i+1] = min(dp[i+1], dp[i] + abs(h[i+1] - h[i]))

Submission status: Accepted

Solution code:
N=int(input())
A=[0]*(N+1)
B=[0]*(N+1)
C=[0]*(N+1)
#dp=[[0]*(N+1)]*3 #同じインデックスのものが全て更新される
dp=[[0 for _ in range(N+1)] for _ in range(3)]

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N = int(input())
    act_list = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        act_list.append((a, b, c))

    # dp[i][j] = i日目までにjを最後に行って得られる最大の幸福度
    dp = [[0] * 3 for _ in range(N)]
    dp[0][0] = act_list[0][0]
    dp[0][1] = act_list[0][1]
    dp[0][2] = act_list[0][2]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

print(max(DP[-1]))

Submission status: Accepted

Solution code:
import itertools
n = int(input())
lst = [[0,0,0]]

for _ in range(n):
  l = list(map(int, input().split()))
  lst.append(l)
  
hp = [[0] * 3 for _ in range(n+1)]

plst = list(itertools.permutations([_ for _ in range(3)], 2))

for _ in range(0, n):
    for i in plst:
      hp[_+1][i[1]] = max(hp[_][i[0]] + lst[_+1][i[1]], hp[_+1][i[1]])

print(max(hp[n]))

Submission status: Accepted

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

    # min -> inf, max -> -1
    #dp = [[-1]*3]*n # <-NGNGNGNG
    dp = [[-1]*3 for _ in range(n)]

    # shoki joken
    dp[0] = abc[0]
    for i in range(1,n):
        # j != k
        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]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# C Vacation

n = int(input())
h_list = [[int(x) for x in input().split()] for i in range(n)]

dp = [[float("-Inf")] * n for i in range(3)]

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

Submission status: Accepted

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

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

# dp[i + 1][j] := i 日目までの活動履歴のうち、最終日であるi日目には活動
# j(0: A, 1: B, 2: C) を選んだ場合の、得られる幸福度の最大値
# dp[ i ][ 0 ] から dp[ i + 1 ][ 1 ] への遷移
# dp[ i ][ 0 ] から dp[ i + 1 ][ 2 ] への遷移
# dp[ i ][ 1 ] から dp[ i + 1 ][ 0 ] への遷移
# dp[ i ][ 1 ] から dp[ i + 1 ][ 2 ] への遷移
# dp[ i ][ 2 ] から dp[ i + 1 ][ 0 ] への遷移
# dp[ i ][ 2 ] から dp[ i + 1 ][ 1 ] への遷移
# 日付
for i in range(n):
    for j in range(3):
        for k in range(3):
            if i == 0:
                dp[i + 1][k] = happiness[i][k]
            elif j == k:
                continue
            else:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][k] + happiness[i][j])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
def vacation(n, nums):
    dp = [nums[0]]
    for i in range(1, n):
        dp.append([
            nums[i][0] + max(dp[-1][1], dp[-1][2]),
            nums[i][1] + max(dp[-1][0], dp[-1][2]),
            nums[i][2] + max(dp[-1][0], dp[-1][1])
        ])
    return max(dp[-1])


n = int(input())
nums = []
for _ in range(n):
    row = [int(i) for i in input().split()]
    nums.append(row)

ans = vacation(n, nums)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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_list[i][j])
                
print(max(dp[n - 1]))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
happiness = []
for _ in range(n):
    a,b,c = map(int,input().split())
    happiness.append((a,b,c,a,b,c))
#最後に選ぶのがa,b,c各々の時の幸福度の最大値
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 k != j:
                dp[i][j] = max(dp[i][j],dp[i-1][k] + happiness[i-1][j])
print(max(dp[n]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!


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

Submission status: Accepted

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

def main():
    n = int(input())
    colA, colB, colC = map(int, input().split())
    for i1 in range(1, n):
        a, b, c = map(int, input().split())
        colA, colB, colC = a + max(colB, colC), b + max(colA, colC), c + max(colA, colB)
    print(max(colA, colB, colC))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# dp[j] stores the max happiness doing activity j on the current
dp = [0]*3

for i in range(n):
    prev = dp.copy()
    for j in range(3):
        dp[j] = happymat[i][j] + max(prev[(j+1)%3], prev[(j+2)%3])

print(max(dp))

Submission status: Accepted

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

# dp[i][j] stores the max happiness after day i ... doing activity j on that day
dp[0][0] = happymat[0][0]
dp[0][1] = happymat[0][1]
dp[0][2] = happymat[0][2]

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

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

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
import sys
readline = sys.stdin.buffer.readline
geta = lambda fn: map(fn, readline().split())
gete = lambda fn: fn(readline())

def main():
    N = gete(int)
 
    cur, prev = [0]*3, [0]*3
    
    for _ in range(N):
        a, b, c = geta(int)
        prev, cur = cur, prev
        cur[0] = max(prev[1], prev[2]) + a
        cur[1] = max(prev[2], prev[0]) + b
        cur[2] = max(prev[0], prev[1]) + c
    
    
    print(max(cur))

	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
import sys
readline = sys.stdin.buffer.readline
geta = lambda fn: list(map(fn, readline().split()))
gete = lambda fn: fn(readline())

def main():
	n=gete(int)
	dp=[[0]*3 for _ in range(n+1)]
	
	
	for i in range(n):
		a,b,c = geta(int)
		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:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
import sys
readline = sys.stdin.buffer.readline
geta = lambda fn: map(fn, readline().split())
gete = lambda fn: fn(readline())

def main():
	n=gete(int)
	dp=[[0]*3 for _ in range(n+1)]
	
	
	for i in range(n):
		a,b,c = geta(int)
		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:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: map(fn, input().split())
gete = lambda fn: fn(input())

def main():
	n=gete(int)
	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:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: map(fn, input().split())
gete = lambda fn: fn(input())

def main():
	n=gete(int)
	dp=[[0]*3 for _ in range(n+1)]
	
	
	for i in range(n):
		a,b,c = geta(int)
		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:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
	n=gete(int)
	dp=[[0]*3 for _ in range(n+1)]
	
	
	for i in range(n):
		a,b,c=geta(int)
		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:
# copy and paste (check calc time)
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:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
    N = gete(int)
    a = [0]*(N+1)
    b, c = a[:], a[:]

    for i in range(N):
        av, bv, cv = geta(int)
        a[i+1] = max(av + b[i], av + c[i])
        b[i+1] = max(bv + c[i], bv + a[i])
        c[i+1] = max(cv + a[i], cv + b[i])

    print(max(a[-1], b[-1], c[-1]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
    N = gete(int)
    a = [0]*(N+1)
    b, c = a[:], a[:]

    for i in range(N):
        av, bv, cv = geta(int)
        a[i+1] = av + max(b[i], c[i])
        b[i+1] = bv + max(c[i], a[i])
        c[i+1] = cv + max(a[i], b[i])

    print(max(a[-1], b[-1], c[-1]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
    N = gete(int)
    p, q, r = 0,0,0
    for _ in range(N):
        a,b ,c = geta(int)
        p,q,r = a + max(q,r), b + max(r,p), c + max(p,q)

    print(max(p,q,r))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
    N = gete(int)
    cur = [0]*3 
    for _ in range(N):
        a = geta(int)
        cur = [max(cur[j-1], cur[j-2]) + a[j] for j in range(3)] 

    print(max(cur))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
    N = gete(int)
    a = (geta(int) for _ in range(N))

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

    for i, ai in enumerate(a):
        for j in range(3):
            dp[i+1][j] = max(dp[i][j-1], dp[i][j-2]) + ai[j] 


    print(max(dp[N]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

def main():
    N = gete(int)

    cur, prev = [0]*3, [0]*3

    for _ in range(N):
        a, b, c = geta(int)
        prev, cur = cur, prev
        cur[0] = max(prev[1], prev[2]) + a
        cur[1] = max(prev[2], prev[0]) + b
        cur[2] = max(prev[0], prev[1]) + c


    print(max(cur))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

N = gete(int)

cur, prev = [0]*3, [0]*3

for _ in range(N):
    a, b, c = geta(int)
    prev, cur = cur, prev
    cur[0] = max(prev[1], prev[2]) + a
    cur[1] = max(prev[2], prev[0]) + b
    cur[2] = max(prev[0], prev[1]) + c


print(max(cur))

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
dp = np.zeros((n,3), dtype='int64')
l = np.array(l)
dp[0] = 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][0], dp[i-1][1])
print(np.max(dp[n-1]))

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

N = gete(int)

cur = [0] * 3

for _ in range(N):
    a, b, c = geta(int)
    prev = cur[:]
    cur[0] = max(prev[1], prev[2]) + a
    cur[1] = max(prev[2], prev[0]) + b
    cur[2] = max(prev[0], prev[1]) + c

print(max(cur))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def solve(n,pos):
    global data,helper
    if(n==-1):
        return 0
    if(helper[n][pos]!=-1):
        return helper[n][pos]
    if(pos==0):
        helper[n][pos]=max(data[n][1]+solve(n-1,1),data[n][2]+solve(n-1,2))
        return helper[n][pos]
    elif(pos==1):
        helper[n][pos] = max(data[n][0]+solve(n-1,0),data[n][2]+solve(n-1,2))
        return helper[n][pos]
    else:
        helper[n][pos] = max(data[n][1]+solve(n-1,1),data[n][0]+solve(n-1,0))
        return helper[n][pos]
n=int(input())
data=[]
helper=[[-1 for y in range(3)] for x in range(n)]
for _ in range(n):
    temp=[int(x) for x in input().split()]
    data.append(temp)
t1=data[-1][0]+solve(n-2,0)
t2=data[-1][1]+solve(n-2,1)
t3=data[-1][2]+solve(n-2,2)
print(max(t1,t2,t3))

Submission status: Accepted

Solution code:
n=int(input())
data=[]
t=[[0 for x in range(4)] for w in range(n+1)]
for _ in range(n):
    temp=[int(x) for x in input().split()]
    data.append(temp)
for i in range(1,n+1):
    for j in range(1,4):
        large=0
        for w in range(1,4):
            if(w==j):
                continue
            else:
                if(t[i-1][w]>large):
                    large=t[i-1][w]
        t[i][j]=data[i-1][j-1]+large
print(max(t[-1]))

Submission status: Accepted

Solution code:
N=int(input())

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

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

Submission status: Accepted

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))

def main():
    n=I()
    a=[]
    b=[]
    c=[]
    for i in range(n):
        tmp=L()
        a.append(tmp[0])
        b.append(tmp[1])
        c.append(tmp[2])
    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(n-1):
        dp[i+1][0]=max(dp[i+1][0],dp[i][1]+a[i+1],dp[i][2]+a[i+1])
        dp[i+1][1]=max(dp[i+1][1],dp[i][0]+b[i+1],dp[i][2]+b[i+1])
        dp[i+1][2]=max(dp[i+1][2],dp[i][0]+c[i+1],dp[i][1]+c[i+1])
    print(max(dp[n-1]))
        
        
    
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

    dp = [[- float('inf') for i in range(3)] for j in range(n + 1)]
    dp[0] = [0] * 3
    for i in range(n):
        for j in range(3):
            for k in range(3):
                if (j == k):
                    continue
                dp[i + 1][k] = max(dp[i + 1][k],
                                   dp[i][j] + abc[i][k])
    print(max(dp[-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a, b, c = [], [], []
for _ in range(n):
    ai, bi, ci = map(int, input().strip().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
dp = []
dp.append((a[0], b[0], c[0]))
for i in range(1, n):
    prev = dp[i-1]
    chosen_a = a[i] + max(prev[1], prev[2])
    chosen_b = b[i] + max(prev[0], prev[2])
    chosen_c = c[i] + max(prev[0], prev[1])
    dp.append((chosen_a, chosen_b, chosen_c))
res = dp[n-1]
print(max(res[0], res[1], res[2]))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x=[]
    for i in range(n):
        x.append(list((map(int,input().split()))))
    
    for i in range(1,n):
        for j in range(3):
            x[i][j]+=max(x[i-1][(j+1)%3],x[i-1][(j+2)%3]);
    
    print(max(x[n-1]))
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

# max happiness after i days doing (a, b, c) on that day is in dp[i][0/1/2]
dp = [[0]*3 for _ in range(n+1)]

dp[1][0] = happy_mat[0][0]
dp[1][1] = happy_mat[0][1]
dp[1][2] = happy_mat[0][2]

for day in range(2, n+1):
    for activity in range(3):
        dp[day][activity] = max(dp[day-1][(activity+1)%3], dp[day-1][(activity+2)%3]) + happy_mat[day-1][activity]

print(max(dp[n]))

Submission status: Accepted

Solution code:
N, = list(map(int, input().split()))

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

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
a = np.array([input().split() for i in range(N)], dtype=int)

dp = np.zeros((N, 3), dtype=int)
dp[0] = a[0]

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

print(np.max(dp[-1]))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
# a = np.array([int(i) for i in input().split()])
a = np.array([input().split() for i in range(N)], dtype=int)

dp = np.zeros((N, 3), dtype=int)
dp[0] = a[0]

for i in range(1, N):
    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] + a[i][k])

print(np.max(dp[-1]))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    happy = []
    for i in range(n):
        happy.append(list(map(int, input().split())))
    
    dp = [[0 for i in range(3)] for j in range(100010)]

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

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

if __name__ == "__main__":
    main()