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:
def getval():
    n = int(input())
    h = [list(map(int,input().split())) for i in range(n)]
    return n,h

def main(n,h):
    dp = [[h[0][0],h[0][1],h[0][2]]]
    for i in range(1,n):
        cur = h[i]
        prev = dp[-1]
        temp = []
        temp.append(max(prev[1],prev[2])+cur[0])
        temp.append(max(prev[0],prev[2])+cur[1])
        temp.append(max(prev[0],prev[1])+cur[2])
        dp.append(temp)
    print(max(dp[-1]))
    
if __name__=="__main__":
    n,h = getval()
    main(n,h)

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(n-1):
    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]+l[i+1][k])
print(max(dp[n-1]))

Submission status: Accepted

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

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

    print(max(dp[-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

    print(max(dp[-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

    print(max(dp))

main()

Submission status: Accepted

Solution code:
def i_input(): return int(input())


def i_map(): return map(int, input().split())


def i_list(): return list(i_map())


def i_row_list(N): return [i_list() for _ in range(N)]


n = i_input()
abc = i_row_list(n)
dp=[]
for i in range(n):
    dp.append([0]*3)
dp[0] = abc[0]
for i in range(n):
    if i!=0:
        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])

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

Submission status: Accepted

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

Submission status: Accepted

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

dp = [[0]*3 for _ in range(n+1)]
#dp[i][a] := i日目にaするときの、i日目までの幸福度の最大値
for i in range(1, n+1):
    dp[i][0] = max(dp[i-1][1] + abc[i-1][0],
                   dp[i-1][2] + abc[i-1][0])
    dp[i][1] = max(dp[i-1][0] + abc[i-1][1],
                   dp[i-1][2] + abc[i-1][1])
    dp[i][2] = max(dp[i-1][0] + abc[i-1][2],
                   dp[i-1][1] + abc[i-1][2])
print(max(dp[n]))

Submission status: Accepted

Solution code:
n=int(input())
#a=[0,a1,a2,a3,...,an]
a=[0]
b=[0]
c=[0]
#０日め　0,0,0
#1日目　a1,b1,c1
#2日目　a2=b1+a2 or c1+a2
dp=[[0 for i in range(3)] for j in range(n+1)]
for i in range(n):
    x,y,z=map(int,input().split())
    a.append(x)
    b.append(y)
    c.append(z)
for i in range(1,n+1):
    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]))

Submission status: Accepted

Solution code:
def li():
    return [int(x) for x in input().split()]


N = int(input())
L = []
for i in range(N):
    L.append(li())

# 1.全探索は間に合うか: 再帰で全探索するとO(3**N)で間に合わない
# 2.貪欲法は使えるか: 一手での最善(部分最適)は次の一手の大きなメリットを逃す可能性があルため最善ではない
# 3.DPは使えるか: 一手ごとにA,B,Cの状態別に最大値1つだけに注目すれば良く、残りは切り捨てて良いので使える

# dp[i][k]: i番目の選択でk(a,b,c)を選択した時の最大値
dp = [[0]*3 for i in range(N+1)]
dp[0] = L[0]
for i in range(1, N):
    for k in range(3):
        if k == 0:
            dp[i][k] = max(dp[i][k], dp[i-1][1] + L[i][0], dp[i-1][2] + L[i][0])
        elif k == 1:
            dp[i][k] = max(dp[i][k], dp[i-1][0] + L[i][1], dp[i-1][2] + L[i][1])
        elif k == 2:
            dp[i][k] = max(dp[i][k], dp[i-1][0] + L[i][2], dp[i-1][1] + L[i][2])

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

Submission status: Accepted

Solution code:
N = int(input())

a_list = []
b_list = []
c_list = []
for i in range(N):
    a, b, c = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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] + event[i][j])
print(max(dp[N - 1]))

Submission status: Accepted

Solution code:
''' ===============================
    -- @uthor : Kaleab Asfaw
    -- Handle : kaleabasfaw2010
    -- Bio    : High-School Student
    ==============================='''

# Fast IO
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file): self._fd = file.fileno(); self.buffer = BytesIO(); self.writable = "x" in file.mode or "r" not in file.mode; self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b: break
            ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0; return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)); self.newlines = b.count(b"\n") + (not b); ptr = self.buffer.tell(); self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1; return self.buffer.readline()
    def flush(self):
        if self.writable: os.write(self._fd, self.buffer.getvalue()); self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file): self.buffer = FastIO(file); self.flush = self.buffer.flush; self.writable = self.buffer.writable; self.write = lambda s: self.buffer.write(s.encode("ascii")); self.read = lambda: self.buffer.read().decode("ascii"); self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout); input = lambda: sys.stdin.readline().rstrip("\r\n")
# Others
# from math import floor, ceil, gcd
# from decimal import Decimal as d
mod = 10**9+7
def lcm(x, y): return (x * y) / (gcd(x, y))
def fact(x, mod=mod):
	ans = 1
	for i in range(1, x+1): ans = (ans * i) % mod
	return ans
def arr2D(n, m, default=0):
	lst = []
	for i in range(n): temp = [default] * m; lst.append(temp)
	return lst
def sortDictV(x): return {k: v for k, v in sorted(x.items(), key = lambda item : item[1])}

def rest(i):
	if i == 1: return [0, 2]
	elif i == 2: return [0, 1]
	else: return [1, 2]

def solve(n, lst):
	dp = arr2D(n+1, 3,-1)
	for i in range(1, n+1):
		for j in range(3):
			if dp[i-1][j] == -1:
				dp[i][j] = lst[i-1][j]
			else:
				for k in rest(j):
					dp[i][j] = max(dp[i-1][k] + lst[i-1][j], dp[i-1][k] + lst[i-1][j], dp[i][j])
	return max(dp[n])



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

Submission status: Accepted

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

Submission status: Accepted

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

DP = [[0 for j in range(3)] for i in range(n)]
DP[0][0], DP[0][1], DP[0][2] = A[0], B[0], 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][0], DP[n - 1][1], DP[n - 1][2]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
import decimal
import itertools
from itertools import product
from functools import reduce
def input():
    return sys.stdin.readline()[:-1]
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def sort_zip(a:list, b:list):
    z = zip(a, b)
    z = sorted(z)
    a, b = zip(*z)
    a = list(a)
    b = list(b)
    return a, b
def ceil(x):
    return math.ceil(x)
def floor(x):
    return math.floor(x)

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

    A = [0]
    B = [0]
    C = [0]

    for i in range(N):
        a = max(B[-1], C[-1]) + abc[i][0]
        b = max(C[-1], A[-1]) + abc[i][1]
        c = max(A[-1], B[-1]) + abc[i][2]
        A.append(a)
        B.append(b)
        C.append(c)

    print(max(A[-1], B[-1], C[-1]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

A = [0]
B = [0]
C = [0]
for d in range(n):
    a = h[d][0] + max(B[-1],C[-1])
    b = h[d][1] + max(A[-1],C[-1])
    c = h[d][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:
import sys
sys.setrecursionlimit(2000000001)
n,ar,dp = 0,0,0

def solve(d,pi):
	global n,ar,dp
	if d>=n: return 0
	if dp[d][pi]:
		# print(f'final day=>({dp[d][pi]}),{d},prev = {pi}')
		return dp[d][pi]

	# print('day = ',d,';','prev job = ',pi,';')	##########################################
	# print('j=',[j for j in range(3) if not j is pi])	##############

	m = 0
	for j in range(3):
		if not j is pi:
			tmp = solve(d+1,j)
			# print('tmp=',ar[d][j], '+', tmp,'; d=',d,';pi=',pi)
			m = max(m,ar[d][pi] + tmp)
	# tmp = [ar[d][j] + solve(d+1,j) for j in range(3) if not j is pi]
	dp[d][pi] = m	#max(tmp)

	# print('m=',m)	##############################################
	# for i in range(n):print(dp[i])	##################################
	# print('-----')		##############################################

	return dp[d][pi]

def main():
	global n,ar,dp
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n, = I()
	ar = [[*I()] for _ in range(n)]
	dp = [[0,0,0] for _ in range(n-1)]+[ar[-1]]
	pr(max(solve(0,0),solve(0,1),solve(0,2)))
	# pr('')
	# for i in range(n):print(dp[i])

main()

Submission status: Accepted

Solution code:
n = int(input())

aa = 0
bb = 0
cc = 0 

for i in range(n):
    a,b,c = map(int,input().split())
    aa,bb,cc = max(bb + a, cc + a),max(aa + b, cc + b),max(aa + c, bb + c)

print(max(aa,bb,cc))

Submission status: Accepted

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


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


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

print(max(dp[-1]))

Submission status: Accepted

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

def main():
    n = int(input())
    
    A = [0]*n
    B = [0]*n
    C = [0]*n
    
    a,b,c = map(int,input().split())
    A[0] = a
    B[0] = b
    C[0] = c
    
    for i in range(1,n):
        a,b,c = map(int,input().split())
        A[i] = max(B[i-1]+a, C[i-1]+a)
        B[i] = max(A[i-1]+b, C[i-1]+b)
        C[i] = max(A[i-1]+c, B[i-1]+c)
    
    print(max(A[n-1], B[n-1], C[n-1]))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve(arr,dp,N):
    dp[0][0],dp[0][1],dp[0][2]=matrix[0][0],matrix[0][1],matrix[0][2]
    for i in range(1,N):
        dp[i][0]=arr[i][0]+max(dp[i-1][1],dp[i-1][2])
        dp[i][1]=arr[i][1]+max(dp[i-1][0],dp[i-1][2])
        dp[i][2]=arr[i][2]+max(dp[i-1][0],dp[i-1][1])
    return max(dp[-1])
if __name__ == "__main__":
    N=int(input())
    matrix=[[0 for j in range(3)] for i in range(N)]
    dp=[[0 for j in range(3)] for i in range(N)]
    for i in range(N):
        matrix[i][0],matrix[i][1],matrix[i][2]=map(int,input().split())
    print(solve(matrix,dp,N))

Submission status: Accepted

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

def main(n,h):
    dp = [[h[0][0],h[0][1],h[0][2]]]
    for i in range(1,n):
        cur = h[i]
        prev = dp[-1]
        temp = []
        temp.append(max(prev[1],prev[2])+cur[0])
        temp.append(max(prev[0],prev[2])+cur[1])
        temp.append(max(prev[0],prev[1])+cur[2])
        dp.append(temp)
    print(max(dp[-1]))
    
if __name__=="__main__":
    n,h = getval()
    main(n,h)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def main():
    n = int(input())
    abc_list = []
    for i in range(n):
        abc_list.append(list(map(int, input().split())))
    dp = [[0] * 3 for i in range(n)]
    dp[0][0] = abc_list[0][0]
    dp[0][1] = abc_list[0][1]
    dp[0][2] = abc_list[0][2]
    # print(dp)
    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(dp)
    print(max(dp[-1]))
        
if __name__ == "__main__":
    main()

Submission status: Accepted

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

N = int(readline())
dp = [[0] * 3 for i in range(N + 1)]

for i in range(N):
  works = list(map(int,readline().split()))
  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] + works[k])

print(max(dp[-1]))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

# print(dp)
dp[0] = l[0]

for i in range(1,n):
    for jnow in range(3):
        for jpre in nums:
            if jpre != jnow:
                dp[i][jnow] = max(dp[i][jnow],dp[i-1][jpre]+l[i][jnow])
print(max(dp[n-1]))

Submission status: Accepted

Solution code:
'''
Created on 2020/09/15

@author: harurun
'''
import sys
pin=sys.stdin.readline

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

dp[0][0],dp[0][1],dp[0][2]=map(int,pin().split())
for i in range(1,N):
  a,b,c=map(int,pin().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[N-1]))
#解説AC

Submission status: Accepted

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

DP = [0] * 3

for f in F:
    D = [0] * 3
    S = {0, 1, 2}
    for i in range(3):
        S.remove(i)
        for s in S:
            D[i] = max(D[i], f[i] + DP[s])
        S.add(i)
    DP = D

print(max(DP))

Submission status: Accepted

Solution code:
N = int(input())
Da = [0 for i in range(N+1)]
Db = [0 for i in range(N+1)]
Dc = [0 for i in range(N+1)]
for i in range(1, N+1):
  a, b, c = map(int, input().split())
  Da[i] = max(Db[i-1], Dc[i-1]) + a
  Db[i] = max(Da[i-1], Dc[i-1]) + b
  Dc[i] = max(Da[i-1], Db[i-1]) + c
print(max(Da[N], Db[N], Dc[N]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

grid = []

for i in range(N):
    grid.append([int(x) for x in input().split()])

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

for i in range(1,N):
    for j in range(3):
        dp[i][j] = max(dp[i-1][k]+grid[i][j] for k in {0,1,2}-{j})

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

Submission status: Accepted

Solution code:
n = int(input())

dp = [[0,0,0] 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]+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(dp)
  
ans = max(dp[n])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import enum


def main():
    N = int(input())
    dp = [[] for _ in range(N)]
    for i in range(N):
        abc = list(map(int, input().split()))
        if i == 0:
            dp[0] = abc
        else:
            for k, v in enumerate(abc):
                vals = []
                for j in range(3):
                    if k != j:
                        vals.append(dp[i-1][j])
                dp[i].append(v + max(vals))

    print(max(dp[-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
 
DP = [[0, 0, 0] 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] + 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[N]))

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N = inp()
a = [0] * N
b = [0] * N
c = [0] * N
for i in range(N):
    a[i], b[i], c[i] = inpl()

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

mx = 0
for i in dp[N-1]:
    mx = max(mx, i)

print(mx)

Submission status: Accepted

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

dp = [list([0,0,0]) for i in range(n)]

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

Submission status: Accepted

Solution code:
N = int(input())

DP = [[0, 0, 0] 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] + 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[N]))

Submission status: Accepted

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

print(max(A[N]))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

for i in range(1, n):
    dp.append([
        max(dp[-1][1] + points[i][0], dp[-1][2] + points[i][0]),
        max(dp[-1][0] + points[i][1], dp[-1][2] + points[i][1]),
        max(dp[-1][0] + points[i][2], dp[-1][1] + points[i][2]),
        ])

print(max(dp[-1]))

Submission status: Accepted

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

dp=[[10**10,10**10,10**10] for i in range(n+1)]

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

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

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    n = int(input())
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    d1 = [0]*n
    d2 = [0]*n
    d3 = [0]*n
    for i in range(n):
        x, y, z = map(int, input().split())
        if not i:
            d1[i] = x
            d2[i] = y
            d3[i] = z
            continue

        d1[i] = max(d2[i-1], d3[i-1]) + x
        d2[i] = max(d1[i-1], d3[i-1]) + y
        d3[i] = max(d1[i-1], d2[i-1]) + z

    print(max(d1[-1], d2[-1], d3[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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

for i in range(n):
    a.append(list(map(int,input().split())))

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] + a[i][j])

print(max(dp[n]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    N = int(input())
    happiness = [list(map(int, input().split())) for _ in range(N)]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    import numpy as np

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

    dp = np.zeros((N, 3), dtype=np.int64)
    dp[0] = happiness[0]
    for i in range(1, N):
        for a, yesterday in enumerate(dp[i - 1]):
            for b, today in enumerate(happiness[i]):
                if a == b:
                    continue
                dp[i][b] = max(dp[i][b], yesterday + today)
    print(max(dp[-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin 

def main():

	n = int(input())

	h_vals = []

	for lines in range(n):
		h = list(map(int, input().split()))
		h_vals.append(h)

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


	for cur_day in range(1, n + 1):
		for val in range(3):
			cur_max = 0
			other_vals = [0, 1, 2]
			other_vals.remove(val)
			for other_val in other_vals:
				cur_max = max(L[other_val][cur_day - 1] + h_vals[cur_day - 1][other_val], cur_max)
			L[val][cur_day] = cur_max

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









if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n = int(input())

vac = []
firstDay = list(map(int, input().split()))

for _ in range(n-1):
    newTotal = [0,0,0]
    
    secondDay = list(map(int, input().split()))
    for j, second in enumerate(secondDay):
        temp = 0
        for i, first in enumerate(firstDay):
            if i != j:
                temp = max(temp, first + second)
                
        newTotal[j] = temp   
                    
    firstDay = newTotal
    
print(max(firstDay))

Submission status: Accepted

Solution code:

# def solve(dp,L,i,j):
#     if i==len(dp):
#         return 0

#     else:
#         temp=0
#         for k in range(3):
#             if j!=k:
#                 temp=max(temp,L[i][k]+solve(dp,L,i+1,k))
#         dp[i]=temp
#         return dp[i]

T=int(input())
A=[]
for x in range(T):
    l=[int(i) for i in input().split()]
    A.append(l)
A.append([0,0,0])

for i in range(T-1,-1,-1):
    for j in range(3):
        temp=0
        for k in range(3):
            if j!=k:
                temp=max(temp,A[i][j]+A[i+1][k])

        A[i][j]=max(A[i][j],temp)
    # print(A)
    

print(max(A[0]))