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

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

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


for i in range(n):
    if i == 0:
        for j in range(3):
            dp[i][j] = li[i][j]
    else:
        for j in range(3):
            for k in range(3):
                if j == k:
                    continue
                else:
                    dp[i][j] = max(dp[i-1][k] + li[i][j], dp[i][j])
                    
print(max(dp[-1]))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n=int(input())
dp=[[0]*3 for x in range(n)]
umi,yama,ie=0,1,2
for i in range(n):
    ai,bi,ci=map(int,input().split())
    if i==0:
        dp[i][umi]=ai
        dp[i][yama]=bi
        dp[i][ie]=ci
        continue
    dp[i][umi]=max(dp[i-1][yama],dp[i-1][ie])+ai
    dp[i][yama]=max(dp[i-1][umi],dp[i-1][ie])+bi
    dp[i][ie]=max(dp[i-1][umi],dp[i-1][yama])+ci
print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from numpy import cumsum


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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
abc = [LIST() for _ in range(n)]


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

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

print(max(dp[-1]))
"""for i in range(n + 1):
    print(dp[i])"""

Submission status: Accepted

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

dp = [0, 0, 0]
for n, p in enumerate(ABC):
	tdp = dp.copy()
	for i in range(3):
		for j in range(3):
			if i == j:
				continue
			tdp[i] = max(tdp[i], dp[j] + p[j])
	dp = tdp
	#print(dp)
print(max(dp))

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 + 1)]

for n, p in enumerate(ABC):
	dp[n + 1][0] = max(dp[n + 1][0], dp[n][1] + p[0], dp[n][2] + p[0])
	dp[n + 1][1] = max(dp[n + 1][1], dp[n][0] + p[1], dp[n][2] + p[1])
	dp[n + 1][2] = max(dp[n + 1][2], dp[n][0] + p[2], dp[n][1] + p[2])

#for line in dp:
#	print(*line)

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n=int(input())

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

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

N = int(input())
arr=[]
ans=[]
for i in range(N):
	arr.append(list(map(int,input().split())))
	ans.append([0,0,0])

ans[-1]=arr[-1]

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

print(max(ans[0]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
abc_l = []
for i in range(N):
    abc_l.append(list(map(int,input().split())))
DP = [[0,0,0] for i in range(N)]
for i in range(3):
    DP[0][i] = abc_l[0][i]
for i in range(1,N):
    for abc in range(3):
#        print(DP)
        copy = DP[i-1][:]
        copy.remove(DP[i-1][abc])
        DP[i][abc] = max(copy) + abc_l[i][abc]
print(max(DP[-1]))

Submission status: Accepted

Solution code:
N = int(input())
dp = [0,0,0]
for i in range(N):
    li = [int(i) for i in input().split()]
    dp = [li[0]+max(dp[1],dp[2]),li[1]+max(dp[0],dp[2]),li[2]+max(dp[0],dp[1])]
print(max(dp))

Submission status: Accepted

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

#print(N,H)

def chmax(dp, n, k, a):
	b = (dp[n][k]<a)
	if b: dp[n][k]=a
	return b


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

print( max(dp[N]) )

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
dp = np.zeros((N+1, 3))  # （i日目にa, b, cを行って）i日目までに得られる幸福度の最大値
"""
i日目にaを選んだ場合
dp[i, 0] = max(dp[i-1, 1], dp[i-1, 2]) + a
i日目にbを選んだ場合
dp[i, 1] = max(dp[i-1, 0], dp[i-1, 2]) + b
i-1日目にcを選んだ場合
dp[i, 2] = max(dp[i-1, 0], dp[i-1, 1]) + c
"""

for i in range(1, N+1):
    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(int(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] = map(int,input().split())
    
#[i] = i日目まで, i日目Aの時の最大値


memo =[[0 for i in range(N+1)] for j in range(3)]


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


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

Submission status: Accepted

Solution code:
# EduDPC - Vacation
import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().rstrip().split())) for _ in range(n)]
dp = [[0, 0, 0] for i in range(n)]
dp[0] = arr[0]
for i in range(1, n):
    dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]
    dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + arr[i][1]
    dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]
print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())

a_sum_last, b_sum_last, c_sum_last = 0, 0, 0
for _ in range(N):
    a_today, b_today, c_today = map(int, input().split())
    a_tomorrow = a_today + max(b_sum_last, c_sum_last)
    b_tomorrow = b_today + max(a_sum_last, c_sum_last)
    c_tomorrow = c_today + max(a_sum_last, b_sum_last)
    
    # Update
    a_sum_last = a_tomorrow
    b_sum_last = b_tomorrow
    c_sum_last = c_tomorrow

print(max(a_sum_last, b_sum_last, c_sum_last))

Submission status: Accepted

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

dp = [[0]*3 for i in range(N)]
dp[0] = abc[0]
for i in range(1, N):
    for j in range(3):
        for next_j in range(3):
            if j != next_j:
                dp[i][next_j] = max(dp[i][next_j], dp[i-1][j] + abc[i][next_j])

print(max(dp[-1]))

Submission status: Accepted

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

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

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j!=k:
                ans[i][k]=max(ans[i][k],ans[i-1][j]+happiness[i-1][k])

print(max(ans[N]))

Submission status: Accepted

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

Submission status: Accepted

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

ans[0][0] = abc[0][0]
ans[0][1] = abc[0][1]
ans[0][2] = abc[0][2]

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

print(max(ans[-1]))

Submission status: Accepted

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


N = int(input())
abc_list = []
for _ in range(N):
    abc_list.append([int(x) for x in input().split()])

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

print(max(dp[-1]))

Submission status: Accepted

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

for _ in range(n):
  li.append(list(map(int, input().split())))

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

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

print(max(dp[n]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from __future__ import division, print_function

def main():
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    dp = [[0 for _ in range(3)] for _ in range(n)]
    for i in range(n):
        if i == 0:
            dp[i][0] = a[i][0]
            dp[i][1] = a[i][1]
            dp[i][2] = a[i][2]
            continue
            
        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][0], dp[i - 1][1])

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


# PyPy 2 Fast IO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

# Importing Modules
import math
import collections

from collections import Counter
from math import fabs

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
activities = []
plans = ['A', 'B', 'C']
for _ in range(N):
    activities.append(tuple(map(int, input().split())))
dp = {i: {p: 0 for p in plans} for i in range(1, N+1)}
for i, p in enumerate(plans):
    dp[1][p] = activities[0][i]
for i in range(2, N+1):
    a, b, c = activities[i-1]
    dp[i]['A'] = max([dp[i-1][p] + a for p in plans if p != 'A'])
    dp[i]['B'] = max([dp[i-1][p] + b for p in plans if p != 'B'])
    dp[i]['C'] = max([dp[i-1][p] + c for p in plans if p != 'C'])
print(max([dp[N][p] for p in plans]))

Submission status: Accepted

Solution code:
n=int(input())
dp=[0,0,0]
for i in range(n):
    a=list(map(int,input().split()))
    dpn=[0,0,0]
    for j in range(3):
        
        for k in range(3):
            if(j!=k):
                dpn[k]=max(dpn[k],dp[j]+a[k])
        
    dp=dpn.copy()
    #print(dpn)
print(max(dp))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


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

    for i, (ca, cb, cc) in enumerate(zip(a, b, c)):
        dp[i + 1][0] = max(dp[i][1], dp[i][2]) + ca
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + cb
        dp[i + 1][2] = max(dp[i][0], dp[i][1]) + cc
    return max(dp[-1])


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))
    result = solve(N, a, b, c)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

n = int(input())
dp = [[-float("inf"),-float("inf"),-float("inf")] for i in range(n+1)]

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

dp[0] = [0]*3
dp[1] = a[0]

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n=int(input()) 

today_a,today_b,today_c=0,0,0
for i in range(n) : 
    a,b,c=map(int,input().split()) 
    tomorrow_a=a+max(today_b,today_c)
    tomorrow_b=b+max(today_a,today_c)
    tomorrow_c=c+max(today_a,today_b)

    today_a=tomorrow_a
    today_b=tomorrow_b
    today_c=tomorrow_c

print(max(tomorrow_a,tomorrow_b,tomorrow_c))

Submission status: Accepted

Solution code:
N = int(input())

h1, h2, h3 = [0] * N, [0] * N, [0] * N

for i in range(N):
  a, b, c = map(int, input().split())
  if i == 0:
    h1[i], h2[i], h3[i] = a, b, c
  else:
    h1[i] = a + max(h2[i-1], h3[i-1])
    h2[i] = b + max(h1[i-1], h3[i-1])
    h3[i] = c + max(h1[i-1], h2[i-1])
print(max(h1[-1], h2[-1], h3[-1]))

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):
    a=list(map(int,input().split()))
    A.append(a)
INF=10**9
dp=[[0]*3 for i in range(N+1)]#dp[i][j] i日目でjをしたときの最大の幸福度
#dp[i+1][a]:=max(dp[i][b]+a,dp[i][c]+a)
dp[0][0]=dp[0][1]=dp[0][2]=0
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][0],dp[N][1],dp[N][2]))

Submission status: Accepted

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

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

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

print(max(dp[-1]))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
ABC = [list(map(int,input().split())) for i in range(N)]

dp = [0]*(N+1)
dp[0] = [0,0,0]

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
ABC = [list(map(int,input().split())) for i in range(N)]

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

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
ABC = [list(map(int,input().split())) for i in range(N)]

dp = [[0]*3 for i 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][j] = max(dp[i-1][k]+ABC[i-1][j],dp[i][j])

print(max(dp[N]))

Submission status: Accepted

Solution code:
N = int(input())
a, b, c = [0] * N, [0] * N, [0] * N
for i in range(N):
	a[i], b[i], c[i] = map(int, input().split())
dp = [[0] * 3 for _ in range(N)]
dp[0] = [a[0], b[0], 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][0] + b[i + 1], dp[i][2] + 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:
# -*- coding: utf-8 -*-
n = int(input())
dp = [[0, 0, 0] 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] = 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 sys

N = int(input())
dpa, dpb, dpc = 0, 0, 0
for _ in range(N):
    a, b, c = map(int, sys.stdin.readline().split())
    dpa1 = a + max(dpb, dpc)
    dpb1 = b + max(dpc, dpa)
    dpc1 = c + max(dpa, dpb)
    dpa, dpb, dpc = dpa1, dpb1, dpc1 
print(max(dpa, dpb, dpc))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

ans = max(dp[N-1])

print(ans)

Submission status: Accepted

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


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    INF = 0
    dp = [[INF] * (N+1) for i in range(3)]

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

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


# 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:
from __future__ import division, print_function

def main():
    n = int(input())
    dp = [0, 0, 0]
    for _ in range(n):
        curr_dp = [0, 0, 0]
        c = [int(_) for _ in input().split()]
        for i in range(3):
            for j in range(3):
                if i != j:
                    curr_dp[j] = max(curr_dp[j], dp[i] + c[j])

        dp = curr_dp

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


# PyPy 2 Fast IO Template. Made by Pajenegod & C1729
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

# Importing Modules
import math
import collections

from collections import Counter
from math import fabs

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [[0, 0, 0] 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]+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:

import sys


def problem():
    N = int(input())
    activityList = []
    for i in range(N):
      row = list(map(int, input().split()))
      activityList.append(row)

    print(algorithm(N,activityList))

def algorithm(N, activityList):
  dp = [[0, 0, 0] for i in range(N+ 1)]

  for index in range(1, N + 1):
    for j in range(3):
      for k in range(3):
        if j == k:
          continue
        if dp[index][j] < dp[index - 1][k] + activityList[index-1][j]:
          dp[index][j] = dp[index - 1][k] + activityList[index-1][j]
      
  return max(dp[N])

problem()

Submission status: Accepted

Solution code:
N = int(input())

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

for i in range(N):
    row = input().split()
    abc = [int(n) for n in row]
    abcs.append(abc)
    if i == 0:
        dp[0][0] = abc[0]
        dp[0][1] = abc[1]
        dp[0][2] = abc[2]
    else:
        dp[i][0] = max([abc[0] + dp[i-1][1], abc[0] + dp[i-1][2]])
        dp[i][1] = max([abc[1] + dp[i-1][0], abc[1] + dp[i-1][2]])
        dp[i][2] = max([abc[2] + dp[i-1][0], abc[2] + dp[i-1][1]])

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

Submission status: Accepted

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

for i in range(N):
    for j in range(3):
        for k in range(3):
            if not j == k:
                dp[i+1][k] = max(dp[i+1][k], dp[i][j]+sel[i][k])

print(max(dp[N]))

Submission status: Accepted

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

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 = np.zeros((N, 3))
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] = A[i+1] + max(DP[i, 1], DP[i, 2])
    DP[i+1, 1] = B[i+1] + max(DP[i, 0], DP[i, 2])
    DP[i+1, 2] = C[i+1] + max(DP[i, 0], DP[i, 1])

print(int(max(DP[-1, 0], DP[-1, 1], DP[-1, 2])))

Submission status: Accepted

Solution code:
import fileinput


def chose_action_prev(current_action, last_best_rewards):
    return max((v, idx) for idx, v in enumerate(last_best_rewards) if idx != current_action)[1]


def vacation(action_values):
    last_best_rewards = [0, 0, 0]
    current_best_rewards = [0, 0, 0]

    for vals_for_day in action_values:
        for action, rev in enumerate(vals_for_day):
            prev_action = chose_action_prev(action, last_best_rewards)
            current_best_rewards[action] = last_best_rewards[prev_action] + rev

        last_best_rewards = current_best_rewards
        current_best_rewards = [0, 0, 0]

    return max(last_best_rewards)


inp = fileinput.input()
line_count = int(inp.readline())

action_vals = []
for _ in range(line_count):
    action_vals.append([int(v) for v in inp.readline().split(" ")])

print(vacation(action_vals))

Submission status: Accepted

Solution code:
# atcoder DPまとめ
# C-Vacation

def get_inputs():
    n = int(input())
    hap = []
    for _ in range(n):
        hap.append([int(x) for x in input().split()])
    
    return n, hap


if __name__ == "__main__":
    n, hap = get_inputs()
    
    dp = [[0, 0, 0] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        # i-1日にA:0の遊びをしたときの最大の幸福度を求める
        dp[i][0] = hap[i - 1][0] + max(dp[i - 1][1], dp[i - 1][2])
        # 同様にB:1の遊びをした時の最大の幸福度
        dp[i][1] = hap[i - 1][1] + max(dp[i - 1][0], dp[i - 1][2])
        # 同様にc:2の遊びをした時の最大の幸福度
        dp[i][2] = hap[i - 1][2] + max(dp[i - 1][0], dp[i - 1][1])
    
    print(max(dp[n]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - Vacation
https://atcoder.jp/contests/dp/tasks/dp_c

"""
import sys


def solve(N, acivities):
    pre_A, pre_B, pre_C = 0, 0, 0
    for a, b, c in acivities:
        aa = a + max(pre_B, pre_C)
        bb = b + max(pre_A, pre_C)
        cc = c + max(pre_A, pre_B)
        pre_A, pre_B, pre_C = aa, bb, cc
    return max(pre_A, pre_B, pre_C)


def main(args):
    N = int(input())
    acivities = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, acivities)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])