Problem:


Score : 100 points

Problem Statement

Taro's summer vacation starts tomorrow, and he has decided to make plans for it now.

The vacation consists of N days.
For each i (1 \leq i \leq N), Taro will choose one of the following activities and do it on the i-th day:

A: Swim in the sea. Gain a_i points of happiness.

B: Catch bugs in the mountains. Gain b_i points of happiness.

C: Do homework at home. Gain c_i points of happiness.

As Taro gets bored easily, he cannot do the same activities for two or more consecutive days.

Find the maximum possible total points of happiness that Taro gains.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq a_i, b_i, c_i \leq 10^4

Input

Input is given from Standard Input in the following format:

N
a_1 b_1 c_1
a_2 b_2 c_2
:
a_N b_N c_N

Output

Print the maximum possible total points of happiness that Taro gains.

Sample Input 1

3
10 40 70
20 50 80
30 60 90

Sample Output 1

210

If Taro does activities in the order C, B, C, he will gain 70 + 50 + 90 = 210 points of happiness.

Sample Input 2

1
100 10 1

Sample Output 2

100

Sample Input 3

7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1

Sample Output 3

46

Taro should do activities in the order C, A, B, A, C, B, A.



Sample input:
3
10 40 70
20 50 80
30 60 90


Sample output:
210

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    abc = [list(map(int, input().split())) for _ in range(n)]
    a, b, c = zip(*abc)
    srs_a = {-1: 0}
    srs_b = {-1: 0}
    srs_c = {-1: 0}
    def dp_a(i):
        return max(srs_b[i-1], srs_c[i-1]) + a[i]
    def dp_b(i):
        return max(srs_c[i-1], srs_a[i-1]) + b[i]
    def dp_c(i):
        return max(srs_a[i-1], srs_b[i-1]) + c[i]
    for i in range(n):
        srs_a[i] = dp_a(i)
        srs_b[i] = dp_b(i)
        srs_c[i] = dp_c(i)
    print(max(srs_a[n-1], srs_b[n-1], srs_c[n-1]))


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# import math
# import bisect
# import heapq
# from collections import deque

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


for i in range(n):
    if i == 0:
        t1 = score[i][0]
        t2 = score[i][1]
        t3 = score[i][2]
    else:
        x1 = t1
        x2 = t2
        x3 = t3

        t1 = max(x2,x3) + score[i][0]
        t2 = max(x1,x3) + score[i][1]
        t3 = max(x1,x2) + score[i][2]

print(max(t1,t2,t3))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
a=int(input())
ans=[]
total=0
for i in range(a):
    z=list(map(int,input().split()))
    ans.append(z)
for i in range(a):
    if(i==0):
        t1=ans[0][0]
        t2=ans[0][1]
        t3=ans[0][2]
        
    else:
        x1=t1
        x2=t2
        x3=t3
        t1=max(x2,x3)+ans[i][0]
        t2=max(x1,x3)+ans[i][1]
        t3=max(x1,x2)+ans[i][2]
        
    
print(max(t1,t2,t3))

Submission status: Accepted

Solution code:
N = int(input())
DP = [[0]*3 for i 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][0]+c,DP[i-1][1]+c)
print(max(DP[-1]))

Submission status: Accepted

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

#print(N,A)

dp = [[0] * 3 for _ in range(N)]
dp[0][0] = A[0][0]
dp[0][1] = A[0][1]
dp[0][2] = A[0][2]
#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]+A[i][j])

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

Submission status: Accepted

Solution code:
"""
@author:  wangquaxiu
@time:  2020/3/7 19:47
"""

import numpy as np
n = int(input())
dp = np.zeros((n,3),dtype=np.int)
happy = []
for i in range(n):
    d = list(map(int,input().split()))
    happy.append(d)

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

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


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

Submission status: Accepted

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

dp_a = [0]*N
dp_b = [0]*N
dp_c = [0]*N
dp_a[0] = l[0][0]
dp_b[0] = l[0][1]
dp_c[0] = l[0][2]

for i in range(1,N):
    dp_a[i] = max(dp_b[i-1],dp_c[i-1])+l[i][0]
    dp_b[i] = max(dp_a[i-1],dp_c[i-1])+l[i][1]
    dp_c[i] = max(dp_b[i-1],dp_a[i-1])+l[i][2]

print(max(dp_a[-1],dp_b[-1],dp_c[-1]))

Submission status: Accepted

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

res = h[0]
for i in range(1, n):
    tmp = res[:]
    for j in range(3):
        res[j] = h[i][j] + max(tmp[(j + 1) % 3], tmp[j - 1])
print(max(res))

Submission status: Accepted

Solution code:
dp=[[0]*3 for _ in range(10**5+1)]
n=int(input())
abc=[[int(i) for i in input().split()] for _ in range(n)]

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

Submission status: Accepted

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

dp = nums[0]

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

print(max(dp))

Submission status: Accepted

Solution code:
def max_ex(target, iex):
  ret = 0
  i_ret = 0
  for v,i in enumerate(range(len(target))):
    if i == iex:
      continue
    if v > ret:
      ret = v
      i_ret = i
  
  return [ret,i_ret]

n = int(input())
abc = []
dp = []
for i in range(n):
  abc.append(list(map(int, input().split())))
  
  if i == 0:
    dp.append(abc[0])
  else:
    dpa = abc[i][0] + max(dp[i-1][1],dp[i-1][2])
    dpb = abc[i][1] + max(dp[i-1][0],dp[i-1][2])
    dpc = abc[i][2] + max(dp[i-1][0],dp[i-1][1])
    dp.append([dpa,dpb,dpc])
    
print('{}'.format(max(dp[n-1])))

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

dp = [[0] * 3 for 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 - 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[n-1]))

Submission status: Accepted

Solution code:
N = int(input())

x, y, z = list(map(int, input().split()))
for _ in range(N-1):
  a, b, c = list(map(int, input().split()))
  x, y, z = a + max(y, z), b + max(x, z), c + max(x, y)

print(max(x,y,z))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

for i in range(N):
    a[i],b[i],c[i] = map(int,input().split())
    
#3パターンがN日
dp = [[0]*3 for i in range(N)]
#初期値は以下
dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]

#二日目以降の操作(i日目に?操作した場合のdp)
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[-1]))

Submission status: Accepted

Solution code:
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    n=int(input())

    [A,B,C]=[[0]*n for _ in range(3)]
    for i in range(n):
        A[i],B[i],C[i]=map(int,input().split())

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

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

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

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



resolve()

Submission status: Accepted

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

for i in range(n):
    inp.append(list(map(lambda x: int(x), input().split(" "))))

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

for i in range(n):
    for j in range(3):
        if (i<n-1):
            m1 = dp[i][j] + inp[i+1][(j+1)%3]
            m2 = dp[i][j] + inp[i+1][(j+2)%3]
            if (dp[i+1][(j+1)%3] < m1):
                dp[i+1][(j+1)%3] = m1
            if (dp[i+1][(j+2)%3] < m2):
                dp[i+1][(j+2)%3] = m2

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

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

Submission status: Accepted

Solution code:

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

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


if __name__ == '__main__':
    main()

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:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N = int(input())
    l = [list(map(int, input().split())) for _ in range(N)]
    dp = [[0]*3 for _ in range(N+1)]
    dp[1] = l[0]
    
    for i in range(1, N):
        for j in range(3):
            a = (j+1)%3
            b = (j+2)%3
            dp[i+1][j] = max(dp[i][a], dp[i][b]) + l[i][j]
    print(max(dp[N]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N = int(input())
    l = [list(map(int, input().split())) for _ in range(N)]
    dp = [[0]*3 for _ in range(N+1)]
    dp[1][0] = l[0][0]
    dp[1][1] = l[0][1]
    dp[1][2] = l[0][2]
    
    for i in range(1, N):
        for j in range(3):
            a = (j+1)%3
            b = (j+2)%3
            dp[i+1][j] = max(dp[i][a], dp[i][b]) + l[i][j]
    print(max(dp[N]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(1,N):
    for j in range(3):
        sc = 0
        for k in range(3):
            if j == k:
                t = dp[i-1][k]
            else:
                t = dp[i-1][k] + abc[i][j]
            if sc < t:
                sc = t
        dp[i][j] = sc
print(max(dp[N-1]))

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


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

# i日目にjを選択した後の幸福度 dp[i][j]
dp = [[0 for j in range(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())
ABC = [list(map(int, input().split())) for i in range(n)]

# i日目にjを選択した後の幸福度 dp[i][j]
dp = [[0 for j in range(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())
list1 = [list(map(int,input().split(" "))) for i in range(n)]
dp = [[0,0,0] for _ in range(n)]
dp[0] = list1[0]
for i in range(1,n):
    dp[i][0] = list1[i][0] + max(dp[i-1][1],dp[i-1][2])
    dp[i][1] = list1[i][1] + max(dp[i-1][2],dp[i-1][0])
    dp[i][2] = list1[i][2] + max(dp[i-1][0],dp[i-1][1])
print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

happiness = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0]*3 for _ in range(n)]

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

Submission status: Accepted

Solution code:
n = int(input())

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


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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# def LIST(): return list(map(str, input().split()))
# def LIST(): return list(input())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
L = [LIST() for i in range(N)]

dp = [[0] * 3 for i in range(N)]
# dp_b = [0] * N
# dp_c = [0] * 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):
    # dp_a[i+1] = max(dp_a[i]+, )
    # for abc in range(3):
    dp[i][0] = max(dp[i-1][1]+L[i][0], dp[i-1][2]+L[i][0])
    dp[i][1] = max(dp[i-1][2]+L[i][1], dp[i-1][0]+L[i][1])
    dp[i][2] = max(dp[i-1][0]+L[i][2], dp[i-1][1]+L[i][2])

ans = 0
for i in range(3):
    if ans < dp[N-1][i]:
        ans = dp[N-1][i]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
abc = [list(map(int,input().split())) for i in range(n)]
f_min = 0 
dp = [[f_min] * 3 for _ in range(n)]
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
def chmax(a,b):
    if a < b:
        return b
    else:
        return a
def main():
    dp[0][0], dp[0][1], dp[0][2] = abc[0][0], abc[0][1], abc[0][2]
    for i in range(1,n):
            a,b,c = abc[i][0], abc[i][1], abc[i][2]
            dp[i][0] = chmax(dp[i][0], chmax(dp[i-1][1] + a, dp[i-1][2] +a))
            dp[i][1] = chmax(dp[i][1], chmax(dp[i-1][0] + b, dp[i-1][2] +b))
            dp[i][2] = chmax(dp[i][2], chmax(dp[i-1][0] + c, dp[i-1][1] +c))
    print(chmax(dp[n-1][0], chmax(dp[n-1][1],dp[n-1][2])))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Fri Mar  6 13:28:27 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

N = ni()
abc = nan(N)
dp = [[0] * 3 for _ in range(N + 1)]
for i in range(N):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][k] + abc[i][j])

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

Submission status: Accepted

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

dp = [[0] * 3 for _ in range(100010)]
for i in range(1, n + 1):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            if dp[i][k] < dp[i - 1][j] + a[i - 1][k]:
                dp[i][k] = dp[i - 1][j] + a[i - 1][k]
print(max(dp[n]))

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):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            if dp[i][k] < dp[i - 1][j] + a[i - 1][k]:
                dp[i][k] = dp[i - 1][j] + a[i - 1][k]
print(max(dp[n]))

Submission status: Accepted

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

Submission status: Accepted

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

print(solve())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

N = int(input())

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

dp[0][0], dp[0][1], dp[0][2] = map(int, sys.stdin.readline().split())

tmp = [0, 0, 0]

for i in range(1, N):
    tmp[0], tmp[1], tmp[2] = map(int, sys.stdin.readline().split())
    for j in range(3):
        dp[i][j] = max(dp[i-1][(j+1)%3]+tmp[j], dp[i-1][(j+2)%3]+tmp[j])

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

Submission status: Accepted

Solution code:
N = int(input())

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

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

print(max(dp[N]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys


def input():
    return sys.stdin.readline().strip()


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

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

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

res = 0

for v in range(3):
    res = max(res, dp[N][v])

print(res)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

dp = [[0 for i in range(3)] for j in range(vacation+1)]
def chmax(a, b):
    if a > b:
        return a
    else:
        return b

for i in range(vacation):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + lst_happiness[i][k])
ans = 0
for i in range(3):
    ans = chmax(ans, dp[vacation][i])
print(ans)

Submission status: Accepted

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

x, y, z = 0, 0, 0
for a, b, c in h:
    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())
abc = [list(map(int, input().split())) for _ in range(n)]

a, b, c = 0, 0, 0
for x, y, z in abc:
    a, b, c = max(b, c) + x, max(a, c) + y, max(a, b) + z

print(max(a, b, c))

Submission status: Accepted

Solution code:
dpa = [-float('inf') for _ in range(100010)]
dpb = [-float('inf') for _ in range(100010)]
dpc = [-float('inf') for _ in range(100010)]


N = int(input())
a = []
b = []
c = []

for i in range(N):
    a1,b1,c1 = map(int,input().split())
    a.append(a1)
    b.append(b1)
    c.append(c1)

#もらうDP
dpa[0] = a[0]
dpb[0] = b[0]
dpc[0] = c[0]

#i日にAを実施。i-1日目にBもしくはC。
for i in range(1,N):
    dpa[i] = max(dpb[i-1]+a[i],dpc[i-1]+a[i])
    dpb[i] = max(dpa[i-1]+b[i],dpc[i-1]+b[i])
    dpc[i] = max(dpa[i-1]+c[i],dpb[i-1]+c[i])

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

Submission status: Accepted

Solution code:
def main():
    N=int(input())
    abc=[0]*N
    for i in range(N):
        xyz=list(map(int,input().split()))
        abc[i]=xyz
    dp=[[0]*3 for _ in range(N+1)]
    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-1)%3],dp[i-1][(j-2)%3]+abc[i-1][(j-1)%3])

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

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
arr = []
for i in range(n):
	arr.append(list(map(int,input().split())))
ans = [arr[0][::]]
for i in range(1,n):
	temp = ans[-1]
	x = max(temp[1]+arr[i][0],temp[2]+arr[i][0])
	y = max(temp[0]+arr[i][1],temp[2]+arr[i][1])
	z = max(temp[0]+arr[i][2],temp[1]+arr[i][2])
	ans.append([x,y,z])
print(max(ans[-1]))

Submission status: Accepted

Solution code:
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
import sys

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n = int(input())
    h = [[0] * 3 for _ in range(n)]

    for i in range(n):
        h[i] = list(map(int,ipti().split()))

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
from operator import itemgetter #sortedの対象を決めたい
from fractions import gcd #最大公約数
from math import ceil, floor, sqrt, isinf #小数点切り上げ、切り捨て、平方根
from copy import deepcopy #参照で影響されないコピー
from collections import Counter, deque #要素ごとの出現回数、双方向アクセス可能データ型
import heapq
import numpy as np
from functools import reduce
sys.setrecursionlimit(200000)

input = sys.stdin.readline
# template

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

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

    dp = np.zeros([3, n+1])

    for i, a_l in enumerate(a):
        for j in range(3):
            for k in range(3):
                if j != k:
                    dp[k, i+1] = max(dp[k, i+1], dp[j, i] + a_l[k])

    print(int(np.max(dp[:, n], axis=0)))


if __name__ == "__main__":
    main()