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())
ABC = [list(map(int,input().split())) for _ in range(N)]


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

select_action = [[1,2], [0,2], [0,1]]
for i in range(1,N):
    for j in range(3):
        abc1 = select_action[j][0]
        abc2 = select_action[j][1]

        dp[i][j] = max(dp[i-1][abc1], dp[i-1][abc2]) + ABC[i][j]


print(max(dp[-1]))

Submission status: Accepted

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

dp=[[0 for i in range(3)]for j 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][j] = max(dp[i][j],dp[i-1][k]+h[i-1][j])

print(max(dp[n]))

Submission status: Accepted

Solution code:
N = int(input())
profit = [list(map(int, input().split())) for i in range(N)]
#dp[i][p] をi日目にｐをしたときのi日目までの最大値
#dpを初期化
dp = [[0 for j in range(3)] for i in range(N+1)]
# for p in range(3):
    # dp[0][p] = profit[0][p]

#dpの更新
for i in range(N):
    for p in range(3):
        dp[i][p] = max(dp[i-1][p-1],dp[i-1][p-2]) + profit[i][p]
print(max(dp[-2]))

Submission status: Accepted

Solution code:
N = int(input())
profit = [list(map(int, input().split())) for i in range(N)]
#dp[i][p] をi日目にｐをしたときのi日目までの最大値
#dpを初期化
dp = [[0 for j in range(3)] for i in range(N)]
for p in range(3):
    dp[0][p] = profit[0][p]

#dpの更新
for i in range(1,N):
    for p in range(3):
        dp[i][p] = max(dp[i-1][p-1],dp[i-1][p-2]) + profit[i][p]
print(max(dp[-1]))

Submission status: Accepted

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

dp = [[a[0], b[0], c[0]]]

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

Submission status: Accepted

Solution code:
n = int(input())

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

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

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

Submission status: Accepted

Solution code:
def RA():
    return list(map(int, input().split()))

def solve():
    n = int(input())
    bestEnding = RA()
    for i in range(n - 1):
        a = RA()
        newBestEnding = [
            max(bestEnding[1], bestEnding[2]) + a[0],
            max(bestEnding[0], bestEnding[2]) + a[1],
            max(bestEnding[0], bestEnding[1]) + a[2]
        ]
        bestEnding = newBestEnding
    print(max(bestEnding))


solve()

Submission status: Accepted

Solution code:
import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    ##li=[[-1 for i in range(4)]for j in range(n)]
    a.append(x)
    b.append(y)
    c.append(z)
li=[[-1 for i in range(4)]for j in range(n)]
for i in range(n):
   for j in range(4):
        if i==0:
            if j==0:
                li[i][j]=a[i]
            if j==1:
                li[i][j]=b[i]
            if j==2:
                li[i][j]=c[i]
            if j==3:
                li[i][j] = 0
            continue
        if j==0:
            li[i][j] = max(a[i] + li[i-1][1] ,a[i] + li[i - 1][2])
        if j==1:
            li[i][j] = max(b[i] + li[i - 1][0], b[i] +li[i - 1][2])
        if j==2:
            li[i][j] = max(c[i] + li[i - 1][1], c[i] + li[i - 1][0])
        if j==3:
            li[i][3] = (max(li[i - 1][2],li[i - 1][1], li[i - 1][0]))
print(max(li[n-1]))

Submission status: Accepted

Solution code:
import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    
    a.append(x)
    b.append(y)
    c.append(z)
li=[[-1 for i in range(3)]for j in range(n)]
li[0][0],li[0][1],li[0][2]=a[0],b[0],c[0]
for i in range(1,n):


        li[i][0] = max(a[i] + li[i-1][1] ,a[i] + li[i - 1][2])

        li[i][1] = max(b[i] + li[i - 1][0], b[i] +li[i - 1][2])

        li[i][2] = max(c[i] + li[i - 1][1], c[i] + li[i - 1][0])
print(max(li[n-1]))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    h = {}

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

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


##########
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
  a_=list(map(int,input().split()))
  a.append(a_)
  
dp=[[0]*3 for i in range(n)]
dp[0]=a[0]
for i in range(1,n):
  for k in range(3):
    
    for j in range(3):
      
      if k!=j:
        dp[i][k]=max(dp[i][k], dp[i-1][j] + a[i][k])
#print(dp)        
print(max(dp[n-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)]
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(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[n-1]))

Submission status: Accepted

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

N=int(input())
a=[]
b=[]
c=[]
for i in range(N):
  x,y,z=map(int,input().split())
  a.append(x)
  b.append(y)
  c.append(z)

ha=[0 for _ in range(N)]
hb=[0 for _ in range(N)]
hc=[0 for _ in range(N)]
ha[0]=a[0]
hb[0]=b[0]
hc[0]=c[0]

for i in range(1,N):
  ha[i]=max(hb[i-1]+a[i],hc[i-1]+a[i])
  hb[i]=max(ha[i-1]+b[i],hc[i-1]+b[i])
  hc[i]=max(ha[i-1]+c[i],hb[i-1]+c[i])

print(max((ha[N-1],hb[N-1],hc[N-1])))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    n = int(readline())
    act = []
    for _ in range(n):
        a, b, c = map(int, readline().split())
        act.append((a, b, c))

    #dp[i][j]:= 太郎くんがi日目に活動jを行って得る幸福度の総和の最大値

    dp = [[0, 0, 0] for _ in range(n)]
    for j in range(3):
        dp[0][j] = act[0][j]

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

    print(max(dp[n-1]))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,io
from functools import lru_cache
import numpy
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n=read()
a,b,c=[0]*n,[0]*n,[0]*n
for i,line in enumerate(readlines()):
    a[i],b[i],c[i]=mp(line)
dp=[[0,0,0] for i in range(n+1)]
for k in range(1,n+1):
    one=dp[k-1][1]
    two=dp[k-1][2]
    zero=dp[k-1][0]
    dp[k][0]= one if one >= two else two
    dp[k][0]+=a[k-1]
    dp[k][1]= zero if zero >= two else two
    dp[k][1]+=b[k-1]
    dp[k][2]= one if one >= zero else zero
    dp[k][2]+=c[k-1]
#print(dp)
print(max(dp[n][0],dp[n][1],dp[n][2]))

Submission status: Accepted

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
ABC=n3(n)
ABC

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())
a = [] # 行動をまとめて格納
for _ in range(N):
  x = list(map(int, input().split()))
  a.append(x)
dp = [[0, 0, 0] for _ in range(N)]
dp[0] = a[0]
for i in range(1, N):
  for j in range(3):
    dp[i][j] = max(dp[i-1][(j+1)%3] + a[i][j], dp[i-1][(j+2)%3] + a[i][j])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
n=int(input())
l1=[]
l2=[]
l3=[]
for i in range(n):
	l=input().split()
	u=int(l[0])
	v=int(l[1])
	w=int(l[2])
	l1.append(u)
	l2.append(v)
	l3.append(w)
dpu=[0 for i in range(n)]
dpv=[0 for i in range(n)]
dpw=[0 for i in range(n)]
dpu[0]=l1[0]
dpv[0]=l2[0]
dpw[0]=l3[0]
for i in range(1,n):
	dpu[i]=max(dpv[i-1],dpw[i-1])+l1[i]
	dpv[i]=max(dpu[i-1],dpw[i-1])+l2[i]
	dpw[i]=max(dpu[i-1],dpv[i-1])+l3[i]
print(max(dpu[-1],dpv[-1],dpw[-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
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())
DP_list = [[0] * 3 for _ in range(N)]
#print(dp)
DP_list[0] = [a[0], b[0], c[0]]

base = np.array([a,b,c]).T
for i in range(1,N):
  DP_list[i][0] = base[i][0] + max(DP_list[i-1][1], DP_list[i-1][2])
  DP_list[i][1] = base[i][1] + max(DP_list[i-1][0], DP_list[i-1][2])
  DP_list[i][2] = base[i][2] + max(DP_list[i-1][1], DP_list[i-1][0])

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

Submission status: Accepted

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

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

dp = [[0] * 3 for _ in range(n + 10) ]
for i in range(n):
    dp[i + 1][0] = chmax(dp[i][1] + A[i], dp[i][2] + A[i])
    dp[i + 1][1] = chmax(dp[i][0] + B[i], dp[i][2] + B[i])
    dp[i + 1][2] = chmax(dp[i][0] + C[i], dp[i][1] + C[i])

print(max(dp[n]))

Submission status: Accepted

Solution code:
from sys import stdin,stdout
inp = stdin.readline
out = stdout.write
n = int(inp())
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0] = list(map(int,inp().split()))
for i in range(1,n):
    a,b,c = map(int,inp().split())
    dp[i][0] = max(dp[i-1][1],dp[i-1][2])+a
    dp[i][1] = max(dp[i-1][0],dp[i-1][2])+b
    dp[i][2] = max(dp[i-1][1],dp[i-1][0])+c
out(str(max(dp[n-1])))

Submission status: Accepted

Solution code:
n = int(input())

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

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

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

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]
for i in range(1,N):
  for j in range(3):
    dp[i][j] = abc[i][j] + max(vv for k,vv in enumerate(dp[i-1]) if k != j)

print(max(dp[-1]))

Submission status: Accepted

Solution code:
def main():
    import sys
    n = int(input())
    a, b, c = 0, 0, 0
    for x in sys.stdin.readlines():
        aa, bb, cc = map(int, x.split())
        if a == b == c == 0:
            a, b, c = aa, bb, cc
        else:
            a, b, c = aa+max(b, c), bb+max(a, c), cc+max(a, b)

    print(max(a, b, c))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())

values = [tuple(map(int, input().split(' '))) for _ in range(N)]
dp = [values[0]]
for _ in range(N - 1):
    dp.append([0, 0, 0])

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

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

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())

values = np.array([list(map(int, input().split(' '))) for _ in range(N)])
dp = np.zeros(shape=(N, 3), dtype=int)

dp[0] = values[0]

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

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

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 = map(int,input().split())
    dp[i][0] = max(dp[i-1][1],dp[i-1][2])+a
    dp[i][1] = max(dp[i-1][0],dp[i-1][2])+b
    dp[i][2] = max(dp[i-1][0],dp[i-1][1])+c
print(max(dp[N]))

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    A = [0, 0, 0]
    for _ in range(N):
        B = read_ints()
        A = [
            max(A[j]+B[i] for j in range(3) if i != j)
            for i in range(3)
        ]
    return max(A)


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
li=[]
for i in range(n):
  li.append([int(k) for k in input().split()])
dp=[[0 for i in range(3)] for j in range(n)]
dp[0]=li[0]

for j in range(1,n):
    for i in range(3):
        if(i==0):
            dp[j][i]=li[j][i]+max(dp[j-1][i+1],dp[j-1][i+2])
        elif(i==1):
            dp[j][i]=li[j][i]+max(dp[j-1][i-1],dp[j-1][i+1])
        elif(i==2):
            dp[j][i]=li[j][i]+max(dp[j-1][i-1],dp[j-1][i-2])    
       
#print(dp)
print(max(dp[n-1]))

Submission status: Accepted

Solution code:
"""
task statement
==============

明日から太郎君の夏休みが始まります。
太郎君は夏休みの計画を立てることにしました。
夏休みは N 日からなります。
各 i (1 \leq i \leq N) について、i 日目には太郎君は次の活動のうちひとつを選んで行います。

A: 海で泳ぐ。 幸福度 a_i を得る。
B: 山で虫取りをする。 幸福度 b_i を得る。
C: 家で宿題をする。 幸福度 c_i を得る。

太郎君は飽き性なので、2 日以上連続で同じ活動を行うことはできません。
太郎君が得る幸福度の総和の最大値を求めてください。

io_style
-------
N
a_1 b_1 c_1
a_2 b_2 c_2
:
a_N b_N c_N
"""
#-*-coding:utf-8-*-

import sys

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

if __name__ == "__main__":
    main2()

Submission status: Accepted

Solution code:
N = int(input())
ans = list(map(int, input().split()))
for _ in range(1, N):
    a, b, c = map(int, input().split())
    tmpa, tmpb, tmpc = ans
    ans[0] = a + max(tmpb, tmpc)
    ans[1] = b + max(tmpa, tmpc)
    ans[2] = c + max(tmpa, tmpb)

print(max(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n = int(inp())
	dic = read()
	for _ in range(n-1):
		arr = read()
		for i in range(3):
			# print(i, [dic[j] for j in range(3) if i != j])
			arr[i] += max([dic[j] for j in range(3) if i != j])
		dic = arr
		# print(dic, "*")
			# m = dic[]
			# for j in range(3):
			# 	if i != j:
			# print([dic[j]+arr[i] for j in range(3) if i!=j])
			# dic[i] = max([dic[j]+arr[i] for j in range(3) if i!=j])
			# print(dic, "****")
	print(max(dic))



if __name__ == "__main__":
	solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product

def solve():
    n = II()

    V = [[] for _ in range(n)]
    for i in range(n):
        a, b, c = MI()
        V[i] = [a, b, c]

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

    # dp[i][0] -> dp[i+1][1], dp[i+1][2]
    for i in range(1, n):

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
import bisect
from queue import Queue
from collections import deque

n = int(input())
table = [[int(i) for i in input().split()] for j in range(n)]

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


for i in range(n):
    if(i == 0):
        for j in range(3):
            d[i][j] = table[i][j]
    else:
        d[i][0] = table[i][0] + max(d[i-1][1], d[i-1][2])
        d[i][1] = table[i][1] + max(d[i-1][0], d[i-1][2])
        d[i][2] = table[i][2] + max(d[i-1][0], d[i-1][1])
print(max(d[n-1]))

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    happy_list = [[int(i) for i in input().strip().split()] for _ in range(N)]
    dp = [[None, None, None] for _ in range(N)]

    dp[0] = happy_list[0]

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

    return max(dp[-1])


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    dp0, dp1, dp2 = 0, 0, 0
    for _ in range(n):
        a, b, c = map(int, input().split())
        dp0, dp1, dp2 = max(dp1, dp2) + a, max(dp2, dp0) + b, max(dp0, dp1) + c
    print(max(dp0, dp1, dp2))
resolve()

Submission status: Accepted

Solution code:
import sys
rl = sys.stdin.readline
n = int(rl())
x, y, z = 0, 0, 0
for _ in range(n):
  a, b, c = map(int, rl().split())
  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:
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

n = int(rl())
li = [list(map(int, rl().split())) for _ in range(n)]
dp = [[0]*3 for _ in range(n)]
dp[0] = li[0]

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

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
import numpy as np

rl = sys.stdin.readline

n = int(rl())
li = [list(map(int, rl().split())) for _ in range(n)]
dp = np.zeros((n, 3), dtype=int)
dp[0] = li[0]

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

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

dp = [[0]*3 for _ in range(N+10)]
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:
N=int(input())
abc=[list(map(int,input().split())) for i in range(N)]
x,y,z = 0,0,0
for a,b,c in abc:
    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:
import sys
N = int(input())
abc = [list(map(int, input().split()))for _ in range(N)]
dp = [[0] * 3 for _ in range(N)]

if N == 1:
    print(max(abc[0]))
    sys.exit()

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())
v = []
for i in range(n):
    v.append(list(map(int,input().split(" "))))
for i in range(1,n):
    e = sorted(v[i-1][:])
    m1 = e[2]
    m2 = e[1]
    for j in range(3):
        if m1 == v[i-1][j]:
            v[i][j] += m2
        else: v[i][j] += m1
print(max(v[n-1]))

Submission status: Accepted

Solution code:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 200010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=spf[1] = -1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]
 
def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))
 
def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))
 
def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD
 
    return (num*(pow(den,MOD-2,MOD)))%MOD
 
def flush():
    return sys.stdout.flush()
 
'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
n = int(input())
a = [arrIN() for _ in range(n)]
dp = deepcopy(a)
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])
print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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


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

    dp = [[0 for _ in range(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 = ABC[i][0]
        b = ABC[i][1]
        c = ABC[i][2]

        dp[i][0] = max(dp[i][0], dp[i - 1][1] + a, dp[i - 1][2] + a)
        dp[i][1] = max(dp[i][1], dp[i - 1][0] + b, dp[i - 1][2] + b)
        dp[i][2] = max(dp[i][2], dp[i - 1][0] + c, dp[i - 1][1] + c)

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
happines=[]
dp=[[0,0,0,0,0,0] for i in range(N+1)]
for i in range(N):
    happy=list(map(int,input().split()))
    happines.append(happy)
def dp_search():
    zenkai=-1
    for i in range(N):
        if i<=N-1:
            dp[i + 1][0] = max(dp[i][2],dp[i][3])+happines[i][0]
            dp[i + 1][1] = max(dp[i][4],dp[i][5])+happines[i][0]
            dp[i + 1][2] = max(dp[i][0],dp[i][1])+happines[i][1]
            dp[i + 1][3] = max(dp[i][4],dp[i][5])+happines[i][1]
            dp[i + 1][4] = max(dp[i][0],dp[i][1])+happines[i][2]
            dp[i + 1][5] = max(dp[i][2],dp[i][3])+happines[i][2]
    print(max(dp[-1]))
dp_search()

Submission status: Accepted

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

Submission status: Accepted

Solution code:



n = int(input())

last = [0,0,0]
for i in range(n):
    new = list(map(int, input().split()))
    newDp = [0,0,0]
    for j in range(3):
        for k in range(3):
            if j!=k:
                newDp[j] = max(newDp[j], last[k]+new[k])
    last = newDp
print(max(last))

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
d = defaultdict(list)
for i in range(n):
  d[i] = list(map(int,input().split()))
mp = [[0,0,0] for i in range(n)] #maxpoint
mp[0] = d[0]
for i in range(1,n):
  mp[i][0] = max(mp[i-1][1],mp[i-1][2]) + d[i][0]
  mp[i][1] = max(mp[i-1][0],mp[i-1][2]) + d[i][1]
  mp[i][2] = max(mp[i-1][1],mp[i-1][0]) + d[i][2]
print(max(mp[n-1]))