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
input = sys.stdin.readline

N = int(input())
Act = [[0,0,0]] + [list(map(int,input().split())) for _ in range(N)]
dp = [[None for _ in range(3)] for _ in range(N+1)]
dp[1][0] = Act[1][0]
dp[1][1] = Act[1][1]
dp[1][2] = Act[1][2]

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

Submission status: Accepted

Solution code:
def resolve():
	n = int(input())
	c = []
	for _ in range(n):
		c.append(list(map(int, input().split())))
	dp = [[0, 0, 0] for _ in range(n)]
	dp[0] = c[0]
	for i in range(n-1):
		for j in range(3):
			for k in range(3):
				if j == k:
					continue
				else:
					dp[i+1][j] = max(dp[i+1][j], dp[i][k] + c[i+1][j])
	print(max(dp[-1]))
resolve()

Submission status: Accepted

Solution code:
def resolve():
	n = int(input())
	c = []
	for _ in range(n):
		c.append(list(map(int, input().split())))
	dp = [[0, 0, 0] for _ in range(n)]
	dp[0] = c[0]
	for i in range(1, n):
		for j in range(3):
			for k in range(3):
				if j == k:
					continue
				else:
					dp[i][j] = max(dp[i][j], dp[i-1][k] + c[i][j])
	print(max(dp[-1]))
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys


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


def main():
    size = int(input())
    dp = [0] * 3
    for _ in range(size):
        z = (list(map(int, input().split())))
        newDp = [0] * 3
        for i in range(3):
            for j in range(3):
                if j != i:
                    # import pdb
                    # pdb.set_trace()
                    newDp[j] = max(newDp[j], dp[i] + z[j])
        dp = newDp
    print(max(dp[0],dp[1],dp[2]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()
abc = [iln() for _ 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][j] = max(dp[i+1][j], dp[i][k]+abc[i][j])

print(max(dp[N]))

Submission status: Accepted

Solution code:
"""
参考 Xenous
if sortを少なくし、maxで処理
""" 
# 初期入力
N = int(input())
a=[]
b=[]
c=[]
for i in range(N):
    a1,b1,c1 = (int(x) for x in input().split())
    
    a.append(a1)
    b.append(b1)
    c.append(c1)

dp_A = [0]*(N) ;dp_A[0] =a[0] 
dp_B = [0]*(N) ;dp_B[0] =b[0] 
dp_C = [0]*(N) ;dp_C[0] =c[0] 


#
for i in range(0,N-1):
    dp_A[i+1] = max(dp_B[i] + a[i+1] , dp_C[i] + a[i+1])
    dp_B[i+1] = max(dp_A[i] + b[i+1] , dp_C[i] + b[i+1])
    dp_C[i+1] = max(dp_A[i] + c[i+1] , dp_B[i] + c[i+1])
print(max (dp_A[N-1],dp_B[N-1],dp_C[N-1]) )

Submission status: Accepted

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

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

print(max(happy[-1]))

Submission status: Accepted

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

def main():
    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(3):
        dp[0][i] = 0
    for i in range(1, N+1):
        for today in range(3):
            for yesterday in range(3):
                if today == yesterday:
                    continue
                dp[i][today] = max(dp[i][today], dp[i-1][yesterday] + abc[i-1][today])
    ans = 0
    for i in range(3):
        ans = max(ans, dp[N][i])
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
x, y, z = 0, 0, 0
n = int(input())
for _ in range(n):
    a, b, c = 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:
def main():
    n = int(input())
    a, b, c = [0] * n, [0] * n, [0] * n
    for i in range(n):
        x, y, z = map(int, input().split())
        a[i] = x
        b[i] = y
        c[i] = z
    dp = [[0 for _ in range(3)] for _ 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]
    return max(dp[n - 1])
print(main())

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

def main():
    N = int(input())
    DPa = [0] * N; DPb = [0] * N; DPc = [0] * N
    for i in range(N):
        a, b, c = map(int, readline().split())
        if i == 0:
            DPa[i] = a; DPb[i] = b; DPc[i] = c
        else:
            DPa[i] = max(DPb[i-1], DPc[i-1]) + a
            DPb[i] = max(DPa[i-1], DPc[i-1]) + b
            DPc[i] = max(DPa[i-1], DPb[i-1]) + c

    ans = max(DPa[N-1], DPb[N-1], DPc[N-1])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
action=[list(map(int,input().split())) for i in range(n)]
#print(action)
DP=[[0 for j in range(3)] for k in range(n+1)]
DP[1][0]=action[0][0]
DP[1][1]=action[0][1]
DP[1][2]=action[0][2]
for l in range(1,n+1):
  DP[l][0]=DP[l-1][1]+action[l-1][0]
  DP[l][1]=DP[l-1][0]+action[l-1][1]
  DP[l][2]=DP[l-1][0]+action[l-1][2]
  if DP[l][0]<DP[l-1][2]+action[l-1][0]:
    DP[l][0]=DP[l-1][2]+action[l-1][0]
  if DP[l][1]<DP[l-1][2]+action[l-1][1]:
    DP[l][1]=DP[l-1][2]+action[l-1][1]
  if DP[l][2]<DP[l-1][1]+action[l-1][2]:
    DP[l][2]=DP[l-1][1]+action[l-1][2]
print(max(max(DP)))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N = int(input())
    dp = [0] * 3

    for day in range(N):
        cur_activities = [int(x) for x in input().split()]

        new_dp = [0] * 3

        for i in range(3):
            for j in range(3):
                if i != j:
                    new_dp[j] = max(new_dp[j], dp[i] + cur_activities[j])

        dp = new_dp

    print(max(dp))

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    dp = [[0] * 3 for _ 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[-1]))


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    n = int(input())
    ary = [list(map(int, stdin.readline().split())) for _ in range(n)]
    dp = [[0 for _ in range(3)] for _ in range(n)]
    for k in range(n):
        for i in range(3):
            if k == 0:
                dp[k][i] = ary[k][i]
            else:
                dp[k][i] = ary[k][i] + max([dp[k-1][j] for j in range(3) if j != i])
    print(max(dp[n-1]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
dp=[]
for j in range(N+1):
    dp.append([0,0,0])

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

# print(dp,sep="\n")
print(max(dp[N][0],dp[N][1],dp[N][2]))

Submission status: Accepted

Solution code:
import sys

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

def main():
    N = int(input())
    L = [list(map(int,input().split())) for _ in range(N)]
    dp = [[0 for _ in range(3)] for _ in range(N+1)]

    for num,i in enumerate(L[0]):
        dp[0][num] = i

    for i in range(1,N):
        for dp_num,k in enumerate(dp[i-1]):
            for l_num,j in enumerate(L[i]):
                if l_num == dp_num:
                    continue
                dp[i][l_num] = max(k + j,dp[i][l_num])
    print(max(dp[N-1]))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * n
b = [0] * n
c = [0] * n
for i in range(n):
    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],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 sys

input = sys.stdin.readline

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

    dpa = [0] * N
    dpb = [0] * N
    dpc = [0] * N

    dpa[0] = A[0]
    dpb[0] = B[0]
    dpc[0] = C[0]

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
if __name__=='__main__':
	N=int(input())
	happiness=[]
	for i in range(N):
		cost=list(map(int,input().split()))
		happiness.append(cost)
	dp=[[0 for j in range(3)] for i in range(N+1)]
#j:0 is from A, 1 is from B, 2 is from C
	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]+happiness[i][k])
				else:
					continue
			
	print(max(dp[-1]))

Submission status: Accepted

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

n = int(input())
abc = [[int(x) for x in 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):
    a, b, c = abc[i]
    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())
P = [list(map(int,input().split())) for i in range(N)]

a=[P[0][0]]*N
b=[P[0][1]]*N
c=[P[0][2]]*N

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

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

Submission status: Accepted

Solution code:
N = int(input())

dp = [[0] * 3 for _ 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][0], dp[i - 1][1]) + c
print(max(dp[N - 1][0], dp[N - 1][1], dp[N - 1][2]))

Submission status: Accepted

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

print(max(dp[n]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

N = int(input())
a = []
dp = [0]*(N+1)
for i in range(N+1):
    dp[i] = [0]*3
#print('dp', dp)
for _ in range(N):
    a.append(tuple(map(int, input().split())))
#print('a', a)
dp[0][0] = 0

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

Submission status: Accepted

Solution code:
n=int(input())
A,B,C=map(int,input().split())
for x in range(n-1):
    a,b,c=map(int,input().split())
    a+=[B,C][B<C]
    b+=[A, C][A < C]
    c+=[B, A][B < A]
    A,B,C=a,b,c
print(max([A,B,C]))

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    ABC = [list(map(int, input().split())) for _ in [0] * N]

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


main()

Submission status: Accepted

Solution code:
N = int(input())

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

arr = [list(map(int, input().split())) for _ 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,1):
    dp[i][0] = max(arr[i][0]+dp[i-1][1],arr[i][0]+dp[i-1][2])
    dp[i][1] = max(arr[i][1]+dp[i-1][0],arr[i][1]+dp[i-1][2])
    dp[i][2] = max(arr[i][2]+dp[i-1][0],arr[i][2]+dp[i-1][1])

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

Submission status: Accepted

Solution code:
def main():
    n, *abc = map(int, open(0).read().split())
    x, y, z = 0, 0, 0
    for (a, b, c) in zip(*[iter(abc)] * 3):
        x, y, z = a + max(y, z), b + max(z, x), c + max(x, y)

    ans = max([x, y, z])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

dp_a = [0]*(N+1)#[i]にi日目の幸福度
dp_b = [0]*(N+1)
dp_c = [0]*(N+1)

for i in range(N):
    a, b, c = map(int,input().split())#i+1日目の幸福度
    dp_a[i+1] = max(dp_b[i],dp_c[i]) + a
    dp_b[i+1] = max(dp_c[i],dp_a[i]) + b
    dp_c[i+1] = max(dp_a[i],dp_b[i]) + c

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

Submission status: Accepted

Solution code:
def main():
    n, *abc = map(int, open(0).read().split())
    x, y, z = 0, 0, 0
    for i, (a, b, c) in enumerate(zip(*[iter(abc)] * 3), 1):
        x, y, z = a + max(y, z), b + max(z, x), c + max(x, y)
    
    ans = max([x, y, z])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

    print(max(dp[-1]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
x = int(input())
li = []
for i in range(x):
    l = list(map(int, input().split()))
    li.append(l)
dp = [[0]*3 for _ in range(x+1)]
for i in range(x):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i+1][j] = max(dp[i][k]+li[i][j], dp[i+1][j])
print(max(max(dp[x][0], dp[x][1]), max(dp[x][1], dp[x][2])))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
inf = 10**9+7

n = int(input())
dp_a = [0 for i in range(n+1)]
dp_b = [0 for i in range(n+1)]
dp_c = [0 for i in range(n+1)]

for i in range(n):
    a,b,c = map(int, input().split())
    dp_a[i+1] = max(dp_b[i]+a, dp_c[i]+a)
    dp_b[i + 1] = max(dp_a[i] + b, dp_c[i] + b)
    dp_c[i + 1] = max(dp_a[i] + c, dp_b[i] + c)
print(max(dp_a[n], dp_b[n], dp_c[n]))

Submission status: Accepted

Solution code:
N = int(input())
A, B, C = map(int, input().split())
dp = [[0] * 3 for _ in range(N)]
dp[0] = [A, B, C]

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

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

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]=list(map(int,input().split(" ")))

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

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

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())

A, B, C = 0, 0, 0 #最後に各活動を行った幸福度の和
for _ in range(N):
    a, b, c = map(int, input().split())
    A, B, C = max(B, C) + a, max(C, A) + b, max(A, B) + c
ans = max(A, B, C)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#dp[i+1][x]:i日目にxを選んだ時の総和の最大値

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

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

Submission status: Accepted

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

dp = [[-float('inf')]*3 for _ in range(N+1)]
for j in range(3):
  dp[0][j] = 0

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]+A[i][k])

print(max(dp[N]))

Submission status: Accepted

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


dp = [[0, 0, 0] for _ in range(n+1)]
for i in range(n):
    for place_y in range(3):
        for place in range(3):
            if place_y != place:
                dp[i+1][place] = max(
                    dp[i+1][place], dp[i][place_y]+abc[i][place]
                )

print(max(dp[n]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(values, _nb):
    ca, cb, cc = 0, 0, 0
    for a, b, c in values:
        ca, cb, cc = max(cb + b, cc + c), max(ca + a, cc + c), max(ca + a, cb + b)
    return max(ca, cb, cc)


def do_job():
    "Do the work"
    # first line is number of test cases
    N = int(input().strip())
    values = []
    for _ in range(N):
        values.append(map(int, input().split()))
    result = solve(values, N)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(values, _nb):
    ca, cb, cc = 0, 0, 0
    for a, b, c in values:
        new_ca = max(cb + b, cc + c)
        new_cb = max(ca + a, cc + c)
        new_cc = max(ca + a, cb + b)
        ca, cb, cc = new_ca, new_cb, new_cc
    return max(ca, cb, cc)


def do_job():
    "Do the work"
    # first line is number of test cases
    N = int(input().strip())
    values = []
    for _ in range(N):
        values.append(map(int, input().split()))
    result = solve(values, N)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())

Submission status: Accepted

Solution code:
def chmax_a(l,B,C,i):
	return max(B+l[i][1],C+l[i][2])

def chmax_b(l,A,C,i):
	return max(A+l[i][0],C+l[i][2])

def chmax_c(l,A,B,i):
	return max(B+l[i][1],A+l[i][0])

if __name__=='__main__':
	N=int(input())
	happiness=[]
	for i in range(N):
		cost=list(map(int,input().split()))
		happiness.append(cost)
	answers=[]
	A=0
	B=0
	C=0
	for i in range(N-1,-1,-1):
		a=chmax_a(happiness,B,C,i)
		b=chmax_b(happiness,A,C,i)
		c=chmax_c(happiness,A,B,i)
		A=a
		B=b
		C=c
	print(max(A,B,C))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def main():
    N = int(readline())
    abc = map(int, read().split())
    x, y, z = 0, 0, 0
    for a, b, c in zip(abc, abc, abc):
        x, y, z = max(y, z) + a, max(x, z) + b, max(x, y) + c

    print(max(x, y, z))


if __name__ == '__main__':
    main()