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


#  dpテーブルの初期化
dp = [abcList[0]]

#  dpテーブルの完成
for i in range(1, n):
    dp.append(
        [
            abcList[i][0] + max(dp[-1][1], dp[-1][2]),
            abcList[i][1] + max(dp[-1][2], dp[-1][0]),
            abcList[i][2] + max(dp[-1][0], dp[-1][1]),
        ]
    )

print(max(dp[-1]))

Submission status: Accepted

Solution code:
from sys import stdin


def solve():
    n = int(input())
    A = []
    for _ in range(n):
        k = [int(i) for i in stdin.readline().split()]
        A.append(k)
    if n == 1: return max(A[0])
    for i in range(1, len(A)):
        A[i][0] += max(A[i-1][1], A[i-1][2])
        A[i][1] += max(A[i-1][0], A[i-1][2])
        A[i][2] += max(A[i-1][0], A[i-1][1])
    return max(A[-1])

print(solve())

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

Submission status: Accepted

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

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

print(max(dp))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function
from collections import defaultdict, Counter, deque
from future_builtins import ascii, filter, hex, map, oct, zip
from itertools import imap as map, izip as zip, permutations, combinations, combinations_with_replacement
from __builtin__ import xrange as range
from math import ceil, factorial, log
from _continuation import continulet
from cStringIO import StringIO
from io import IOBase
import __pypy__
from bisect import bisect, insort, bisect_left, bisect_right
from fractions import Fraction
from functools import reduce
import string
import sys
import os
import re
inf = float('inf')
mod_ = int(1e9) + 7
mod = 998244353

def factors(n):
    from functools import reduce
    return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def sieve(m):
    n=1
    primes = {}
    arr=set([])
    for i in range(2, int(m ** 0.5) + 1):
        a = n // i
        b = m // i
        for k in range(max(2, a), b + 1):
            c = i * k
            primes[c] = 1

    for i in range(max(n, 2), m + 1):
        if i not in primes:
            arr.add(i)

    return arr

def nc2(x):
    return (x*(x-1))//2
class DisjointSetUnion:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = n
 
    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a
 
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a != b:
            if self.size[a] < self.size[b]:
                a, b = b, a
 
            self.num_sets -= 1
            self.parent[b] = a
            self.size[a] += self.size[b]
 
    def set_size(self, a):
        return self.size[self.find(a)]
 
    def __len__(self):
        return self.num_sets



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











        

        
    




    



# region fastio

BUFSIZE = 8192

class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

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

print(max(dpa, dpb, dpc))

Submission status: Accepted

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

dpa = 0
dpb = 0
dpc = 0

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


print(max(dpa,dpb,dpc))

Submission status: Accepted

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

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

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


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
x=int(input())
A=[]
B=[]
C=[]
dictA=[-1]*x
dictB=[-1]*x
dictC=[-1]*x
for i in range(x):
    a,b,c=list(map(int,input().split()))
    A.append(a)
    B.append(b)
    C.append(c)
def maxA(n):
    if dictA[n]!=-1:
        return dictA[n]
    if n==0:
        dictA[n]=A[0]
        return A[0]
    dictA[n]=A[n]+max(maxB(n-1),maxC(n-1))
    return dictA[n]
def maxB(n):
    if dictB[n]!=-1:
        return dictB[n]
    if n==0:
        dictB[n]=B[0]
        return B[0]
    dictB[n]=B[n]+max(maxA(n-1),maxC(n-1))
    return dictB[n]
def maxC(n):
    if dictC[n]!=-1:
        return dictC[n]
    if n==0:
        dictC[n]=C[0]
        return C[0]
    dictC[n]=C[n]+max(maxB(n-1),maxA(n-1))
    return dictC[n]
def Nmax(n):
    return max(maxA(n),maxB(n),maxC(n))
print(Nmax(x-1))

Submission status: Accepted

Solution code:
n = int(input())
inf = float("inf")

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

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


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

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    dp=[0]*(3)
    for _ in range(n):
        dp1=[0]*3 
        nums=list(map(int,input().split()))
        for i in range(3):
            for j in range(3):
                if i!=j:
                    dp1[j]=max(dp1[j],dp[i]+nums[j])
            
        dp=dp1
    print( max(dp[0],dp[1],dp[2]))
if __name__ == '__main__':
    main()

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

Submission status: Accepted

Solution code:
from pprint import pprint


n = int(input())

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

dp_table = [[-float("inf")]*(n+1) for _ in range(3)]

#0日目は幸福度0
dp_table[0][0] = 0
dp_table[1][0] = 0
dp_table[2][0] = 0

for i in range(1,n+1):
    for abc in range(3):
        for before_abc in range(3):
            if abc != before_abc:
                dp_table[abc][i] = max(dp_table[abc][i],dp_table[before_abc][i-1] + points[i-1][abc])
            else:
                continue

pprint(max(dp_table[0][-1],dp_table[1][-1],dp_table[2][-1]))

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
if __name__=='__main__':
    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(x,z)+b,max(x,y)+c 
    
    print(max(x,y,z))

Submission status: Accepted

Solution code:
# coding:utf-8

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

dp = [[0 for x in range(3)] for y in range(N)]

dp[0][0] = act[0][0]
dp[0][1] = act[0][1]
dp[0][2] = act[0][2]

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

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

print(m)

Submission status: Accepted

Solution code:
N = 3
ARR = [
    [10, 40, 70],
    [20, 50, 80],
    [30, 60, 90]
]

N = 1
ARR = [
    [
        100, 10, 1
    ]
]


N = 7
ARR = [
    [6, 7, 8],
    [8, 8, 3],
    [2, 5, 2],
    [7, 8, 6],
    [4, 6, 8],
    [2, 3, 4],
    [7, 5, 1]
]

N = int(input())
ARR = []

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


def calculate(n, arr):
    result = []



    for index, value in enumerate(arr):
        if index == 0:
            result.append(value)
        else:
            s0 = max(value[0] + result[index - 1][1], value[0] + result[index - 1][2])
            s1 = max(value[1] + result[index - 1][0], value[1] + result[index - 1][2])
            s2 = max(value[2] + result[index - 1][0], value[2] + result[index - 1][1])
            result.append([s0, s1, s2])


    print(max(result[-1]))


calculate(N, ARR)

Submission status: Accepted

Solution code:
n = int(input())
c = [[],[],[]]
for x in range(n):
    a_,b_,c_ = [int(x) for x in input().split(" ")]
    c[0].append(a_)
    c[1].append(b_)
    c[2].append(c_)

dp = [0 for x in range(3)]
for i in range(n):
    newdp = [0 for x in range(3)]
    for x in range(3):
        for y in range(3):
            if x != y:
                newdp[y] = max(newdp[y], dp[x] + c[y][i])
    
    dp[0] = newdp[0]
    dp[1] = newdp[1]
    dp[2] = newdp[2]

print(max(dp))

Submission status: Accepted

Solution code:
import numpy as np

# 入力
N = int(input())
a = np.array([[int(i) for i in input().split()] for j in range(N)]).T

# a(0行), b(1行), c(2行)の添え字付きDPテーブルを生成
dp = np.zeros(3*(N+1), dtype=int).reshape(3, (N+1))

# 0日目(0)からN-1日目(N-1)までループ処理
for i in range(N):    # 参照する前日(i)
    for j in [0, 1, 2]:    # 前日(i)のアクティビティ
        for k in [0, 1, 2]:    # 当日(i+1)のアクティビティ
            if j != k:    # 前日のアクティビティではいけない
                dp[k, i+1] = max(dp[k, i+1], dp[j, i] + a[j, i])
                
# N日目の処理
ans = 0
for j in [0, 1, 2]:
    ans = max(ans, dp[j, N])
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    ABC = [(0, 0, 0)]
    for _ in range(N):
        a, b, c = map(int, input().split())
        ABC.append((a, b, c))

    dp_a = [0] * (N + 1)
    dp_b = [0] * (N + 1)
    dp_c = [0] * (N + 1)
    for i in range(1, N + 1):
        a, b, c = ABC[i]
        dp_a[i] = max(dp_b[i - 1] + a, dp_c[i - 1] + a)
        dp_b[i] = max(dp_c[i - 1] + b, dp_a[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]))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# N = 3
# ARR = [
#     [10, 40, 70],
#     [20, 50, 80],
#     [30, 60, 90]
# ]


# N = 7
# ARR = [
#     [6, 7, 8],
#     [8, 8, 3],
#     [2, 5, 2],
#     [7, 8, 6],
#     [4, 6, 8],
#     [2, 3, 4],
#     [7, 5, 1]
# ]
#

N = int(input())
ARR = []

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



def calculate(n, arr):
    result = []
    for index, ar in enumerate(arr):
        if index == 0:
            result.append(ar)
        else:
            s1 = max(result[-1][1] + ar[0], result[-1][2] + ar[0])
            s2 = max(result[-1][0] + ar[1], result[-1][2] + ar[1])
            s3 = max(result[-1][0] + ar[2], result[-1][1] + ar[2])
            result.append([s1, s2, s3])

    print(max(result[-1]))


calculate(N, ARR)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
m=[[]*n for i in range(3)]

for i in range(n):
    a,b,c=map(int,input().split())
    m[0].append(a)
    m[1].append(b)
    m[2].append(c)

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

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

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

Submission status: Accepted

Solution code:
import sys
# import numpy as np

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N = I()
	activity = []
	for i in range(N):
		activity.append(LI())
	
	# dp = np.zeros((N, 3), dtype=int)
	dp = [[0, 0, 0] for _ in range(N)]
	dp[0][0] = activity[0][0]
	dp[0][1] = activity[0][1]
	dp[0][2] = activity[0][2]
	for i in range(1, N):
		dp[i][0] = max(dp[i-1][1] + activity[i][0], dp[i-1][2] + activity[i][0])
		dp[i][1] = max(dp[i-1][0] + activity[i][1], dp[i-1][2] + activity[i][1])
		dp[i][2] = max(dp[i-1][0] + activity[i][2], dp[i-1][1] + activity[i][2])
	print(max(dp[-1]))

if __name__ == "__main__":
	main()

Submission status: Accepted

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

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

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

for i in range(2, N + 1):
    for j in range(3):
        if j == 0:
            dp[i][j] = max(dp[i - 1][1] + katsudou[i][j], 
            dp[i - 1][2] + katsudou[i][j])
        elif j == 1:
            dp[i][j] = max(dp[i - 1][0] + katsudou[i][j], 
            dp[i - 1][2] + katsudou[i][j])
        else:
            dp[i][j] = max(dp[i - 1][0] + katsudou[i][j], 
            dp[i - 1][1] + katsudou[i][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() )
#    print( a[ i ], b[ i ], c[ i ] )

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

print( max( dpa, dpb, dpc ) )

Submission status: Accepted

Solution code:
n = int(input())
abcs = [None for _ in range(n)]

# dp[i][j][k] i 番目 連続/未連続 abc
for i in range(n):
    abcs[i] = list(map(int, input().split()))

dp = [abcs[0]] + [[0, 0, 0] for _ in range(n - 1)]
for i in range(1, n):
    for k in range(3):  # next abc
        for j in range(3):  # previous abc
            if k != j:
                dp[i][k] = max(dp[i][k], dp[i - 1][j] + abcs[i][k])
print(max(dp[i]))
# これは三日以上
# for i in range(n):
#     for k in range(3):  # next abc
#         for j in range(2):  # j == 0: 未連続, j == 1: 連続
#             for l in range(3):  # previous abc
#                 if k == l and j == 1:
#                     dp[i][j][k] = dp[i - 1][0][l] + abcs[i][k]
#                 elif k != l:
#                     dp[i][j][k] = max(dp[i][j][k],
#                                       dp[i - 1][j][l] + abcs[i][k])
#                 print(dp[i])

Submission status: Accepted

Solution code:

n = int(input())
abc = []
for _ in range(n):
  abc.append(list(map(int, input().split())))
hap = abc[0]
for day in range(1, n):
  a = abc[day][0] + max(hap[1], hap[2])
  b = abc[day][1] + max(hap[0], hap[2])
  c = abc[day][2] + max(hap[1], hap[0])
  hap = [a,b,c]
print(max(hap))

Submission status: Accepted

Solution code:
from sys import stdin, stdout
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A, B, C = [], [], []
	for _ in range(n):
		a, b, c = rli()
		A.append(a)
		B.append(b)
		C.append(c)
	LA, LB, LC = A[0], B[0], C[0]
	for i in range(1, n):
		nLA = A[i] + max(LB, LC)
		nLB = B[i] + max(LA, LC)
		nLC = C[i] + max(LB, LA)
		LA, LB, LC = nLA, nLB, nLC
	print(max(LA, LB, LC))
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
N = int(input())

costs = [[0, 0, 0] for _ in range(N + 1)]  # [[0,0,0], [10,20,30]]
for n in range(1, N + 1):
    a, b, c = map(int, input().split())
    if n == 1:
        costs[1][0] = a
        costs[1][1] = b
        costs[1][2] = c
        continue
    max_value = 0
    for i in range(3):
        if i == 0:
            tmp_max_b_a = costs[n - 1][1] + a
            tmp_max_c_a = costs[n - 1][2] + a
            max_value = max(tmp_max_b_a, tmp_max_c_a)
            costs[n][0] = max_value
        if i == 1:
            tmp_max_a_b = costs[n - 1][0] + b
            tmp_max_c_b = costs[n - 1][2] + b
            max_value = max(tmp_max_a_b, tmp_max_c_b)
            costs[n][1] = max_value
        if i == 2:
            tmp_max_a_c = costs[n - 1][0] + c
            tmp_max_b_c = costs[n - 1][1] + c
            max_value = max(tmp_max_a_c, tmp_max_b_c)
            costs[n][2] = max_value
print(max(costs[-1]))

Submission status: Accepted

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

def maximizeVacation(swimming, bugs, homework):
    '''
    Each of swimming, bugs, and homework represents a list of values for that activity on day i of the list.
    Return the maximum value possible such that an activity cannot be performed consecutively.
    '''
    n = len(swimming) 
    '''
    justSwam =      [0] * n
    justBugged =    [0] * n
    justDidHw =     [0] * n

    justSwam[0] = swimming[0]
    justBugged[0] = bugs[0]
    justDidHw[0] = homework[0]
    '''
    justSwam = swimming[0]
    justBugged = bugs[0]
    justDidHw = homework[0]

    for i in range(1, n):
        tmpSwam, tmpBugged, tmpHw = justSwam, justBugged, justDidHw
        justSwam = max(tmpBugged, tmpHw) + swimming[i]
        justBugged = max(tmpSwam, tmpHw) + bugs[i]
        justDidHw = max(tmpSwam, tmpBugged) + homework[i]

        '''
        justSwam[i] = max(justBugged[i-1], justDidHw[i-1]) + swimming[i]
        justBugged[i] = max(justSwam[i-1], justDidHw[i-1]) + bugs[i]
        justDidHw[i] = max(justSwam[i-1], justBugged[i-1]) + homework[i]
        '''

        '''
        justSwam[i] = max(justBugged[i-1], justDidHw[i-1]) + justSwam[i-1] 
        justBugged[i] = max(justSwam[i-1], justDidHw[i-1]) + justBugged[i-1]
        justDidHw[i] = max(justSwam[i-1], justBugged[i-1]) + justDidHw[i-1]
        '''

    return max(justSwam, justBugged, justDidHw)

def main():
    '''
    print("Vacation dynamic programming problem")
    print(maximizeVacation([10, 20, 30], [40, 50, 60], [70, 80, 90]))
    print(maximizeVacation([100], [10], [1]))
    print(maximizeVacation([6, 8, 2, 7, 4, 2, 7], [7, 8, 5, 8, 6, 3, 5], [8, 3, 2, 6, 8, 4, 1]))
    '''
    n = int(input())

    swimming = [0] * n
    bugs = [0] * n
    homework = [0] * n

    for i in range(n):
        values = input()
        values = values.split()
        swimming[i] = int(values[0])
        bugs[i] = int(values[1])
        homework[i] = int(values[2])

    print(maximizeVacation(swimming, bugs, homework))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def maximizeVacation(swimming, bugs, homework):
    '''
    Each of swimming, bugs, and homework represents a list of values for that activity on day i of the list.
    Return the maximum value possible such that an activity cannot be performed consecutively.
    '''
    n = len(swimming) 
    justSwam =      [0] * n
    justBugged =    [0] * n
    justDidHw =     [0] * n

    justSwam[0] = swimming[0]
    justBugged[0] = bugs[0]
    justDidHw[0] = homework[0]

    for i in range(1, n):
        justSwam[i] = max(justBugged[i-1], justDidHw[i-1]) + swimming[i]
        justBugged[i] = max(justSwam[i-1], justDidHw[i-1]) + bugs[i]
        justDidHw[i] = max(justSwam[i-1], justBugged[i-1]) + homework[i]

        '''
        justSwam[i] = max(justBugged[i-1], justDidHw[i-1]) + justSwam[i-1] 
        justBugged[i] = max(justSwam[i-1], justDidHw[i-1]) + justBugged[i-1]
        justDidHw[i] = max(justSwam[i-1], justBugged[i-1]) + justDidHw[i-1]
        '''

    return max(justSwam[n-1], justBugged[n-1], justDidHw[n-1])

def main():
    '''
    print("Vacation dynamic programming problem")
    print(maximizeVacation([10, 20, 30], [40, 50, 60], [70, 80, 90]))
    print(maximizeVacation([100], [10], [1]))
    print(maximizeVacation([6, 8, 2, 7, 4, 2, 7], [7, 8, 5, 8, 6, 3, 5], [8, 3, 2, 6, 8, 4, 1]))
    '''
    n = int(input())

    swimming = [0] * n
    bugs = [0] * n
    homework = [0] * n

    for i in range(n):
        values = input()
        values = values.split()
        swimming[i] = int(values[0])
        bugs[i] = int(values[1])
        homework[i] = int(values[2])

    print(maximizeVacation(swimming, bugs, homework))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortresult:
        div.sort()
    return div
# endregion
N = ri()
a = [0] * N
b = [0] * N
c = [0] * N
for i in range(N):
    a[i], b[i], c[i] = ri_()
dp = [[0] * 3 for _ in range(N)]
dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]
for i in range(1, N):
    dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + a[i]
    dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + b[i]
    dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + c[i]
print(max(dp[N - 1]))

Submission status: Accepted

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


def solve():
  N = int(input())

  A, B, C = 0, 0, 0
  for _ in range(N):
      a, b, c = map(int, input().split())
      A, B, C = max(B, C) + a, max(C, A) + b, max(A, B) + c
  return max(A, B, C)
 
if __name__ == "__main__":
	print(solve())

Submission status: Accepted

Solution code:
N = int(input())

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

print(ans)

Submission status: Accepted

Solution code:
import sys

input = lambda :sys.stdin.readline().rstrip()

def main():
    n = int(input())
    A, B, C = [0 for _ in range(n)], [0 for _ in range(n)], [0 for _ in range(n)]
    for i in range(n):
        a, b, c = map(int, input().split())
        A[i], B[i], C[i] = a, b, c
    ans = solve(n, A, B, C)
    print(ans)


def solve(n, A, B, C):
    a, b, c = 0, 1, 2
    dp = [[0 for _ in range(3)] for _ in range(n)]
    dp[0][a], dp[0][b], dp[0][c] = A[0], B[0], C[0]
    for i in range(1, n):
        dp[i][a] = max(dp[i - 1][b], dp[i - 1][c]) + A[i]
        dp[i][b] = max(dp[i - 1][c], dp[i - 1][a]) + B[i]
        dp[i][c] = max(dp[i - 1][a], dp[i - 1][b]) + C[i]
    #print(*dp, sep = '\n')
    return max(dp[n - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N = I()
abc = [LI() for _ in range(N)]
dp = [[0,0,0] for _ in range(N)]
dp[0] = abc[0]
for i,j,k in itertools.product(range(1,N),[0,1,2],[0,1,2]):
    if j==k:
        continue
    dp[i][j] = max(dp[i][j],dp[i-1][k]+abc[i][j])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N = I()
abc = [LI() for _ in range(N)]
dp = [[0,0,0] for _ in range(N)]
dp[0] = abc[0]
for i,j,k in itertools.product(range(N),[0,1,2],[0,1,2]):
    if j==k:
        continue
    if i-1>=0:
        dp[i][j] = max(dp[i][j],dp[i-1][k]+abc[i][j])
print(max(dp[-1]))

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

Submission status: Accepted

Solution code:
#最初に置いておくもの
import sys
sys.setrecursionlimit(500000) 
input=sys.stdin.readline

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

inf=float('inf')
dp=[[0]*3 for j in range(N+1)]

def chmax(a,b):
    return max(a,b)

for n in range(N):
    for i in range(3):
        for m in range(3):
                if (i == m):
                    continue
                dp[n+1][m]=chmax(dp[n+1][m], dp[n][i] + A[n][m])


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
l=[]
dp=[[0 for i in range(3)]for j in range(N+2)]
for i in range(N):
    a,b,c=[int(x) for x in input().rstrip().split()]
    l.append([a,b,c])


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