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())
memo =[[0,0,0] for _ in range(n)]
days = []
for i in range(n):
    days.append(list(map(int, input().split())))
memo[-1] = days[-1]


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

Submission status: Accepted

Solution code:
N = int(input())
happy = [list(map(int, input().split())) for _ in range(N)]
dp = [[-1]*3 for x in range(N)]

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

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

Submission status: Accepted

Solution code:
n=int(input())
dp=[0]*n
for i in range(n):
	dp[i]=[0]*3
dp[0][0],dp[0][1],dp[0][2]=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][2],dp[i-1][1])
	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:
N = int(input())
A, B, C = list(map(int, input().split()))

for i in range(N - 1):
    a, b, c = list(map(int, input().split()))
    A, B, C = max(B, C) + a, max(C, A) + b, max(A, B) + c
print(max(A, B, C))

Submission status: Accepted

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

n = int(input())

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

def happy(n, abc):
    da, db, dc = 0, 0, 0
    for a, b, c in abc:
        na = max(db, dc) + a
        nb = max(dc, da) + b
        nc = max(da, db) + c
        da, db, dc = na, nb, nc

    return max(da, db, dc)

print(happy(n, abc))

Submission status: Accepted

Solution code:

n = int(input())

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

def happy(n, a):
    d = [[0] * 3 for j in range(n)]
    for i in range(3):
        d[0][i] = a[0][i]

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

    return max(d[n - 1])

print(happy(n, a))

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, abc):
    la, lb, lc = 0, 0, 0
    for a, b, c in abc:
        na, nb, nc = max(lb + a, lc + a), \
            max(la + b, lc + b), max(la + c, lb + c)
        la, lb, lc = na, nb, nc
    return(max(la, lb, lc))

n = int(input())    # 1 <= n <= 10^5
abc = [list(map(int, input().rstrip().split())) for _ in range(n)]

print(f(n, abc))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, abc):
    dp = [0] * 3
    for a, b, c in abc:
        dp = [ max(dp[1] + a, dp[2] + a), \
               max(dp[0] + b, dp[2] + b), \
               max(dp[0] + c, dp[1] + c) ]
    return(max(dp))

n = int(input())    # 1 <= n <= 10^5
abc = [list(map(int, input().rstrip().split())) for _ in range(n)]

print(f(n, abc))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, abc):
    dp = [0] * 3
    for i in range(n):
        a, b, c = abc[i]
        dp0, dp1, dp2 = dp
        dp = [ max(dp1 + a, dp2 + a), \
               max(dp0 + b, dp2 + b), \
               max(dp0 + c, dp1 + c) ]
    return(max(dp))

n = int(input())    # 1 <= n <= 10^5
abc = [list(map(int, input().rstrip().split())) for _ in range(n)]

print(f(n, abc))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, abc):
    dp = [0] * 3
    for i in range(1, n + 1):
        a, b, c = abc[i - 1]
        dp = [ max(dp[1] + a, dp[2] + a), \
               max(dp[0] + b, dp[2] + b), \
               max(dp[0] + c, dp[1] + c) ]
    return(max(dp))

n = int(input())    # 1 <= n <= 10^5
abc = [list(map(int, input().rstrip().split())) for _ in range(n)]

print(f(n, abc))

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, abc):
    dp = [[0] * 3 for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(3):
            dp[i][j] = max(dp[i - 1][k] + abc[i - 1][j] \
                for k in range(3) if k != j)
    return(max(dp[n]))

n = int(input())    # 1 <= n <= 10^5
abc = [list(map(int, input().rstrip().split())) for _ in range(n)]

print(f(n, abc))

Submission status: Accepted

Solution code:
n=int(input())
L=[0,0,0] #a,b,c prosli
for i in range(n):
    a,b,c=map(int,input().split())
    L=[max(L[1]+a,L[2]+a), max(L[0]+b,L[2]+b), max(L[0]+c,L[1]+c)]
print(max(L))

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] =  [int(x) for x in input().split()]
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]+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[-1][0],dp[-1][1],dp[-1][2]))

Submission status: Accepted

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

for i in range(n):
    cur = [int(i) for i in input().split()]
    joy.append(cur)

dp = [[0 for i in range(n+5)] for j in range(3)]
import sys
sys.setrecursionlimit(10000000)
def brute(curday, prvmove):
    if curday>=n:
        return 0
    if dp[prvmove][curday]!=0:
        return dp[prvmove][curday]
    ans = 0
    
    for i in range(3):
        if prvmove == i:
            continue
        ans = max(ans, brute(curday+1, i) + joy[curday][i])

    #print('with', daysleft)
    #print('returning', ans)
    dp[prvmove][curday] = ans
    return ans

ans = 0

for i in range(3):
    ans = max(ans, brute(0, i))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a, b, c = 0, 0, 0

for i in range(n):
  x, y, z = map(int, input().split())
  a, b, c = x+max(b,c), y+max(a,c), z+max(a,b)
print(max(a,b,c))

Submission status: Accepted

Solution code:
import pdb


def solve(a,n):
    if n==1:
        return max(a[0])
    dp = [[0,0,0] for i in xrange(n)]
    dp[0]= [a[0][0],a[1][0],a[2][0]]
    for i in xrange(1,n):
        try:
            dp[i][0] = a[0][i]+max(dp[i-1][1],dp[i-1][2])
            dp[i][1] = a[1][i]+max(dp[i-1][0],dp[i-1][2])
            dp[i][2] = a[2][i]+max(dp[i-1][0],dp[i-1][1])
        except:
            pdb.set_trace()
    return max(dp[n-1])

        
    

if __name__=='__main__':
    n = int(raw_input())
    
    a = [[],[],[]]
    for i in xrange(n):
        ai,bi,ci = map(int,raw_input().split())
        a[0].append(ai)
        a[1].append(bi)
        a[2].append(ci)
    print solve(a,n)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
a = [[0]*N for i in range(3)]
for i in range(N):
    bin = [int(i) for i in input().split()]
    for j in range(3):
        a[j][i] = bin[j]

dp = [[0]*(N+1) for i in range(3)]
for i in range(3):
    dp[i][1] = a[i][0]
ls = [0, 1, 2]

for i in range(2, N+1):
    for j in ls:
        for k in ls:
            if j != k:
                dp[j][i] = max(dp[j][i], dp[k][i-1] + a[j][i-1])
ans = 0
for i in range(3):
    ans = max(ans, dp[i][N])
print(ans)

Submission status: Accepted

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

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

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/2
Solved on 2019/3/
@author: shinjisu
"""


# Educational Dynamic Programming
# import math
import numpy as np


def getInt(): return int(input())


# def getIntList(): return [int(x) for x in input().split()]
def getIntList(): return np.array(input().split(), dtype='int')


# def zeros(n): return [0]*n
def zeros(n): return np.zeros(n, dtype='int')


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**12


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def prob_A():  # Frog 1
    N = getInt()
    H = getIntList()
    dmp((N, H), 'N, H')
    c = zeros(N)
    c[1] = abs(H[1]-H[0])
    for i in range(2, N):
        c[i] = min(c[i-1] + abs(H[i]-H[i-1]),
                   c[i-2] + abs(H[i]-H[i-2]))
    dmp(c, 'c')
    return c[N-1]


def prob_B_TLE():  # Frog 2 3/16 TLE
    N, K = getIntList()
    H = getIntList()
    dmp((N, K, H), 'N, K, H')
    c = np.zeros(N)
    c[0] = 0
    for i in range(1, N):
        #c[i] = INF
        for j in range(max(0, i-K), i):
            c[i] = min(c[i], c[j] + abs(H[i]-H[j]))
    dmp(c, 'c')
    return c[N-1]


def prob_B():  # Frog 2
    N, K = getIntList()
    H = np.array(input().split(), dtype='int')
    dmp((N, K, H), 'N, K, H')
    c = np.zeros(N, dtype='int')
    c[0] = 0
    for i in range(1, N):
        c[i] = np.min(c[max(0, i-K):i] + np.abs(H[max(0, i-K):i] - H[i]))
    dmp(c, 'c')
    return c[N-1]


def prob_C():  # Vacation
    N = getInt()
    a = zeros(N)
    b = zeros(N)
    c = zeros(N)
    for i in range(N):
        a[i], b[i], c[i] = getIntList()
    dmp(N, 'N')
    dmp(a, 'a')
    dmp(b, 'b')
    dmp(c, 'c')
    dpa = zeros(N)
    dpb = zeros(N)
    dpc = zeros(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], dpc[i-1]) + a[i]
        dpb[i] += max(dpc[i-1], dpa[i-1]) + b[i]
        dpc[i] += max(dpa[i-1], dpb[i-1]) + c[i]
    dmp(dpa, 'dpa')
    dmp(dpb, 'dpb')
    dmp(dpc, 'dpc')
    return max(dpa[N-1], dpb[N-1], dpc[N-1])


debug = False  # True False
ans = prob_C()
print(ans)
#for row in ans:
#    print(row)

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] * n for _ in range(3)]
dp[0][-1], dp[1][-1], dp[2][-1] = a[-1], b[-1], c[-1]

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

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

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)]
dp[-1] = [a[-1], b[-1], c[-1]]

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

print(max(dp[0]))

Submission status: Accepted

Solution code:

N  = int(input())
a = []
b = []
c = [] 
for i in range(N):
    aa, bb, cc = [int(i) for i in input().split()] 
    a.append(aa)
    b.append(bb)
    c.append(cc)

# cost[i][1], cost[i][2], cost[i][3]
cost = [[0 for i in range(3)] for j in range(N)]

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

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

print(max(cost[N-1][0], cost[N-1][1],cost[N-1][2]))

Submission status: Accepted

Solution code:
n = int(input())
A = [0]*n
B = [0]*n
C = [0]*n

A[0], B[0], C[0] = map(int, input().split())
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]))

Submission status: Accepted

Solution code:
N = int(input())

happinesses_each_day = []
for n in range(N):
    happinesses_each_day.append(list(map(int, input().split())))

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

for i, happinesses in enumerate(happinesses_each_day):
    for j, happiness in enumerate(happinesses):
        for k in range(3):
            if j == k:
                continue
            if dp[i + 1][k] < (dp[i][j] + happiness):
                dp[i + 1][k] = (dp[i][j] + happiness)

print(max(dp[N]))

Submission status: Accepted

Solution code:
n=int(input())
A,B,C=0,0,0

for _ in range(n):
  a,b,c=map(int,input().split())
  A,B,C=a+max(B,C),b+max(A,C),c+max(A,B)

print(max(A,B,C))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
x, y, z = 0, 0, 0

for i 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:
N=int(input())
H=[[int(x) for x in input().split()] for y in range(N)]

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

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

for i in range(1,N):
    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[-1]))

Submission status: Accepted

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

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

Submission status: Accepted

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

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

for idx, val in enumerate(lis[1:], start=1):
	a = val[0] + max([dp[idx-1][i] for i in range(3) if 0 != i ])
	b = val[1] + max([dp[idx-1][i] for i in range(3) if 1 != i ])
	c = val[2] + max([dp[idx-1][i] for i in range(3) if 2 != i ])
	dp[idx] = [a,b,c]
print(max(dp[-1]))

Submission status: Accepted

Solution code:
from sys import stdin
n=int(stdin.readline())
dp=[0]*3
for i in range(n):
    before=[0,0,0]
    l=list(map(int,stdin.readline().split()))
    for i in range(3):
        before[i]=max(dp[(i+1)%3],dp[(i+2)%3])+l[i]
    dp=before
print(max(dp))

Submission status: Accepted

Solution code:
def solve(actions, n):
    # 1-origin
    dp = [[0] * 4 for _ in range(n + 1)]

    for day, action in enumerate(actions, 1):
        action1, action2, action3 = action[0], action[1], action[2]
        for key in range(1, 4):
            if key == 1:
                dp[day][key] = action1 + max(dp[day - 1][2], dp[day - 1][3])
            elif key == 2:
                dp[day][key] = action2 + max(dp[day - 1][1], dp[day - 1][3])
            else:
                dp[day][key] = action3 + max(dp[day - 1][1], dp[day - 1][2])

    return max(dp[n])


def main():
    n = int(input())
    actions = []

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

    ans = solve(actions, n)
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]
aa = [0]*(n+1)
bb = [0]*(n+1)
cc = [0]*(n+1)
for i in range(1,n+1):
  I = i-1
  front = abc[I]
  aa[i] = front[0] + max([bb[I],cc[I]])
  bb[i] = front[1] + max([aa[I],cc[I]])
  cc[i] = front[2] + max([bb[I],aa[I]])
print(max([aa[n],bb[n],cc[n]]))

Submission status: Accepted

Solution code:
#n,k=map(int,input().split())
n=int(input())
#h=list(map(int,input().split()))
abc=[]
for i in range(n):
    abc.append(list(map(int,input().split())))
dp=[]
dp.append([abc[0][0],abc[0][1],abc[0][2]])
for i in range(1,n):
    dp.append([max(dp[i-1][1]+abc[i][0],dp[i-1][2]+abc[i][0]),max(dp[i-1][0]+abc[i][1],dp[i-1][2]+abc[i][1]),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:
def solve(abc):
    dp1 = [0, 0, 0]
    dp2 = [0, 0, 0]
    for i in abc:
        for j in range(3):
            for k in range(3):
                if j == k:
                    continue
                dp2[j] = max(dp2[j], dp1[k] + i[j])
        for j in range(3):
            dp1[j] = dp2[j]
    return max(dp2)

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

Submission status: Accepted

Solution code:
n = int(input())

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

# n日目に act を行うときの最大値
dp = [None] * n

# 初期条件： 0日目にa, b, c (= 0, 1, 2) を行うときの最大値
dp[0] = [0, 0, 0]
dp[0][0] = data[0][0]
dp[0][1] = data[0][1]
dp[0][2] = data[0][2]

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

mx = max(dp[n - 1])

print(mx)

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 for _ in range(N)] for i in range(3) ]
flag = ""

dp[0][0] = A[0]
dp[1][0] = B[0]
dp[2][0] = C[0]

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

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

Submission status: Accepted

Solution code:
N=int(input())
abc=[[0 for i in range(3)] for j in range(N)]
for i in range(N):
    A=list(map(int,input().split()))
    for j in range(3):
        abc[i][j]=A[j]
dp=[[0,0,0] for i in range(N+1)]
for i in range(N):
    for j in range(3):
        buf=[]
        for h in range(3):
            if h!=j:
                buf.append(dp[i][h]+abc[i][h])
        dp[i+1][j]=max(buf)
print(max(dp[N]))

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())
lists = []

for i in range(N):
    lists.append(list(map(int,input().split())))

dp = [[0 for i in range(3)] for j in range(N)]
dp[0] = lists[0]
for i in range(1,N):
    for j in [0,1,2]:

        if j == 0:
            dp[i][j] = lists[i][0] + max(dp[i - 1][1], dp[i - 1][2])
        elif j == 1:
            dp[i][j] = lists[i][1] + max(dp[i - 1][0], dp[i - 1][2])
        else:
            dp[i][j] = lists[i][2] + max(dp[i - 1][0], dp[i - 1][1])

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

Submission status: Accepted

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

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

for i in range(n):
    for j in range(3):
        DP[i+1][j] = max(DP[i][k] + A[i][j] for k in range(3) if j != k)

print(max(DP[n]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
import numpy as np
abc = np.array([[int(x) for x in input().split()] for y in range(n)],dtype=int)
dp = np.zeros((n,3),dtype=int)
dp[0] = abc[0]
for p in range(1,n):
    dp[p][0] = max(dp[p-1][1],dp[p-1][2]) + abc[p][0]
    dp[p][1] = max(dp[p-1][0],dp[p-1][2]) + abc[p][1]
    dp[p][2] = max(dp[p-1][0],dp[p-1][1]) + abc[p][2]
print(max(dp[n-1]))

Submission status: Accepted

Solution code:
###modular exponentiation: a^n % M
#pow(a, n, M) 
### gcd: gcd(a, b)
#import fractions
#fractions.gcd(a, b)
### LCM (M, N)
#lcm = M*N/fractions.gcd(M, N)
INF = 1000000000+5

def get_res(N, A):
    DPA = [0]*N
    DPB = [0]*N
    DPC = [0]*N
    a0, b0, c0 = A[0]
    DPA[0] = a0
    DPB[0] = b0
    DPC[0] = c0
    for i in range(1, N):
        # DP[i] = minimum penalty incurred in reaching stone i from stone 1
        ai, bi, ci = A[i]
        DPA[i] = ai + max(DPB[i-1], DPC[i-1])
        DPB[i] = bi + max(DPA[i-1], DPC[i-1])
        DPC[i] = ci + max(DPA[i-1], DPB[i-1])
    return max(DPA[N-1], DPB[N-1], DPC[N-1])

N = int(input())
A = []
for _ in range(N):
    L = [int(s) for s in input().split(" ")]
    A.append(L)
result = get_res(N, A)
print("{}".format(result))

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
A = []
B = []
C = []
for _ 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):
    dp[0][i] = max(dp[1][i-1], dp[2][i-1])+A[i]
    dp[1][i] = max(dp[2][i-1], dp[0][i-1])+B[i]
    dp[2][i] = max(dp[0][i-1], dp[1][i-1])+C[i]

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

Submission status: Accepted

Solution code:
# C
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 _ in range(N)]

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

Submission status: Accepted

Solution code:
N=int(input())
inputs=[]
dp=[]
for _ in range(N):
    inputs.append([int(x) for x in input().split()])
    dp.append([0]*3)

for j in range(3):
    dp[0][j]=inputs[0][j]

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-1][k],dp[i][j])
        
        dp[i][j]+=inputs[i][j]



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

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
abc = []
for i in range(n):
    abc.append([int(x) for x in stdin.readline().rstrip().split()])
dp = [[0] * (n + 1) for i in range(3)]
dp[0][0] = abc[0][0]
dp[1][0] = abc[0][1]
dp[2][0] = abc[0][2]
for i in range(n - 1):
    for j in range(3):
        for k in range(3):
            if j != k:
                renew = dp[k][i] + abc[i + 1][j]
                if dp[j][i + 1] < renew:
                    dp[j][i + 1] = renew
ans = 0
for i in range(3):
    if ans < dp[i][n-1]:
        ans = dp[i][n-1]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
for _ in range(n):
    ai, bi, ci = list(map(int, input().split()))
    a.append([ai, bi, ci])
    
dp = [[0]*3 for _ in range(n+1)]

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_list_of_int():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


# inputs
N = 0
A, B, C = [0], [0], [0]


def set_inputs():
    global N, A, B, C
    N = get_int()
    a, b, c = [], [], []
    for _ in range(N):
        x, y, z = get_list_of_int()
        a.append(x)
        b.append(y)
        c.append(z)
    A, B, C = a, b, c


def main():
    set_inputs()
    happiness = [(A[0], B[0], C[0])]
    for i in range(1, N):
        h = happiness[i-1]
        a = max(h[1], h[2]) + A[i]
        b = max(h[0], h[2]) + B[i]
        c = max(h[0], h[1]) + C[i]
        happiness.append((a, b, c))
    print(max(happiness[N-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for i in range(N):
    a, b, c = abc[i]
    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(max(dp[N]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 09:48:04 2019

@author: maezawa
"""

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

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

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

Submission status: Accepted

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

dp[0] = [0,0,0]
for i in range(N):
  dp[i+1] = [max([dp[i][k] for k in range(L) if k != j]) + X[i][j] for j in range(L)]

print(max(dp[-1]))

Submission status: Accepted

Solution code:
#coding:utf-8

n = int(input())

x = 0
y = 0
z = 0
for i in range(n):
    a,b,c = map(int,input().split())
    nx = max(y,z) + a
    ny = max(x,z) + b
    nz = max(x,y) + c
    x = nx
    y = ny
    z = nz

print(max(x,y,z))

Submission status: Accepted

Solution code:
n = int(input())

x = 0
y = 0
z = 0
for i in range(n):
    a,b,c = map(int,input().split())
    nx = max(y,z) + a
    ny = max(x,z) + b
    nz = max(x,y) + c
    x = nx
    y = ny
    z = nz

print(max(x,y,z))

Submission status: Accepted

Solution code:
N = int(input())
happy = [[int(n) for n in input().split()] 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 not j == k:
                dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + happy[i][k])

print(max(dp[N]))

Submission status: Accepted

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

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

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

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

ans = 0
for k in range(3):
    ans = max(ans, dp[n-1][k])

print(ans)

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))
N = int(input())
sa, sb, sc = 0, 0, 0
for i in range(N):
    a, b, c = inpl()
    sa, sb, sc = max(sb+a, sc+a), max(sa+b, sc+b), max(sa+c, sb+c)
print(max(sa, sb, sc))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**8) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
abc = [list(li()) for _ in range(n)]

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

for day in range(n):
    ai,bi,ci = abc[day]
    dp[day+1][0] = max(dp[day][1], dp[day][2]) + ai
    dp[day+1][1] = max(dp[day][2], dp[day][0]) + bi
    dp[day+1][2] = max(dp[day][0], dp[day][1]) + ci
    
print(max(dp[n]))