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:
"""
https://atcoder.jp/contests/dp/tasks/dp_c
"""
import sys

N = int(sys.stdin.readline())
input_arr = []
for i in range(N):
    input_arr.append([int(i) for i in sys.stdin.readline().split(" ")])

def getMaxPoints():
    dp = []
    dp.append([
        max(input_arr[0][1], input_arr[0][2]),
        max(input_arr[0][0], input_arr[0][2]),
        max(input_arr[0][0], input_arr[0][1]),
    ])
    for i in range(1, N):
        dp.append(
            [
                input_arr[i][0] + max(dp[i-1][1], dp[i-1][2]),
                input_arr[i][1] + max(dp[i-1][0], dp[i-1][2]),
                input_arr[i][2] + max(dp[i-1][0], dp[i-1][1]),
            ]
        )
        
    return max(dp[-1])
sys.stdout.write(str(getMaxPoints()))

Submission status: Accepted

Solution code:
N = int(input())

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

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
a = np.zeros((N,3))
for i in range(N):
    a[i][0],a[i][1],a[i][2] = map(int,input().split())

memo = np.zeros((N,3))

memo[0][0], memo[0][1], memo[0][2] = a[0][0],a[0][1],a[0][2]
day = 1

while (day < N):
    memo[day] = [max(memo[day-1][(x+1)%3],memo[day-1][(x+2)%3]) + a[day][x] \
                   for x in [0,1,2]]
    day += 1

print(int(max(memo[day - 1])))

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = np.zeros((n, 3))
for i in range(n):
    a[i][0], a[i][1], a[i][2] = map(int, input().split())
ans = 0
memo = np.zeros((n + 1, 3))
for i in range(1, n + 1):
    for j in range(3):
        for k in range(3):
            if (j == k):
                continue
            memo[i][j] = max(memo[i][j], memo[i - 1][k] + a[i-1][j])

print(int(max(memo[n])))

Submission status: Accepted

Solution code:
n = int(input())

all_days = []
for _ in range(n):
  day = input()
  day = day.split()
  for i in range(len(day)):
    day[i] = int(day[i])
  all_days.append(day)
  
def vacation(arr):
    dp = [[0,1,2] for i in range(len(arr))]
    dp[0][0] = arr[0][0]
    dp[0][1] = arr[0][1]
    dp[0][2] = arr[0][2]
    
    for i in range(1, len(arr)):
        dp[i][0] = arr[i][0] + max(dp[i-1][1], dp[i-1][2])
        dp[i][1] = arr[i][1] + max(dp[i-1][0], dp[i-1][2])
        dp[i][2] = arr[i][2] + max(dp[i-1][1], dp[i-1][0])
    
    return max(max(dp[-1][0], dp[-1][1]), dp[-1][2])
  
print(vacation(all_days))

Submission status: Accepted

Solution code:
n=int(input())
arr=[]
res=[]
for i in range(n):
    inp = list(map(int,input().split()))
    arr.append(inp)
res.append(arr[0][0])
res.append(arr[0][1])
res.append(arr[0][2])
for i in range(1,len(arr)):
    x=[-1,-1,-1]
    x[0]=max(res[1],res[2])+arr[i][0]
    x[1]=max(res[0],res[2])+arr[i][1]
    x[2]=max(res[0],res[1])+arr[i][2]
    res=x
print (max(res))

Submission status: Accepted

Solution code:
n = int(input())
prev_dp=[0]*3
for _ in range(n):
    arr=[]
    a,b,c = list(map(int,input().split()))
    arr.append((a,b,c))
    curr_dp = [0]*3
    for i in range(3):
        for j in range(3):
            if i!=j:
                #print(i,j)
                curr_dp[j] = max(curr_dp[j],prev_dp[i] + arr[0][j])
    prev_dp = curr_dp
print(max(prev_dp[0],prev_dp[1],prev_dp[2]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
a = np.zeros((N,3))
for i in range(N):
  a[i][0],a[i][1],a[i][2] = map(int,input().split())

ans = 0

# dpテーブル
dp = np.zeros((N+1,3))

for i in range(N):
  for x in range(3):
    for y in range(3):
      if x == y:
        continue
      dp[i+1][y] = max(dp[i+1][y],dp[i][x]+a[i][y])


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

Submission status: Accepted

Solution code:
import math
from functools import lru_cache
def Frog1():
    n = int(input())
    h = list(map(int,input().split(' ')))
    @lru_cache(None)
    def Solve(i):
        if i==n-1:
            return 0
        if i==n-2:
            return abs(h[i]-h[i+1])
        return min(Solve(i+1)+abs(h[i]-h[i+1]),Solve(i+2)+abs(h[i]-h[i+2]))
    dp = [0]*n
    for i in reversed(range(n)):
        if i==n-1:
            dp[i] = 0
        elif i==n-2:
            dp[i] = abs(h[i]-h[i+1])
        else:
            dp[i] = min(dp[i+1]+abs(h[i]-h[i+1]),dp[i+2]+abs(h[i]-h[i+2]))
    print(dp[0])
def Frog2():
    n,k = input().split(' ')
    n,k = int(n),int(k)
    h = list(map(int, input().split(' ')))
    @lru_cache(None)
    def Solve(i):
        if i==n-1:
            return 0
        ans = math.inf
        for j in range(1,k+1):
            new_i = i+j
            if new_i<=n-1:
                ans = min(ans , Solve(new_i)+abs(h[i]-h[new_i]))
            else:
                break
        return ans

    dp = [0]*n
    for i in reversed(range(n)):
        if i==n-1:
            dp[i] = 0
        else:
            ans = math.inf
            for j in range(1,k+1):
                new_i = i+j
                if new_i<=n-1:
                    ans = min(ans,dp[new_i]+abs(h[i]-h[new_i]))
                else:
                    break
            dp[i] = ans
    print(dp[0])

def Vacation():
    n = int(input())
    gain = []
    for i in range(n):
        a = list(map(int,input().split(' ')))
        gain.append(a)
    @lru_cache(None)
    def Solve(i,prevj):
        if i==n:
            return 0
        ans = -math.inf
        m = list({0,1,2} - {prevj})
        for j in m:
            ans = max(ans,Solve(i+1,j)+gain[i][j])
        return ans

    dp = [[0 for j in range(3)] for i in range(n+1)]
    for i in reversed(range(n+1)):
        for prevj in range(3):
            if i!=n:
                ans = -math.inf
                m = m = list({0,1,2} - {prevj})
                for j in m:
                    ans = max(ans,dp[i+1][j]+gain[i][j])
                dp[i][prevj] = ans
    print(max(dp[0]))
Vacation()

Submission status: Accepted

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

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


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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    dp = [[0] * 3 for _ in range(N)]
    dp[0] = abc[0]
    for i, (a, b, c) in enumerate(abc[1:], start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        dp_i[0] = max(dp_im[1], dp_im[2]) + a
        dp_i[1] = max(dp_im[0], dp_im[2]) + b
        dp_i[2] = max(dp_im[0], dp_im[1]) + c

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    dp = [[0] * 3 for _ in range(N)]
    dp[0] = abc[0]
    for i, (a, b, c) in enumerate(abc[1:], start=1):
        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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    dp = [[0] * 3 for _ in range(N)]
    dp[0] = abc[0]
    for i, (a, b, c) in enumerate(abc[1:], start=1):
        dp_im = dp[i - 1]
        dp[i][0] = max(dp_im[1], dp_im[2]) + a
        dp[i][1] = max(dp_im[0], dp_im[2]) + b
        dp[i][2] = max(dp_im[0], dp_im[1]) + c

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())

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

dpa=[a[0]]+[None]*(n-1)
dpb=[b[0]]+[None]*(n-1)
dpc=[c[0]]+[None]*(n-1)

for i in range(1,n):
    dpa[i]=a[i]+max(dpb[i-1],dpc[i-1])
    dpb[i]=b[i]+max(dpa[i-1],dpc[i-1])
    dpc[i]=c[i]+max(dpa[i-1],dpb[i-1])

print(max(dpa[-1],dpb[-1],dpc[-1]))

Submission status: Accepted

Solution code:
import functools
import threading
import sys


def main():
    @functools.lru_cache(maxsize=None)
    def _solve(n, action):
        if n == 1:
            return Utility[1][action]
        else:
            return max(
                _solve(n - 1, a) + Utility[n][action] for a in range(3) if a != action
            )

    def solve(n):
        return max(_solve(n, a) for a in range(3))

    N = int(input())
    Utility = [[None, None, None]]
    for i in range(N):
        Utility.append([int(x) for x in input().split(" ")])
    print(solve(N))


if __name__ == "__main__":

    sys.setrecursionlimit(1024 * 1024 * 2)
    threading.stack_size(128 * 1024 * 1024 * 2)
    threading.Thread(target=main).start()

Submission status: Accepted

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

for i in range(1, N + 1):
    ipt = list(map(int, input().split()))
    for j in range(3):
        if j != 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][0] + ipt[j])
        if j != 1:
            dp[i][j] = max(dp[i][j], dp[i - 1][1] + ipt[j])
        if j != 2:
            dp[i][j] = max(dp[i][j], dp[i - 1][2] + ipt[j])

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

Submission status: Accepted

Solution code:
def readinput():
    n=int(input())
    a=[]
    b=[]
    c=[]
    for _ in range(n):
        aa,bb,cc=list(map(int,input().split()))
        a.append(aa)
        b.append(bb)
        c.append(cc)
    return n,a,b,c

def main(n,a,b,c):
    dp=[]
    dp.append([0]*n)
    dp.append([0]*n)
    dp.append([0]*n)

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

if __name__=='__main__':
    n,a,b,c=readinput()
    ans=main(n,a,b,c)
    print(ans)

Submission status: Accepted

Solution code:
N=int(input())
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S = [[0 for j in range(3)] for i in range(100010)]

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

for i in range(N):
    A,B,C=map(int,input().split())
    S[i+1][0]=A
    S[i+1][1]=B
    S[i+1][2]=C

DP=[[0 for j in range(3)] for i in range(100010)]

DP[0][0]=0
DP[0][1]=0
DP[0][2]=0
DP[1][0]=S[1][0]
DP[1][1]=S[1][1]
DP[1][2]=S[1][2]

if N==1:
    print(max(DP[1]))
    exit()

for k in range(2,N+1):
    for i in range(3):
        for j in range(3):
            if i!=j:
                DP[k][i]=chmax(DP[k-1][j]+S[k][i],DP[k][i])
                DP[k][j]=chmax(DP[k-1][i]+S[k][j],DP[k][j])
print(max(DP[N]))

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] = map(int, input().split())

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

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

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

Submission status: Accepted

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

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

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


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

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

Submission status: Accepted

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
import numpy as np
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 = np.zeros((3, n+1), dtype=np.int)
for i in range(1, n+1):
    dp[0, i] = max(dp[1,i-1]+b[i-1], dp[2,i-1]+c[i-1])
    dp[1, i] = max(dp[0,i-1]+a[i-1], dp[2,i-1]+c[i-1])
    dp[2, i] = max(dp[0,i-1]+a[i-1], dp[1,i-1]+b[i-1])
print(max(dp[:, n]))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
class Data:
    def __init__(self,n):
        self.n = n
        self.abc = []
        self.dp = [[0,0,0]]

    def input_abc(self):
        for i in range(self.n):
            self.abc.append(list(map(int,input().split())))
    
    def chmax(self,i,j,k):
        a = self.dp[i-1][j] + self.abc[i-1][k]
        b = self.dp[i][k]
        if (a>b):
            self.dp[i][k] = a
        #print("j",j,"k",k,a,b,"\n",self.dp)
def main():
    n = int(input())
    data = Data(n)
    data.input_abc()
    for i in range(1,n+1):
        data.dp.append([0,0,0])
        for j in range(3):
            for k in range(3):
                if j != k:
                    data.chmax(i,j,k)
    print(max(data.dp[i]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# Vacation
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N)]
dp_a, dp_b, dp_c = [0 for _ in range(N)], [0 for _ in range(N)], [0 for _ in range(N)]
dp_a[0], dp_b[0], dp_c[0] = abc[0][0], abc[0][1], abc[0][2]
for i in range(1, N):
    a, b, c = abc[i]
    dp_a[i] = max(dp_b[i-1] + a, dp_c[i-1] + a)
    dp_b[i] = max(dp_a[i-1] + b, dp_c[i-1] + b)
    dp_c[i] = max(dp_a[i-1] + c, dp_b[i-1] + c)
print(max(dp_a[-1], dp_b[-1], dp_c[-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

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

for i in range(N):
    a = list(map(int,input().split()))
    for j in range(3):
        table[i][j] = a[j]


dp = [[0]*3 for i 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] + table[i][k])

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

Submission status: Accepted

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

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve(N, scores):
    last_score = scores[0]
    for i in range(1, N):
        next_score = [
            max(last_score[1], last_score[2]) + scores[i][0],
            max(last_score[2], last_score[0]) + scores[i][1],
            max(last_score[0], last_score[1]) + scores[i][2],
        ]
        last_score = next_score
    return max(last_score)


T1 = """
3
10 40 70
20 50 80
30 60 90
"""


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


def _test():
    """
    >>> as_input(T1)
    >>> main()
    210
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

dp = [[0]*3 for i 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(dp)
print(max(dp[-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 = max(y, z)+a, max(z, x)+b, max(x, y)+c
print(max(x, y, z))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def solve(a,lvl,prev,dp):
    if (prev,lvl) in dp: return dp[(prev,lvl)]
    if lvl==len(a)-1:
        if prev==0: return max(a[-1][1],a[-1][2])
        if prev==1: return max(a[-1][0],a[-1][2])
        if prev==2: return max(a[-1][0],a[-1][1])
    if prev==-1:
        p=a[0][0]+solve(a,lvl+1,0,dp)
        q=a[0][1]+solve(a,lvl+1,1,dp)
        r=a[0][2]+solve(a,lvl+1,2,dp)
        return max(p,q,r)
    dp[(prev,lvl)]=max(a[lvl][(prev+1)%3]+solve(a,lvl+1,(prev+1)%3,dp),a[lvl][(prev-1)%3]+solve(a,lvl+1,(prev-1)%3,dp))
    return dp[(prev,lvl)]
if __name__=='__main__':
    n=int(input())
    a=[]
    for i in range(n):
        a.append([int(i) for i in input().split()])
    if n==1:
        print(max(a[0]))
    else:
        print(solve(a,0,-1,{}))

Submission status: Accepted

Solution code:
n = int(input())
a = [0 for i in range(n)]
b = [0 for i in range(n)]
c = [0 for i in range(n)]

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

for t in range(n):
    x = input().split()
    a[t] = int(x[0])
    dp[t][0] = a[t]
    b[t] = int(x[1])
    dp[t][1] = b[t]
    c[t] = int(x[2])
    dp[t][2] = c[t]

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

ans = 0

if a and b and c:
    #dp[0][0] = a[0]
    #dp[0][1] = b[0]
    #dp[0][2] = c[0]
    #print(dp)

    for k in range(1,n):
        for x in range(3):
            dp[k][x] = max(dp[k-1][(x+1)%3], dp[k-1][(x+2)%3]) + dp[k][x]
    #print(dp)

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

print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=None)
def dp(i, a):
    if i == 0:
        return action[0][a]
    else:
        return max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]

import sys
sys.setrecursionlimit(1000000)
print(max([dp(n-1,a) for a in range(3)]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

memo = []
for i in range(n):
    memo.append([-1]*3)

def dp(i, a):
    if i == 0:
        return action[0][a]
    elif memo[i][a] != -1:
        return memo[i][a]
    else:
        memo[i][a] = max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]
        return memo[i][a]

print(max([dp(n-1,a) for a in range(3)]))

Submission status: Accepted

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

memo = []
for i in range(n):
    memo.append([-1]*3)

def dp(i, a):
    if i == 0:
        return action[0][a]
    elif memo[i][a] != -1:
        return memo[i][a]
    else:
        memo[i][a] = max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]
        return memo[i][a]

import sys
sys.setrecursionlimit(1000000)
print(max([dp(n-1,a) for a in range(3)]))

Submission status: Accepted

Solution code:
N = int(input())

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

dp = []
for i in range(N+1):
    dp.append([])
    for j in range(3):
        dp[i].append(0)

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

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

print(res)

#print(happy)

Submission status: Accepted

Solution code:
import sys
#import numpy as np
#from collections import defaultdict
import math
#from collections import deque

input = sys.stdin.readline



def main():


    n = int(input())

    dp = [0]*n
    dp[0] = list(map(int,input().split()))

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#dp[i][j]:i日目に活動j:0,1,2:A,B,Cをするときの幸福度の最大値

N = int(input())
abc = [list(map(int,input().split())) for i in range(N)]#abc:012

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

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

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

Submission status: Accepted

Solution code:
II = lambda: int(input())
SI = lambda: input()
LI = lambda: list(map(int,input().split()))
MI = lambda: map(int,input().split())
n = II()
d = [[0,0,0] for i in range(n)]
for i in range(n):
	a,b,c = MI()
	if i == 0:
		d[0][0] = a
		d[0][1] = b
		d[0][2] = c
	else:
		d[i][0] = max(d[i-1][1],d[i-1][2])+a
		d[i][1] = max(d[i-1][0],d[i-1][2])+b
		d[i][2] = max(d[i-1][1],d[i-1][0])+c
print(max(d[-1]))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

happiness[0] = day[0]

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

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

Submission status: Accepted

Solution code:
n = int(input())
li = [-1]*n

for i in range(n):
    li[i] = [int(w) for w in input().split()]

dp = [[-1] * 3 for i in range(n)]
dp[0][0] = li[0][0]
dp[0][1] = li[0][1]
dp[0][2] = li[0][2]


for i in range(1, n):
    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] + li[i][j])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

N = int(input())
a, b, c = [], [], []
dp = [[0] * 3 for _ in range(N+1)]

for i in range(N):
    v1, v2, v3 = map(int, input().split())
    a.append(v1)
    b.append(v2)
    c.append(v3)

def solve(idx, prev):
    if dp[idx][prev] > 0:
        return dp[idx][prev]

    if idx == N:
        dp[idx][prev] = 0
    elif idx == 0:
        v1 = solve(idx + 1, 0) + a[idx]
        v2 = solve(idx + 1, 1) + b[idx]
        v3 = solve(idx + 1, 2) + c[idx]
        dp[idx][prev] = max(v1, v2, v3)

    # Prev was A
    elif prev == 0:
        # Select B
        a1 = solve(idx + 1, 1) + b[idx]
        # Select C
        a2 = solve(idx + 1, 2) + c[idx]
        dp[idx][prev] = max(a1, a2)

    # Prev was B
    elif prev == 1:
        # Select A
        b1 = solve(idx + 1, 0) + a[idx]
        # Select C
        b2 = solve(idx + 1, 2) + c[idx]
        dp[idx][prev] = max(b1, b2)

    # Prev was B
    elif prev == 2:
        # Select A
        c1 = solve(idx + 1, 0) + a[idx]
        # Select B
        c2 = solve(idx + 1, 1) + b[idx]
        dp[idx][prev] = max(c1, c2)

    return dp[idx][prev]

print(solve(0, 0))

Submission status: Accepted

Solution code:
n = int(input())

felicidade = []

for x in range(n):
    felicidade.append(list(map(int,input().split())))

dp = []

dp.append([felicidade[0][0],felicidade[0][1],felicidade[0][2]])

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


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


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

Submission status: Accepted

Solution code:
n = int(input())

felicidade = []

for x in range(n):
    felicidade.append(list(map(int,input().split())))

DP = [0,0,0]

if n == 1:
    print(max(felicidade[0]))

else:

    for x in range(3):
        DP[x] = felicidade[0][x]


    for dia in range(1,n):
        m = [0] * 3
        for x  in range(3):#As duas possíveis escolhas são x e y
            for y  in range(3):
                if x != y: #Se elas forem diferentes
                    m[x] = max(m[x], DP[y] + felicidade[dia][x])
        DP = m
    
    print(max(DP))

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n = inp()
dp = [[0]*3 for i in range(n)]
a,b,c = [],[],[]
for _ in range(n):
    aa,bb,cc = ip()
    a.append(aa)
    b.append(bb)
    c.append(cc)
dp[0] = [a[0],b[0],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())
abc=[[-1,-1,-1,-1]]

for i in range(n):
  a,b,c=map(int,input().split())
  abc.append([-1,a,b,c])
dp=[[0 for i in range(4)] for j in range(n+1)]

for i in range(1,n+1):
  for j in range(1,4):
    for k in range(1,4):
      if j==k:
        continue
      dp[i][k]=max(dp[i][k],dp[i-1][j]+abc[i][k])
ans=max(dp[n])
print(ans)

Submission status: Accepted

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

dp = [[0] * 3 for i in range(n + 1)]
for i in range(n):
    for j in range(3):
        for k in range(3):
            if j != k:
                dp[i + 1][j] = max(dp[i][k] + value[i][j], dp[i + 1][j])
print(max(dp[n]))

Submission status: Accepted

Solution code:
#C
n=int(input())
inf=float("inf")
dp=[[-inf for i in range(3)] for j in range(n+1)]
dp[0][0]=0
dp[0][1]=0
dp[0][2]=0
for i in range(n):
    x=list(map(int,input().split()))
    for j in range(3):
        cst_list=[]
        for k in range(3):
            if j!=k:
                cst_list.append(dp[i][k]+x[j])
        dp[i+1][j]=max(cst_list)
print(max(dp[n]))

Submission status: Accepted

Solution code:
n = int(input())
x = []
for i in range(n):
    l = list(map(int, input().split()))
    x.append(l)
count = 0
dp = [[0 for j in range(3)] for i in range(n)]
dp[0][0], dp[0][1], dp[0][2] = x[0][0], x[0][1], x[0][2]

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


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