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())
L = []
for i in range(N):
    L.append(list(map(int, input().split())))
# print(L)

# その日までの幸福度の最大, ではデータが不足
# ∵翌日何の行動がとれるかわからないから
# dp[i][j]:i+1日目に行動jをしたときの幸福度最大値

dp=[[0,0,0] for i in range(N)]
for j in range(3):
    dp[0][j]=L[0][j]
# print(dp)

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

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    abc = in_nl2(N)

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for n_i in range(n):
  if n_i == 0:
    dp[n_i][0] = ABC[n_i][0]
    dp[n_i][1] = ABC[n_i][1]
    dp[n_i][2] = ABC[n_i][2]
  else:
    dp[n_i][0] = max(ABC[n_i][0]+dp[n_i-1][1], ABC[n_i][0]+dp[n_i-1][2])
    dp[n_i][1] = max(ABC[n_i][1]+dp[n_i-1][0], ABC[n_i][1]+dp[n_i-1][2])
    dp[n_i][2] = max(ABC[n_i][2]+dp[n_i-1][0], ABC[n_i][2]+dp[n_i-1][1])
    
print(max(dp[-1]))

Submission status: Accepted

Solution code:
n=int(input())
temp=100
ans=0
dp=list(list(map(int,input().split())) for i in range(n))

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [[0 for _ in range(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(3):
            if j != k:
                dp[i+1][j] = max(dp[i+1][j], dp[i][k] + abc[j])

print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
prev_a = 0
prev_b = 0
prev_c = 0

for n in range(N):
    a, b, c = [int(i) for i in input().split(' ')]

    next_a = a + max(prev_b, prev_c)
    next_b = b + max(prev_a, prev_c)
    next_c = c + max(prev_a, prev_b)

    prev_a = next_a
    prev_b = next_b
    prev_c = next_c

print(max(prev_a, prev_b, prev_c))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n=int(input())
a,b,c=map(int,input().split())
dp=[[0]*3 for i in range(n)]
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())
  for j in range(3):
    if j==0:
      dp[i][j]=max(dp[i-1][1],dp[i-1][2])+a
    elif j==1:
      dp[i][j]=max(dp[i-1][0],dp[i-1][2])+b
    else:
      dp[i][j]=max(dp[i-1][0],dp[i-1][1])+c
      
print(max(dp[-1]))

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
happiness=[LI() for i in range(n)]
dp=[[0]*3 for i in range(n)]
dp[0]=happiness[0]
for i in range(n-1):
    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]+happiness[i+1][j])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
dp = [[0] * 3 for _ in range(n)]
for i in range(n):
    a, b, c = LI()
    if 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)
    else:
        dp[0] = a, b, c

print(max(dp[-1]))

Submission status: Accepted

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

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

for i in range(n):
    if i == 0:
        for j in range(3):
            dp[i][j] = li[i][j]
    else:
        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] + li[i][k])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())
data = [[] for _ in range(N)]
for i in range(N):
    data[i] = [int(i) for i in input().split()]

#%%
dp = [[0] * 3 for i in range(N + 1)]
for i in range(1, N + 1):
    for j in range(3):
        temp = max(dp[i - 1][j - 1], dp[i - 1][j - 2])
        dp[i][j]= data[i - 1][j] + temp

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [[0 for _ in range(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(3):
            if j!=k :
                dp[i+1][j]  = max( dp[i+1][j], dp[i][k] + abc[j])

print(max(dp[-1]))

Submission status: Accepted

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

happy_list = [[0, 0, 0]] # n日目にa|b|cを選んだときの幸福のそこまでの最大値
# before_act = -1 # a: 0, b: 1, c: 2
for n in range(N):
    before_happy_a, before_happy_b, before_happy_c = happy_list[-1]
    a, b, c = abc_list[n]
    tmp_happy_a = max(before_happy_b, before_happy_c) + a
    tmp_happy_b = max(before_happy_c, before_happy_a) + b
    tmp_happy_c = max(before_happy_a, before_happy_b) + c
    happy_list.append([tmp_happy_a, tmp_happy_b, tmp_happy_c])

print(max(happy_list[-1]))

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)

dpA,dpB,dpC = [0]*n,[0]*n,[0]*n
dpA[0],dpB[0],dpC[0] = A[0],B[0],C[0]

for i in range(1,n):
    dpA[i] = max(dpB[i-1],dpC[i-1])+A[i]
    dpB[i] = max(dpA[i-1],dpC[i-1])+B[i]
    dpC[i] = max(dpB[i-1],dpA[i-1])+C[i]

print(max(dpA[-1],dpB[-1],dpC[-1]))

Submission status: Accepted

Solution code:
INF = 10**9
N = int(input())
happiness = [[0, 0, 0]]
for _ in range(N):
  happiness.append(list(map(int, input().split())))
dp = [[-INF] * 3 for _ in range(N+1)]
dp[0] = [0, 0, 0]

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

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_a, dp_b, dp_c = [0] * n, [0] * n, [0] * n
dp_a[0] = A[0]
dp_b[0] = B[0]
dp_c[0] = C[0]

for i in range(1, n):
  dp_a[i] = max(dp_b[i-1], dp_c[i-1]) + A[i]
  dp_b[i] = max(dp_c[i-1], dp_a[i-1]) + B[i]
  dp_c[i] = max(dp_a[i-1], dp_b[i-1]) + C[i]
print(max(dp_a[-1], dp_b[-1], dp_c[-1]))

Submission status: Accepted

Solution code:
n = int(input())
l = []
pa = 0
pb = 0
pc = 0
for i in range(n):
    a,b,c = map(int,input().split())
    na = max((a+pb),(a+pc))
    nb = max((b+pa),(b+pc))
    nc = max((c+pa),(c+pb))
    pa = na
    pb = nb
    pc = nc

print(max(pa,pb,pc))

Submission status: Accepted

Solution code:
n=int(input())
x,y,z=0,0,0
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 input_li():
    return list(map(int, input().split()))

def input_int():
    return int(input())

N = input_int()
# dp[x][y] ... x日目にyを行った時の幸福度を格納する
dp = [[0] * 3 for _ in range(N)]
for i in range(N):
    a, b, c = input_li()
    if i == 0:
        dp[i][0] = a
        dp[i][1] = b
        dp[i][2] = c
    else:
        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=[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],dp[i][(j+2)%3])+l[i+1][j]
print(max(dp[n-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin,stdout

n = int(stdin.readline())
ls = list()
dp1 = [0] * n
dp2 = [0] * n
dp3 = [0] * n
for i in range(n):
	a, b, c = map(int, stdin.readline().split())
	if i == 0:
		dp1[0] = a
		dp2[0] = b
		dp3[0] = c
	else:
		dp1[i] = max(dp2[i - 1], dp3[i - 1]) + a
		dp2[i] = max(dp1[i - 1], dp3[i - 1]) + b
		dp3[i] = max(dp1[i - 1], dp2[i - 1]) + c
print(max(dp1[n - 1], dp2[n - 1], dp3[n - 1]))

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

x,y,z = 0,0,0
for _ in range(int(input())):
    a,b,c = ilele()
    d = a + max(y,z)
    e = b + max(x,z)
    f = c + max(x,y)
    x,y,z = d,e,f
print(max(x,y,z))

Submission status: Accepted

Solution code:
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

x,y,z = 0,0,0
for _ in range(int(input())):
    a,b,c = ilele()
    if x == y == z == 0:
        x,y,z = a,b,c
    else:
        d = a + max(y,z)
        e = b + max(x,z)
        f = c + max(x,y)
        x,y,z = d,e,f
print(max(x,y,z))

Submission status: Accepted

Solution code:
N = int(input())

vac = []
for i in range(N):
    vac.append(list(map(int, input().split())))
    
DP = [[0 for _ in range(3)] for _ in range(N+1)]

for i in range(N):
    for j in range(3):
        for k in range(3):
            if(j == k):
                continue
            DP[i+1][k] = max(DP[i+1][k], DP[i][j]+vac[i][k])
ans = 0
for i in DP[N]:
    ans = max(ans, i)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
h = [] #happiness
for i in range(n):
 a_input, b_input, c_input = map(int, input().split())
 h.append([a_input, b_input, c_input]) 
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 and dp[i][j] < dp[i-1][k] + h[i-1][j]:
       dp[i][j] = dp[i-1][k] + h[i-1][j]
ans = 0
for j in range(3):
 if ans < dp[n][j]:
   ans = dp[n][j]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

n = int(input())
a, b, c = list(map(int, input().split()))

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = [[int(i) for i in input().split()] for i in range(n)]

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

for i in range(1, n + 1):
    for j in range(3):
        for k in range(3):
            if j == k:
                # if same as previous day
                continue
            dp[i][j] = max(dp[i - 1][k] + a[i - 1][j], dp[i][j])

print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

dp = [0,0,0]
for a in arr:
	dp = [a[0]+max(dp[1],dp[2]),a[1]+max(dp[0],dp[2]),a[2]+max(dp[0],dp[1])]

print(max(dp))

Submission status: Accepted

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

dp=[[0,0,0] for n in range(n + 1)]
# dp = [[0] * 3] * (n + 1)

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])
                
res = 0
for j in range(3):
    res = max(res, dp[n][j])
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# Author: S Mahesh Raju
# Username: maheshraju2020
# Date: 30/07/2020

from sys import stdin,stdout
from math import gcd, ceil, sqrt
from collections import Counter
from bisect import bisect_left, bisect_right
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
mod = 1000000007

n = ii1()
cur = None
for i in range(n):
    a, b, c = iia()
    if not cur:
        cur = [a, b, c]
    else:
        t1 = max(cur[1], cur[2]) + a
        t2 = max(cur[0], cur[2]) + b
        t3 = max(cur[0], cur[1]) + c
        cur = [t1, t2, t3]
print(max(cur))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
data = ILL(N)

dp = [[0,0,0] for i in range(N+1)]

for i in range(N):
  dp[i+1][0] = max(dp[i+1][0],dp[i][1]+data[i][0],dp[i][2]+data[i][0])
  dp[i+1][1] = max(dp[i+1][1],dp[i][0]+data[i][1],dp[i][2]+data[i][1])
  dp[i+1][2] = max(dp[i+1][2],dp[i][0]+data[i][2],dp[i][1]+data[i][2])
  
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 = list(map(int, input().split()))
    for j in range(3):
        dp[i][j] = a[j] + max(dp[i - 1][(j+1) % 3], dp[i - 1][(j+2) % 3])

print(max(dp[N]))

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

print(max(dp[N]))

Submission status: Accepted

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

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


for i in range(n-1):
  #print("i={}日目".format(i+2))
  for j in range(3):
    #print("{}から遷移".format(dp[i][j]))
    for k in range(3):
      if j==k:
        continue
      if dp[i][j]+abc[i+1][k]>=dp[i+1][k]:
        dp[i+1][k]=dp[i][j]+abc[i+1][k]
      #print(dp)
      
print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

#B- Frog 2

def solution(nums):
    n = len(nums)
    dp = [0,0,0]
    for day in range(n):
        new_dp = [0,0,0]
        for i in range(3):
            for j in range(3):
                if i!=j:
                    new_dp[i] = max(new_dp[i] , dp[j]+ nums[day][i] )
        dp = new_dp
    return max(dp[0],dp[1],dp[2])

N = int(input())
nums = []
for _ in range(N):    
    day = list(map(int,input().split()))
    nums.append(day)
res = solution(nums)
print(res)