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:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev


def main():
	N = int(input())
	abc = []
	for i in range(N):
		a,b,c = map(int, input().split(" "))
		abc.append((a,b,c))
		
	DP = [[0 for _ in range(3)] for _ in range(N)]
	
	for i, val in enumerate(abc):
		a, b, c = val
		if i == 0:
			DP[i][0] = a
			DP[i][1] = b
			DP[i][2] = c
			continue
		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][0], DP[N-1][1], DP[N-1][2]))
	
	
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:

def vac(l,n):
    dp=[[0 for i in range(3)]for j in range(n+1)]
    for i in range(1,n+1):
        x=l[i-1]
        for j in range(3):
            for k in range(3):
                if(k==j):
                    continue
                else:
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+x[k])
    m=max(dp[n][0],max(dp[n][1],dp[n][2]))
    # print(dp)
    return m

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

# print(l)
print(vac(l,n))

Submission status: Accepted

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

dp = [[0] * N , [0] * N, [0] * N]

for i, (a, b, c) in enumerate(lst):
    if i == 0:
        dp[0][0] = a
        dp[1][0] = b
        dp[2][0] = c
    else:
        a_ob = dp[0][i-1]
        b_ob = dp[1][i-1]
        c_ob = dp[2][i-1]
        dp[0][i] = max(b_ob + a, c_ob + a)
        dp[1][i] = max(a_ob + b, c_ob + b)
        dp[2][i] = max(a_ob + c, b_ob + c)
        
print(max(dp[0][-1], dp[1][-1], dp[2][-1]))

Submission status: Accepted

Solution code:
N = int(input())
abc = list(list(map(int,input().split()))for i 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][j-1],DP[i][j-2])+abc[i][j]
print(max(DP[-1]))

Submission status: Accepted

Solution code:
n = int(input())
ls = [[int(x) for x in input().split()] for _ in range(n)]

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

for i in range(1,n+1):

    dp[i][0] = ls[i-1][0] + max(dp[i-1][1],dp[i-1][2])
    dp[i][1] = ls[i-1][1] + max(dp[i-1][0],dp[i-1][2])
    dp[i][2] = ls[i-1][2] + max(dp[i-1][0],dp[i-1][1])

print(max(dp[n]))

Submission status: Accepted

Solution code:
# Educational DP Contest C-Vacation

def solve():
    n = int(input())
    dpa = [0] * n
    dpb = [0] * n
    dpc = [0] * n
    
    a, b, c = list(map(int, input().split()))
    dpa[0] = a
    dpb[0] = b
    dpc[0] = c
    for i in range(1, n):
        a, b, c = list(map(int, input().split()))
        dpa[i] = max(dpb[i-1] + a, dpc[i-1] + a)
        dpb[i] = max(dpa[i-1] + b, dpc[i-1] + b)
        dpc[i] = max(dpb[i-1] + c, dpa[i-1] + c)
    return(max(dpa[-1], dpb[-1], dpc[-1]))

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

Submission status: Accepted

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

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

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

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

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

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

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#dp3 #Vacation
import sys
def S(): return list(sys.stdin.readline())[:-1]
def LI(): return list(map(int,sys.stdin.readline().split()))
def c():
    n = int(input())
    dpa = [0]*n
    dpb = [0]*n
    dpc = [0]*n

    a,b,c = LI()
    dpa[0] = a
    dpb[0] = b
    dpc[0] = c
    for i in range(1,n):
        a,b,c = LI()
        dpa[i] = max(dpb[i-1] + a,dpc[i-1] + a)
        dpb[i] = max(dpa[i-1] + b,dpc[i-1] + b)
        dpc[i] = max(dpa[i-1] + c,dpb[i-1] + c)
    print(max(dpa[-1],dpb[-1],dpc[-1]))
if __name__ == '__main__':
    c()

Submission status: Accepted

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

def c():
    n = int(input())
    dpa = [0]*n
    dpb = [0]*n
    dpc = [0]*n

    a,b,c = list(map(int,input().split()))
    dpa[0] = a
    dpb[0] = b
    dpc[0] = c
    for i in range(1,n):
        a,b,c = list(map(int,input().split()))
        dpa[i] = max(dpb[i-1] + a,dpc[i-1] + a)
        dpb[i] = max(dpa[i-1] + b,dpc[i-1] + b)
        dpc[i] = max(dpa[i-1] + c,dpb[i-1] + c)
    print(max(dpa[-1],dpb[-1],dpc[-1]))
if __name__ == '__main__':
    c()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#dp3 #Vacation
n = int(input())
dpa = [0]*n
dpb = [0]*n
dpc = [0]*n

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

Submission status: Accepted

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

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

for i in range(1, N+1):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            #前の値がdp[i-1][j]で今選んでいるのがa[i-1][k]
            dp[i][k] = max(dp[i][k], dp[i-1][j] + a[i-1][k])

print(max(dp[N]))

Submission status: Accepted

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


def main():
    n = int(input())
    abc = [[0 for _ in range(3)] for _ in range(n)]
    dp = [[0 for _ in range(3)] for _ in range(n + 1)]

    for i in range(n):
        ai, bi, ci = map(int, input().split())
        abc[i][0] = ai
        abc[i][1] = bi
        abc[i][2] = ci

    # See:
    # https://qiita.com/drken/items/dc53c683d6de8aeacf5a
    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] + abc[i][k])

    print(max(dp[n]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = inp()
abc = [inpl() for _ in range(N)]
dp = [[0]*3 for _ in range(N)]
dp[0] = abc[0]

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
def factorial(n):
    if (n==0) or (n==1):
        return 1
    ret = 1
    for i in range(2, n+1):
        ret *= i
    return ret
def combination(n, k):
    return factorial(n)//factorial(k)//factorial(n-k)
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
abc = LIR(N)

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

for i in range(N):
    a, b, c = abc[i]
    dp[A][i+1] = max(dp[B][i], dp[C][i]) + a
    dp[B][i+1] = max(dp[A][i], dp[C][i]) + b
    dp[C][i+1] = max(dp[A][i], dp[B][i]) + c

print(max(dp[A][N], dp[B][N], dp[C][N]))

Submission status: Accepted

Solution code:
N=int(input())
Days=[]
for _ in range(N):
    a,b,c=list(map(int,input().strip().split(" ")))
    Days+=[(a,b,c)]

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

for i in range(N):
    if i==0:
        for j in range(3):
            dp[0][j]=Days[0][j]
    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]+Days[i][j])
print(max(dp[-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.append(a)
    B.append(b)
    C.append(c)

maxA = [0 for i in range(N)]
maxB = [0 for i in range(N)]
maxC = [0 for i in range(N)]

maxA[0] = A[0]
maxB[0] = B[0]
maxC[0] = C[0]

for i in range(1, N) :
    maxA[i] = max(maxB[i - 1], maxC[i - 1]) + A[i]
    maxB[i] = max(maxA[i - 1], maxC[i - 1]) + B[i]
    maxC[i] = max(maxA[i - 1], maxB[i - 1]) + C[i]

print(max(maxA[N - 1], maxB[N - 1], maxC[N - 1]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

N = int(input())
hpns = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0, 0, 0] for _ in [0]*(N)]
dp[0] = hpns[0]

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


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

Submission status: Accepted

Solution code:
N = int(input())
a = []
b = []
c = []

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

dp_a = [-1] * N
dp_b = [-1] * N
dp_c = [-1] * 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] = dp_b[i-1] + a[i] if dp_b[i-1] > dp_c[i-1] else dp_c[i-1] + a[i]
    dp_b[i] = dp_a[i-1] + b[i] if dp_a[i-1] > dp_c[i-1] else dp_c[i-1] + b[i]
    dp_c[i] = dp_a[i-1] + c[i] if dp_a[i-1] > dp_b[i-1] else dp_b[i-1] + c[i]

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
"Template made by : https://codeforces.com/profile/c1729 , github repo : https://github.com/cheran-senthil/PyRival"
from __future__ import division, print_function
import bisect
import math
import itertools
import sys
from atexit import register

if sys.version_info[0] < 3:
    from io import BytesIO as stream
else:
    from io import StringIO as stream


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

def main():
    n=int(input())
    l1=[]
    for i in range(n):
        l1.append(list(map(int,input().split())))
    dp=[ [0]*3 for _ in range(n)]
    dp[0]=l1[0]
    for i in range(1,n):
        dp[i][0]=l1[i][0]+max(dp[i-1][1],dp[i-1][2])
        dp[i][1]=l1[i][1]+max(dp[i-1][0],dp[i-1][2])
        dp[i][2]=l1[i][2]+max(dp[i-1][0],dp[i-1][1])
    print(max(dp[-1]))
if __name__ == '__main__':
    sync_with_stdio(False)
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
def factorial(n):
    if (n==0) or (n==1):
        return 1
    ret = 1
    for i in range(2, n+1):
        ret *= i
    return ret
def combination(n, k):
    return factorial(n)//factorial(k)//factorial(n-k)
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
abc = LIR(N)

#dpb[i] = max(dpa[i-1], dpc[i-1])

dpa = [0]*(N+1)
dpb = [0]*(N+1)
dpc = [0]*(N+1)

for i in range(1, N+1):
    dpa[i] = max(dpb[i-1], dpc[i-1]) + abc[i-1][0]
    dpb[i] = max(dpa[i-1], dpc[i-1]) + abc[i-1][1]
    dpc[i] = max(dpa[i-1], dpb[i-1]) + abc[i-1][2]

print(max(dpa[N], dpb[N], dpc[N]))

Submission status: Accepted

Solution code:
N = int(input())

matrix = []
for _ in range(N):
    matrix.append(list(map(int, input().split())))
    
dp_matrix = [[0, 0, 0]]

for i in range(N):
    dp_matrix_list = [0, 0, 0]
    for j in range(3):
        for k in range(3):
            if (j != k) and (dp_matrix_list[j] < dp_matrix[i][k] + matrix[i][j]):
                dp_matrix_list[j] = dp_matrix[i][k] + matrix[i][j]
    dp_matrix.append(dp_matrix_list)
    
print(max(dp_matrix[-1]))

Submission status: Accepted

Solution code:
# @author 

import sys

class CVacation:
    class Activity:
        def __init__(self, a, b, c):
            self.a = a
            self.b = b
            self.c = c

    def solve(self):
        n = int(input())
        a = []
        for i in range(n):
            a.append([int(_) for _ in 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):
            for j in range(3):
                for k in range(3):
                    if k != j:
                        dp[i][j] = max(dp[i - 1][k] + a[i][j], dp[i][j])

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

solver = CVacation()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
N = int(input())
D = [[0, 0, 0] for _ in range(N)]
for i in range(N):
    a = tuple(map(int, input().split()))
    for j in range(3):
        D[i][j] = a[j]

INIT = -1
dp = [[INIT, INIT, INIT] for _ in range(N)]
dp[0][0] = D[0][0]
dp[0][1] = D[0][1]
dp[0][2] = D[0][2]

for i in range(1, N):
    for j in range(3):
        tmp = INIT
        for k in range(3):
            if k == j:
                continue
            tmp = max(tmp, dp[i-1][k] + D[i][j])
        dp[i][j] = tmp

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

Submission status: Accepted

Solution code:
import math
N = int(input())
days = []
temp = [list(map(int, input().split(" "))) for _ in range(N)]
days.extend(temp)


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


dp[1] = days[0]

for d in range(1,N ):
    for a in range(3): #d+1日目にする活動
        cands = []
        for i in range(3):
            if i != a:
                cands.append(dp[d][i])

        dp[d+1][a] = max(cands) + days[d][a]

print(max(dp[-1]))

Submission status: Accepted

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

INIT = -1
dp = [[INIT, INIT, INIT] for _ in range(N)]
dp[0][0] = D[0][0]
dp[0][1] = D[0][1]
dp[0][2] = D[0][2]

for i in range(1, N):
    for j in range(3):
        tmp = INIT
        for k in range(3):
            if k == j:
                continue
            tmp = max(tmp, dp[i-1][k] + D[i][j])
        dp[i][j] = tmp

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

Submission status: Accepted

Solution code:

N = int(input())


lis = [[0,0,0]]

for i in range(N):

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

    lis.append( [ a + max( lis[-1][1] , lis[-1][2] ) , b + max( lis[-1][0] , lis[-1][2] ), c + max( lis[-1][0] , lis[-1][1] ) ] )

print (max (lis[-1]))

Submission status: Accepted

Solution code:
"C Vacation"
N = int(input())
summer = []
for i in range(N):
    active = list(map(int, input().split()))
    summer.append(active)

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

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

print(max(dp[-1]))

Submission status: Accepted

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

max_a = [0] * N
max_b = [0] * N
max_c = [0] * N

max_a[0] = A[0]
max_b[0] = B[0]
max_c[0] = C[0]

for i in range(1,N):
    max_a[i] = max(max_b[i-1], max_c[i-1]) + A[i]
    max_b[i] = max(max_a[i-1], max_c[i-1]) + B[i]
    max_c[i] = max(max_a[i-1], max_b[i-1]) + C[i]

print(max(max_a[N-1], max_b[N-1], max_c[N-1]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline
def intinput():return map(int,input().split())

n=int(input())
x=[tuple(intinput()) for i in range(n)]
dp=[[0,0,0] for i in range(n+1)]
for i in range(len(x)):
    for j in range(3):
        dp[i+1][j]=max(dp[i][j-1]+x[i][j-1],dp[i][j-2]+x[i][j-2])
print(max(dp[-1]))

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(_) for _ in 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(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][2] + b[i+1], dp[i][0] + 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:
def resolve():
    (N) = int(input())
    abcs = [list(map(int, input().split(" "))) for _ in range(N)]
    dps = [[0]*3 for _ in range(N)]
    dps[0] = abcs[0]

    for i in range(1, N):
        for j in range(3):
            dps[i][j] = max(dps[i-1][(j+1)%3]+abcs[i][j], dps[i-1][(j+2)%3]+abcs[i][j])

    print(max(dps[-1]))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
# happy[i][j] : i日めにjをした。(j=0:a, j=1:b, j=2:c)
happy = [[0, 0, 0, 0] for i in range(n)]
for i in range(n):
    a,b,c = map(int, input().split())
    if i == 0:
        happy[0][0] = a
        happy[0][1] = b
        happy[0][2] = c
    else:
        happy[i][0] = max(happy[i-1][1], happy[i-1][2]) + a
        happy[i][1] = max(happy[i-1][0], happy[i-1][2]) + b
        happy[i][2] = max(happy[i-1][0], happy[i-1][1]) + c

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

Submission status: Accepted

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

# dp = [[None] * n for _ in range(3)]
# def dfs(ng, depth=n - 1):
#     if dp[ng][depth] != None:
#         return dp[ng][depth]
#
#     if depth == 0:
#         dp[ng][0] = max([abc[depth][x] for x in range(3) if x != ng])
#         return dp[ng][0]
#     dp[ng][depth] = max(dfs(x, depth - 1) + abc[depth][x] for x in range(3) if x != ng)
#     return dp[ng][depth]
#
# print(dfs(0))
# print(dfs(1))
# print(dfs(2))
# print(dp)


dp = [[None] * n for _ in range(3)]
for ng in range(3):
    dp[ng][0] = max([abc[0][x] for x in range(3) if x != ng])

for depth in range(1, n):
    for ng in range(3):
        dp[ng][depth] = max(dp[x][depth - 1] + abc[depth][x] for x in range(3) if x != ng)
print(max(dp[i][-1] for i in range(3)))

Submission status: Accepted

Solution code:
N = int(input())
table = [[0 for i in range(N+1)] for j in range(3)]
for i in range(N):
    abc = list(map(int, input().split()))
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            table[k][i+1] = max(table[k][i+1], table[j][i]+abc[k])
ans = max([table[i][-1] for i in range(3)])
print(ans)

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
a, b, c = [0] * N, [0] * N, [0] * N
dp = [[0] * 3 for _ in range(N)]

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

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]

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

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = []
c = []
for i in range(n):
    m,v,p = map(int,input().split())
    a.append(m)
    b.append(v)
    c.append(p)
d = [[0]*3 for i in range(n)]
d[0][0]=a[0]
d[0][1]=b[0]
d[0][2]=c[0]
for i in range(1,n):
    for j in range(3):
        if j == 0:
            d[i][j] = max(d[i-1][1],d[i-1][2]) + a[i]
        elif j == 1:
            d[i][j] = max(d[i-1][0],d[i-1][2]) + b[i]
        else:
            d[i][j] = max(d[i-1][0],d[i-1][1]) + c[i]
print(max(d[-1][0],d[-1][1],d[-1][2]))

Submission status: Accepted

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

Submission status: Accepted

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

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

# 1日目の初期化
dp[0]= ABC[0]
for i in range(1,N):
    # 次ステップでA,B,Cに行く場合、
    for toi in range(3):
        s = 0
        # どこから来るのが最大か求める
        for fromi in range(3):
            # 同じ行動はとらない
            if toi==fromi:
                continue
            s = max(s, dp[i-1][fromi] + ABC[i][toi])
        dp[i][toi] = s

print(max(dp[-1]))

Submission status: Accepted

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

dp = [[0 for 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(1,N):
    for toi in range(3):
        s = 0
        for fromi in range(3):
            if toi==fromi:
                continue
            s = max(s, dp[i-1][fromi] + ABC[i][toi])
        dp[i][toi] = s


print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    dp = collections.defaultdict(int)

    for i,x in enumerate([a,b,c]):
        dp[0,i] = x[0]

    for i,abc in itertools.islice(enumerate(zip(a,b,c)),1,None):
        for p,q in ((p,q) for p in range(3) for q in range(3) if p != q):
            dp[i,p] = max(dp[i,p], dp[i-1,q] + abc[p])

    print(max([dp[N-1,c] for c in range(3)]))


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = [[0]*3 for i in range(n)]

for i in range(n):
  if i == 0:
    ans[0][0] = l[0][0]
    ans[0][1] = l[0][1]
    ans[0][2] = l[0][2]
  if i > 0:
    for j in range(0,3):
      a = j - 1
      b = j + 1
      if b > 2:
        b = 0
        #print(a,b)
      ans[i][j] = max(ans[i-1][a] + l[i][j], ans[i-1][b] + l[i][j])

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

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)]
dp[0] = abc[0]

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

Submission status: Accepted

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

N=II()
LIS=[LI() for i in range(N)]
DP = [[0,0,0] for i in range(N+1)]
for i, li in enumerate(LIS):
    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]+li[k])


print(max(DP[N]))

Submission status: Accepted

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

dpA = [0]*(N+1)
dpB = [0]*(N+1)
dpC = [0]*(N+1)

for i in range(N):
    a, b, c = table[i]
    dpA[i+1] = max(dpB[i], dpC[i]) + a
    dpB[i+1] = max(dpC[i], dpA[i]) + b
    dpC[i+1] = max(dpA[i], dpB[i]) + c

print(max(dpA[N], dpB[N], dpC[N]))

Submission status: Accepted

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