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())
dp = [[0,0,0]]*n
a,b,c = map(int, input().split())
dp[0]=[a,b,c]

for i in range(1,n):
    abc = list(map(int, input().split()))
    #dp[i][0]=abc[0]+max(dp[i-1][1], dp[i-1][2])
    #dp[i][1]=abc[1]+max(dp[i-1][2], dp[i-1][0])
    #dp[i][2]=abc[2]+max(dp[i-1][0], dp[i-1][1])
    dp0= abc[0]+max(dp[i-1][1], dp[i-1][2])
    dp1= abc[1]+max(dp[i-1][2], dp[i-1][0])
    dp2= abc[2]+max(dp[i-1][0], dp[i-1][1])
    dp[i]=[dp0,dp1,dp2]
ans = dp[-1]
print(max(ans))

Submission status: Accepted

Solution code:
n = int(input())
dp = [[0,0,0]]*n
a,b,c = map(int, input().split())
dp[0]=[a,b,c]
for i in range(1,n):
    abc = list(map(int, input().split()))
    dp0= abc[0]+max(dp[i-1][1], dp[i-1][2])
    dp1= abc[1]+max(dp[i-1][2], dp[i-1][0])
    dp2= abc[2]+max(dp[i-1][0], dp[i-1][1])
    dp[i]=[dp0,dp1,dp2]
ans = dp[-1]
print(max(ans))

Submission status: Accepted

Solution code:
INF = 1000000
n = int(input())
t = [[int(i) for i in input().split()] for j in range(n)]
dp = [[-INF for i in range(3)] for j in range(n)]
for j in range(3):
    dp[0][j] = t[0][j]
a = [0, 1, 2]

for i in range(1, n):
    for j in range(3):
        k = list(set(a).difference(set([j])))
        dp[i][j] = max(dp[i - 1][k[0]], dp[i - 1][k[1]]) + t[i][j]

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

Submission status: Accepted

Solution code:
N=int(input())
dp=[0,0,0]
#dp=[]
for i in range(0,N):
    new_dp=[]
    for i in range(0,3):
        new_dp.append(0)
    costs=[int(j) for j in input().split()]
    for k in range(0,3):
        for j in range(0,3):
            if(k!=j):
                new_dp[j]=max(new_dp[j],dp[k]+costs[j])
    dp=new_dp
print(max(dp[0],dp[1],dp[2]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# atcoder https://atcoder.jp/contests/dp/tasks/dp_c

N = int(input())
a, b, c = [], [], []
for _ in range(N):
    ai, bi, ci = map(int, input().split())
    a.append(ai); b.append(bi); c.append(ci)


dp = [[0] * N for _ in range(3)] #dp[h][i]: i日目にhを行った場合の最大幸福度
dp[0][0], dp[1][0], dp[2][0]  = a[0], b[0], c[0]

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

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

Submission status: Accepted

Solution code:
N = int(input())

A = [0 for _ in range(N)]
B = [0 for _ in range(N)]
C = [0 for _ in range(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][2], dp[i - 1][0]) + 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:
def run():
  N = int(input())
  abc_li = [[int(i) for i in input().split()] for n in range(N)]
  dp = [[0]*3 for n in range(N)]
  dp[0] = abc_li[0]
  for n in range(1, N):
    for next_abc in range(3):
      for pre_abc in range(3):
        if pre_abc == next_abc: continue
        dp[n][next_abc] = max(dp[n][next_abc], dp[n-1][pre_abc]+abc_li[n][next_abc])
  print(max(dp[N-1]))
  
if __name__ == '__main__':
  run()

Submission status: Accepted

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

# dp[i][j] i日の時に行動jを起こす状況における最大幸福
dp = [[0]*3 for i in range(N)]
dp[0][0] = abc[0][0]
dp[0][1] = abc[0][1]
dp[0][2] = abc[0][2]

for i in range(N-1):
    for j in range(3):
        actions = list(set([0, 1, 2]) - set([j]))
        dp[i+1][j] = max(list(map(lambda x: abc[i+1][j]+dp[i][x], actions)))

print(max(dp[-1]))

Submission status: Accepted

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

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

if n == 1:
    ans = min(dp[0])
else:
    for i in range(1,n):
        for j in range(3):
            dp[i][j] = max([ dp[i-1][k] for k in ls[j] ]) + abc[i][j]

print(max(dp[-1]))

Submission status: Accepted

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


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

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

Submission status: Accepted

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

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

for i in range(0, 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] + actions[i][k])

print(max(dp[n]))

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
data = []
for _ in range(N):
    a,b,c = [int(x) for x in stdin.readline().rstrip().split()]
    data.append((a,b,c))

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = [[0 for i in range(3)] for i in range(n)]
dp = [[0 for i in range(3)] for i in range(n+1)]
for i in range(n):
    a[i] = list(map(int, input().split()))

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

print(max(dp[n]))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def solve(n, a, b, c): 
    dp = [[0,0,0] for i in range(n)]
    v = [[a[i], b[i], c[i]] for i in range(n)]
    for i in range(3):
        dp[-1][i] = v[-1][i]
    for i in range(n-2, -1, -1):
        for j in range(3):
            for k in range(3):
                if j != k:
                    dp[i][j] = max(dp[i][j], dp[i+1][k] + v[i][j])
    return max(dp[0])

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())
print(solve(n, a, b, c))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import fractions
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
a = []
b = []
c = []
for i in range(n):
    a1, b1, c1 = MAP()
    a.append(a1)
    b.append(b1)
    c.append(c1)

dp0 = [0]*3
dp1 = [0]*3
dps = [dp0, dp1]
dp = [0]*n
abc = [a, b, c]

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

dp[0] = max(dps[0])

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

print(dp[n-1])

Submission status: Accepted

Solution code:
n = int(input())
a, b, c = map(int, input().split())

for i in range(n-1):
    ai, bi, ci = map(int, input().split())
    ai += max(b, c)
    bi += max(a, c)
    ci += max(a, b)
    a, b, c = ai, bi, ci

print(max(a, b, c))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [{"a":0,"b":0,"c":0} for _ in range(n+1)]

for i in range(n):
    a, b, c = map(int,input().split())
    dp[i+1]["a"] = max(dp[i]["b"],dp[i]["c"]) + a
    dp[i+1]["b"] = max(dp[i]["a"],dp[i]["c"]) + b
    dp[i+1]["c"] = max(dp[i]["a"],dp[i]["b"]) + c
print(max(dp[n].values()))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
INF = float('inf')


N = int(input())
dp = [[] for _ in range(N)]

for i in range(N):
    dp[i] = inpl()

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


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

Submission status: Accepted

Solution code:
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n = INT()
a = [MAP() for _ in range(n)]
dp = [[0,0,0] for _ in range(n+1)]

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
n=int(input())
a=[]
b=[]
c=[]
for i in range(n):
	x,y,z=map(int,input().split())
	a.append(x)
	b.append(y)
	c.append(z)
dp=[[a[0],b[0],c[0]]]
for i in range(n-1):
	x=a[i+1]+max(dp[i][1],dp[i][2])
	y=b[i+1]+max(dp[i][0],dp[i][2])
	z=c[i+1]+max(dp[i][0],dp[i][1])
	dp.append([x,y,z])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())

dp = [[0 for _ in range(3)] for _ in range(N+1)]
#dp[i][j]:i日目に活動a~cを行ったときに得られる最高の累積幸福度

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

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

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())

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
dp = [[0]*3 for i in range(100100)]

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

print(max(dp[N]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#DP C
n=int(input())
data=[list(map(int,input().split())) for _ in range(n)]
fa=[data[0][0]]
fb=[data[0][1]]
fc=[data[0][2]]
for i in range(1,n):
    fa.append(max(fb[i-1],fc[i-1])+data[i][0])
    fb.append(max(fa[i-1],fc[i-1])+data[i][1])
    fc.append(max(fb[i-1],fa[i-1])+data[i][2])
print(max(fa[-1],fb[-1],fc[-1]))

Submission status: Accepted

Solution code:
n=int(input())
al=[0]*n
bl=[0]*n
cl=[0]*n
for i in range(n):
    a,b,c=map(int,input().split())
    if i==0:
        al[0]=a;bl[0]=b;cl[0]=c
    else:
        al[i]=max(bl[i-1],cl[i-1])+a
        bl[i]=max(al[i-1],cl[i-1])+b
        cl[i]=max(al[i-1],bl[i-1])+c
print(max(al[-1],bl[-1],cl[-1]))

Submission status: Accepted

Solution code:
n = int(input())

hap = [[0] for i in range(n)]
for i in range(n):
  hap[i] = [int(i) for i in input().split()]
  
dp = [[0]*3 for i in range(n)]
for i in range(3):
  dp[0][i] = hap[0][i]
  
for i in range(1, n):
  for j in range(3):
    dp[i][j] = max(dp[i-1][(j+1)%3]+hap[i][j], dp[i-1][(j+2)%3]+hap[i][j])
print(max(dp[n-1]))

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

Submission status: Accepted

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


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    dp = [[0 for _ in range(3)] for _ in range(N)]

    H = list(zip(a,b,c))

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

    print(max(dp[-1]))


    return


# Generated by 1.1.5 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, *abc = map(int, open(0).read().split())
plan = list(zip(*[iter(abc)]*3))
profit = [[0]*3 for _ in range(N)]
profit[0] = [p for p in plan[0]]
# ２つの遷移元から来たときの最大幸福値を求めていく
for day in range(1, N):
    # 次の行動 0=A 1=B 2=C
    for n_plan in range(3):
        max_plofit = max([pr + plan[day][n_plan]
            if n_plan != i
            else 0
            for i, pr in enumerate(profit[day-1])])
        profit[day][n_plan] = max_plofit      
print(max(profit[N-1]))

Submission status: Accepted

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

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

for i in range(1,n):
  for j in range(3):
    s = 0 
    for k in range(3):
      s = max(s,(dp[i-1][k]+Act[i][j])*int(j!=k))
    dp[i][j] = s

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
ary = [list(map(int,input().split())) for _ in range(n)]
ary = np.array(ary)
dp = np.zeros((n,3))
dp[0] = ary[0]
for i in range(n-1):
    for j in range(3):
        for k in range(3):
            if k == j:continue
            check = dp[i][j] + ary[i+1][k]
            if check > dp[i+1][k]:
                dp[i+1][k] = check
print(int(max(dp[n-1])))

Submission status: Accepted

Solution code:
n=int(input())

a=0
b=0
c=0

for _ in range(n):
  aa,bb,cc=map(int,input().split())
  
  a1=max(b,c)+aa
  b1=max(a,c)+bb
  c1=max(b,a)+cc
  a=a1
  b=b1
  c=c1
  #print(a,b,c)
  
print(max(a,b,c))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def vacation():
    N = int(input())
    d = list(input().split() for _ in range(N))

    happiness=list()

    if N==1:
        return max(d[0])

    for i in range(N):
        day = list()
        if i == 0:
            for c in range(3):
                day.append(int(d[0][c]))
        else:
            for c in range(3):
                tmp = list()
                for bc in range(3):
                    if c != bc:
                        tmp.append(int(happiness[i-1][bc])+int(d[i][c]))
                day.append(max(tmp))

        happiness.append(day)
    return max(happiness[-1])


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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
n = int(sys.stdin.readline())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#print(L)

dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0] = L[0].copy()

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

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(3)] for _ in range(N+1) ]

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
dp = [[0, 0, 0] for i in range(N+1)]
A = [[0, 0, 0] for i in range(N+1)]
for i in range(N):
    a, b, c = [int(_) for _ in stdin.readline().rstrip().split()]
    A[i][0], A[i][1], A[i][2] = a, b, c 

for i in range(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]+A[i][j])
print(max(dp[N-1]))

Submission status: Accepted

Solution code:
N = int(input())

dp = [[0]*3 for i in range(N+1)]
A = [list(map(int, input().split())) for i in range(N)]

for i in range(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]+A[i][j])

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

Submission status: Accepted

Solution code:
N = int(input())

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

for i in range(1, N+1):
  acitivities = list(map(int, input().split()))
  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]+acitivities[j])

print(max(dp[N]))

Submission status: Accepted

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

dp = [[None, None, None] for _ in range(N)]
# dp[0][0]はAを選んだ時
dp[0] = [Data[0][0], Data[0][1], Data[0][2]]

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())

A = [0] * (N+1)
B = [0] * (N+1)
C = [0] * (N+1)

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    v = [a, b, c]
    dp = [[0] * 3 for _ in range(N + 1)]
    dp[1] = [a[0], b[0], c[0]]
    for i in range(1, N):
        for j in range(3):
            for k in [1, 2]:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][(j + k) % 3] + v[j][i])
    print(max(dp[N]))
    return


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

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

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
import copy
N = int(input())
dp = [0]*3
for _ in range(N):
  tmp = [int(n) for n in input().split()]
  tmp_dp = copy.deepcopy(dp)
  tmp_dp[0] = max(dp[1],dp[2]) + tmp[0]
  tmp_dp[1] = max(dp[0],dp[2]) + tmp[1]
  tmp_dp[2] = max(dp[0],dp[1]) + tmp[2]
  dp = tmp_dp
print(max(dp))

Submission status: Accepted

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

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

for i in range(1, N):
    dp.append([0, 0, 0])
    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][1], dp[i-1][0]) + c[i]
    
print(max(dp[N-1]))

Submission status: Accepted

Solution code:
# DP(配るDP)
N = int(input())

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

Submission status: Accepted

Solution code:
# DP(貰うDP)
N = int(input())

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = []
b = []
c = []
for _ in range(N):
    a_val , b_val , c_val = map(int , input().split())
    a.append(a_val)
    b.append(b_val)
    c.append(c_val)

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

Submission status: Accepted

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

i=n-2
while i>-1:
	a[i]+=max(b[i+1],c[i+1])
	b[i]+=max(a[i+1],c[i+1])
	c[i]+=max(b[i+1],a[i+1])
	i=i-1
print(max([a[0],b[0],c[0]]))

Submission status: Accepted

Solution code:
n = int(input())
li = []
while True:
    try:
        li.append(list(map(int,input().split())))
    except:
        break

f_inf = float('inf')
dpa=[li[0][0]]+[0]*(n-1)
dpb=[li[0][1]]+[0]*(n-1)
dpc=[li[0][2]]+[0]*(n-1)

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

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

Submission status: Accepted

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

INF = float('inf')
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)]

dpa = [abc[0][0]]+[0]*(n-1)
dpb = [abc[0][1]]+[0]*(n-1)
dpc = [abc[0][2]]+[0]*(n-1)

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

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

Submission status: Accepted

Solution code:
class Solver(object):
    def __init__(self, N, happy):
        self.dp = [[99999999 for _ in range(3)] for _ in range(N)]
        self.N = N
        self.happy = happy

    def solve(self):
        happy_list = self.happy
        self.dp[0] = happy_list[0]
        for i in range(1, self.N):
            self.dp[i][0] = max(happy_list[i][0] + self.dp[i-1][1],
                                happy_list[i][0] + self.dp[i-1][2])
            self.dp[i][1] = max(happy_list[i][1] + self.dp[i-1][0],
                                happy_list[i][1] + self.dp[i-1][2])
            self.dp[i][2] = max(happy_list[i][2] + self.dp[i-1][0],
                                happy_list[i][2] + self.dp[i - 1][1])
        return max(self.dp[-1])


def main():
    N = int(input())
    happy = [[int(i) for i in input().split()] for _ in range(N)]
    solver = Solver(N, happy)
    print(solver.solve())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
n = int(sys.stdin.readline())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

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

p[0] = L[0].copy()
#print(p)
#print(L)

for d in range(1, n):
    for i in range(3):
        if i ==0:
            p[d][0] = max(p[d-1][1], p[d-1][2]) + L[d][0]
        elif i ==1:
            p[d][1] = max(p[d-1][0], p[d-1][2]) + L[d][1]
        elif i==2:
            p[d][2] = max(p[d-1][0], p[d-1][1]) + L[d][2]

print(max(p[-1]))

Submission status: Accepted

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
N=int(input())
li=[list(map(int,input().split())) for i in range(N)]
dp=[[0]*3 for i in range(N)]
for i in range(N):
    if i==0:
        for j in range(3):
            dp[i][j] = li[i][j]
    else:
        for j in range(3):
            if j == 0:
                dp[i][j] = li[i][0] + dp[i-1][1] if dp[i-1][1] >= dp[i-1][2] else li[i][0] + dp[i-1][2]
            if j == 1:
                dp[i][j] = li[i][1] + dp[i-1][0] if dp[i-1][0] >= dp[i-1][2] else li[i][1] + dp[i-1][2]
            if j == 2:
                dp[i][j] = li[i][2] + dp[i-1][0] if dp[i-1][0] >= dp[i-1][1] else li[i][2] + dp[i-1][1]
print(max(dp[N-1]))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

input = sys.stdin.readline


def main():
    N = int(input())
    f_inf = float('inf')
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    MAX_N = 110000
    dp = [[]] * N
    for i in range(N):
        a, b, c = map(int, input().split())
        if i == 0:
            dp[i] = [a, b, c]
        else:
            dp[i] = [max(dp[i-1][1], dp[i-1][2]) + a, max(dp[i-1][0], dp[i-1][2]) + b, max(dp[i-1][0], dp[i-1][1]) + c]
    print(max(dp[N-1]))


if __name__ == '__main__':
    main()