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:
def main():
    n = int(input())
    abc = [list(map(int,input().split())) for i 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(n-1):
        for j in range(3):
            dp[i+1][j] = max(dp[i][(j+1) % 3], dp[i][(j+2) % 3]) + abc[i+1][j]

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    abc = [list(map(int,input().split())) for i 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(n-1):
        today = dp[i]
        tomorrow = abc[i+1]
        for j in range(3):
            for k in range(3):
                if j == k:
                    continue
                dp[i+1][j] = max(dp[i+1][j], today[k] + tomorrow[j])

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
data = [list(map(int, input().split(" "))) for i in range(N)]
dp = [[0] * 3 for i in range(N+1)]
dp[0][0]=0
dp[0][1]=0
dp[0][2]=0
ans=0
for i in range(0,N):
    for k in range(3):
        for j in range(3):
            if j != k:
                dp[i+1][k] = max(dp[i+1][k], dp[i][j] + data[i][k])
ans = max(dp[N][0], dp[N][1])
print(max(ans, dp[N][2]))

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
abc=np.array([list(map(int,input().split())) for _ in range(n)])
dp=np.zeros((n+1,3),np.int64)
# dp[i+1][j]:i日目にjで遊んだ時の最大の幸福度
# dp[0][j]=0,dp[1][j]=abc[0][j]
dp[1]=abc[0]
for i in range(1,n):
      dp[i+1][0]=abc[i][0]+max(dp[i][1],dp[i][2])
      dp[i+1][1]=abc[i][1]+max(dp[i][0],dp[i][2])
      dp[i+1][2]=abc[i][2]+max(dp[i][0],dp[i][1])
print(np.max(dp[-1]))

Submission status: Accepted

Solution code:
N = input()

score = [[0,0,0] for n in range(N)]

for n in range(N) :
  a, b, c = map(int,raw_input().split())

  if n == 0 : score[0] = [a, b, c]
  else : 
    score[n][0] = a + max(score[n-1][1], score[n-1][2])
    score[n][1] = b + max(score[n-1][0], score[n-1][2])
    score[n][2] = c + max(score[n-1][0], score[n-1][1])
  
print max(score[-1])

Submission status: Accepted

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

dp = [[-1]*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(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[-1]))

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
dpa = [0]*N
dpb = [0]*N
dpc = [0]*N
dpa[0] = A[0][0]
dpb[0] = A[0][1]
dpc[0] = A[0][2]
for i in range(1,N):
    a = A[i][0]
    b = A[i][1]
    c = A[i][2]
    dpa[i] = max(dpb[i-1]+a,dpc[i-1]+a)
    dpb[i] = max(dpa[i-1]+b,dpc[i-1]+b)
    dpc[i] = max(dpb[i-1]+c,dpa[i-1]+c)
Min = dpa[N-1]
Mmin = max(dpb[N-1],dpc[N-1])
print(max(Min,Mmin))

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
dpa = [0]*N
dpb = [0]*N
dpc = [0]*N
dpa[0] = A[0][0]
dpb[0] = A[0][1]
dpc[0] = A[0][2]
for i in range(1,N):
    a = A[i][0]
    b = A[i][1]
    c = A[i][2]
    dpa[i] = max(dpb[i-1]+a,dpc[i-1]+a)
    dpb[i] = max(dpa[i-1]+b,dpc[i-1]+b)
    dpc[i] = max(dpb[i-1]+c,dpa[i-1]+c)
Min = dpa[N-1]
Mmin = max(dpb[N-1],dpc[N-1])
print(max(Min,Mmin))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    n = int(input())
    abc = [list(map(int, input().split())) for i in range(n)]
    abc.reverse()

    ans = [[-1 for _ in range(3)] for __ in range(n)]

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

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

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3
10 40 70
20 50 80
30 60 90"""
        output = """210"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """1
100 10 1"""
        output = """100"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1"""
        output = """46"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

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

ans = []
ans.append(happy[0])

for i in range(1, n):
    ans.append( [max(ans[i-1][(j+1)%3] + happy[i][j], ans[i-1][(j+2)%3] + happy[i][j]) for j in range(3)] )

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  n=int(input())
  l=[tuple(map(int,input().split())) for _ in range(n)]
  dp=[[0]*3 for _ in range(n+1)]
  for i in range(1,n+1):
    dp[i][0]=max(dp[i-1][1],dp[i-1][2])+l[i-1][0]
    dp[i][1]=max(dp[i-1][2],dp[i-1][0])+l[i-1][1]
    dp[i][2]=max(dp[i-1][0],dp[i-1][1])+l[i-1][2]
  print(max(dp[-1]))
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
     
    N = int(readline())
    m = map(int,read().split())
    ABC = zip(m,m,m)
     
    x,y,z = 0,0,0 # 最後の活動 -> 幸福度のmax
    for a,b,c in ABC:
        x,y,z = max(y,z)+a,max(x,z)+b,max(x,y)+c
     
    answer = max(x,y,z)
    print(answer)
main()

Submission status: Accepted

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

dp = [[0] * 3 for _ in range(N)]
dp[0] = abc[0]
# print(dp)

for day in range(N - 1):
    for todo in range(3):
        for did in range(3):
            if todo != did:
                dp[day + 1][todo] = max(dp[day][did] + abc[day + 1][todo], dp[day + 1][todo])
print(max(dp[N - 1]))

Submission status: Accepted

Solution code:
n=int(input())
happy=list(map(int,input().split(' ')))
for i in range(1,n):
    h=list(map(int,input().split(' ')))
    x=max(happy[1]+h[0],happy[2]+h[0])
    y=max(happy[2]+h[1],happy[0]+h[1])
    z=max(happy[0]+h[2],happy[1]+h[2])
    happy=[x,y,z]
print(max(happy))

Submission status: Accepted

Solution code:


def solve(N, arr):

	dp = [0] * 3

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

	for i in range(1, N):
		dp2 = [0] * 3
		for j in range(3):
			for x in [(j - 1) % 3, (j + 1) % 3]:

				if 0 <= x < 3:
					dp2[j] = max(dp2[j], dp[x] + arr[i][j])
		dp = dp2
	return max(dp)

N = int(input())
arr = []
for _ in range(N):
	arr.append([int(s) for s in input().split()])
print(solve(N, arr))

Submission status: Accepted

Solution code:
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N)]
INF = 1 << 100
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][k] = max(ABC[i-1][k] + dp[i - 1][j], dp[i][k])
print(max(dp[N]))

Submission status: Accepted

Solution code:
n = int(input())
ABC = [tuple(map(int, input().split())) for i in range(n)]
A = [a for a, b, c in ABC]
B = [b for a, b, c in ABC]
C = [c for a, b, c in ABC]
DP = [[0 for j in range(3)] for i in range(n+1)]
for i in range(1, n+1):
    DP[i][0] = max(DP[i-1][1], DP[i-1][2])+A[i-1]
    DP[i][1] = max(DP[i-1][2], DP[i-1][0])+B[i-1]
    DP[i][2] = max(DP[i-1][0], DP[i-1][1])+C[i-1]
print(max(DP[n]))

Submission status: Accepted

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

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

for i in range(1,n+1):
    a,b,c=d[i]
    dp_a,dp_b,dp_c=dp[i-1]
    dp[i]=[max(dp_b+a,dp_c+a),max(dp_c+b,dp_a+b),max(dp_a+c,dp_b+c)]

dp_a,dp_b,dp_c=dp[n]
print(max(dp_a,dp_b,dp_c))

Submission status: Accepted

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

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

dpA = [0]*N
dpB = [0]*N
dpC = [0]*N
dpA[0] = S[0][0]
dpB[0] = S[0][1]
dpC[0] = S[0][2]

for i in range(1, N):
    dpA[i] = max(dpB[i-1], dpC[i-1]) + S[i][0]
    dpB[i] = max(dpC[i-1], dpA[i-1]) + S[i][1]
    dpC[i] = max(dpA[i-1], dpB[i-1]) + S[i][2]

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

Submission status: Accepted

Solution code:
import math
import operator as op
from functools import reduce
from fractions import Fraction as frac

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
"""
int(input())
map(int,input().split())
list(map(int,input().split()))
"""
# t=int(input())
n=int(input())
A=[]
for i in range(n):
    x=list(map(int,input().split()))
    A.append(x)
dp=[[0,0,0] for i in range(n+1)]
for i in range(1,n+1):
    dp[i][0]=max(dp[i-1][1]+A[i-1][1],dp[i-1][2]+A[i-1][2])
    dp[i][1]=max(dp[i-1][0]+A[i-1][0],dp[i-1][2]+A[i-1][2])
    dp[i][2]=max(dp[i-1][1]+A[i-1][1],dp[i-1][0]+A[i-1][0])
print(max(dp[n]))

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)

n=int(data())
dp1=[0]*(n+1)
dp2=[0]*(n+1)
dp3=[0]*(n+1)
for i in range(1,n+1):
    a,b,c=mdata()
    dp1[i]=max(dp2[i-1],dp3[i-1])+a
    dp2[i] = max(dp1[i - 1], dp3[i - 1]) + b
    dp3[i] = max(dp2[i - 1], dp1[i - 1]) + c
print(max(dp1[-1],dp2[-1],dp3[-1]))

Submission status: Accepted

Solution code:
from sys import stdin


# 最大化問題
def chmax(a,b):
    if a < b: return b
    else: return a


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    a_b_c_arr = []
    for i in range(N):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        a_b_c_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dp = [[0] * 3 for _ in range(N+1)] # 最大化問題 (初期条件 dp=0)
    
    # 配るDP
    for i in range(N):
        for j in range(3):
            for k in range(3):
                if j != k:
                    dp[i+1][k] = chmax(dp[i+1][k],dp[i][j]+a_b_c_arr[i][k])
    cnt = max(dp[N])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = [0]*N
for i in range(N):
    A[i] = list(map(int, input().split()))
def solve(N,A):
    dp = [[0]*3 for i 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]
    ans = max(dp[-1])
    return ans
print(solve(N,A))

Submission status: Accepted

Solution code:
N = int(input())
li = [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):
    a = 0
    for k in range(3):
      if j == k:
        continue
      a = max(a,(dp[i][k]))
    dp[i+1][j] = max(dp[i+1][j],a + li[i][j])
  
print(max(dp[-1]))

Submission status: Accepted

Solution code:
#3

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

dp=[[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:
                continue
            dp[i][j]=max(dp[i][j],dp[i-1][k]+act[i][j])
print(max(dp[N]))

Submission status: Accepted

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

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[i],b[i],c[i] = map(int,input().split())
dp = [[0,0,0] for i in range(n+1)]
for i in range(1,n+1):
    for j in range(3):
        if j == 0: dp[i][j] = max(dp[i-1][1],dp[i-1][2])+a[i]
        elif j == 1: dp[i][j] = max(dp[i-1][0],dp[i-1][2])+b[i]
        else: dp[i][j] = max(dp[i-1][0],dp[i-1][1])+c[i]
print(max(dp[n]))

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[i],b[i],c[i] = map(int,input().split())
dp = [[0,0,0] for i in range(n+1)]
for i in range(1,n+1):
    for j in range(3):
        if j == 0: dp[i][j] = max(dp[i-1][1]+a[i],dp[i-1][2]+a[i])
        elif j == 1: dp[i][j] = max(dp[i-1][0]+b[i],dp[i-1][2]+b[i])
        else: dp[i][j] = max(dp[i-1][0]+c[i],dp[i-1][1]+c[i])
print(max(dp[n]))

Submission status: Accepted

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

# print(*dp, sep='\n')
print(max(dp[N-1]))

Submission status: Accepted

Solution code:
import sys


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


sys.setrecursionlimit(10 ** 9)


def main():
    N = int(input())
    A = [0]
    B = [0]
    C = [0]
    for _ in range(N):
        a, b, c = map(int, input().split())
        A.append(a)
        B.append(b)
        C.append(c)
    dp = [[0 for _ in range(N + 1)] for _ in range(3)]

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def q3():
    """C - Vacation"""
    N = int(input())

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

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

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

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

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


if __name__ == '__main__':
    q3()

Submission status: Accepted

Solution code:
N = int(input())
happiness = [[0,0,0] for i in range(N)]
for i in range(N) :
	feeling = [int(i) for i in input().split()]
	for j in range(3) :
		if i != 0 :
			if j == 0 :
				happiness[i][j] = feeling[j] + max(happiness[i-1][1], happiness[i-1][2])
			elif j == 1 :
				happiness[i][j] = feeling[j] + max(happiness[i-1][0], happiness[i-1][2])
			elif j == 2 :
				happiness[i][j] = feeling[j] + max(happiness[i-1][0], happiness[i-1][1])
		else :
			happiness[i] = feeling
			break
print(max(happiness[N-1]))

Submission status: Accepted

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

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

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] + l[i][j])

print(max(dp[-1]))

Submission status: Accepted

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

#print(H)

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


def chmax(dp,i,j, x):
	b = (dp[i][j]<x)
	if b: dp[i][j]=x
	return b


for i in range(N):
	for j in range(3):
		for k in range(3):
			if j==k: continue
			chmax(dp,i,j, H[i][j] + (dp[i-1][k] if i>0 else 0))

print( max(dp[-1]) )

#print(dp)

Submission status: Accepted

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

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()

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


for i in range(N):
    abc = LIST()
    if i == 0:
        DP[0] = abc
        continue
    for j in range(3):
        DP[i][j] = max(DP[i-1][(j+1)%3] + abc[j],
                       DP[i-1][(j+2)%3] + abc[j])


print(max(DP[-1]))

Submission status: Accepted

Solution code:
INF  = float("inf") # 正の無限大

N = int(input())						# 5

A=[0]*N
B=[0]*N
C=[0]*N

for i in range(N):
	a,b,c = map(int, input().split())		# 5 7 2
	A[i] = a
	B[i] = b
	C[i] = c


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

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


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

#print(dp)

Submission status: Accepted

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

dp = [[0,0,0] for _ in range(N)]
dp[0] = L[0].copy()
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][0], dp[i-1][1])
    #print(dp)
print(max(dp[-1]))

Submission status: Accepted

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

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    DP = [[0 for i in range(3)] for j in range(N+1)]
    
    for i in range(N):
        a = list(map(int, input().split()))
        for x in range(3):
            for y in range(3):
                if x != y:
                    DP[i+1][y] = max(DP[i+1][y],DP[i][x]+a[y])
    print(max(DP[-1]))

if __name__ == "__main__":
    main()
    pass

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
abc = [map(int,input().split()) for _ in range(n)]
a,b,c = [list(i) for i in zip(*abc)]
dp = [[0]*3 for _ in range(n+1)]
d = [0,1,2] #aが0,bが1,cが,2に対応している
for i in d:#初期値の設定（今回はなくても可）
    dp[0][i] = 0
for i in range(1,n+1):#全体の漸化式
    for j in d:#iを固定したときのjにまつわる漸化式
        if j%3 == 0:
            dp[i][j] = max(dp[i-1][(j+1)%3]+a[i-1],dp[i-1][(j+2)%3]+a[i-1])
        elif j%3 == 1:
            dp[i][j] = max(dp[i-1][(j+1)%3]+b[i-1],dp[i-1][(j+2)%3]+b[i-1])
        else:
            dp[i][j] = max(dp[i-1][(j+1)%3]+c[i-1],dp[i-1][(j+2)%3]+c[i-1])
ans = max(dp[n][0],dp[n][1],dp[n][2])
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
dp=[[0]*3 for i in range(N+1)]#今回は正の範囲で最大値をもとめたいので0で初期化
for i in range(N):
  a=list(map(int,input().split()))
  for j in range(3):
    for k in range(3):
      if k!=j:
        dp[i+1][j]=max(dp[i][k]+a[j],dp[i+1][j])
print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def resolve():
	n = int(input())
	dp = [[0]*3 for _ in range(n+1) ]
	for i in range(1, n+1):
		r = 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] + r[j])
	print(max(dp[-1]))
resolve()

Submission status: Accepted

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

n = int(input())
dp = [[0]*3  for _ in range(n)] 
ABC = []
for _ in range(n):
    a,b,c = map(int,input().split())
    ABC.append([a,b,c])

def rec(flag,num):# flag は A=0,B=1,C=2を表す。 numは何番目かを表す。
    if dp[num][flag] != 0:
        return dp[num][flag]
    if num == 0:
        dp[num][flag] = ABC[num][flag]
        return dp[num][flag]
    else:
        res = 0
        if flag == 0:
            res = max(rec(1,num-1),rec(2,num-1))+ABC[num][flag]
        elif flag == 1:
            res = max(rec(0,num-1),rec(2,num-1))+ABC[num][flag]
        else:
            res = max(rec(1,num-1),rec(0,num-1))+ABC[num][flag]
        dp[num][flag] = res
        return dp[num][flag]

rec(0,n-1)
rec(1,n-1)
rec(2,n-1)

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

Submission status: Accepted

Solution code:
N=int(input())

X=[0]   #X[0]はダミー #X[i]はi日めの活動の情報
for x in range(N):
    x=tuple(map(int,input().split()))
    X.append(x)

inf=float('inf')
DP=[[0,0,0]]
for i in range(N):
    DP.append([-inf,-inf,-inf])

#DPの初期値
DP[1][0]=X[1][0]
DP[1][1]=X[1][1]
DP[1][2]=X[1][2]

for i in range(2,N+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]+X[i][j])

#for index in range(N+1):
    #print(DP[index])

print(max(DP[N]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    HAPPY = [list(map(int, input().split())) for i in range(N)]
    dp = [[0]*3 for i in range(N+1)]
    for i in range(N):
        for j in range(3):
            for k in range(3):
                if j == k:
                    continue
                dp[i+1][k] = max(dp[i+1][k], HAPPY[i][k] + dp[i][j])
    print(max(max(dp[N][0], dp[N][1]), dp[N][2]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
  n = int(input())  #nは入力回数
  num_list = [list(map(int, input().split())) for _ in range(n)]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
H=[[0,0,0] for _ in range(110000)]
dp=[[0,0,0] for _ in range(110000)]

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

for i in range(1,N+1):
    for p in range(3):
        for y in range(3):
            if (p!=y):
                dp[i][p]=max(dp[i][p],dp[i-1][y]+H[i][p])

print(max(dp[N]))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

a,b,c = 0,0,0
n = int(input())
for i in range(n):
    x,y,z = map(int,input().split())
    a,b,c = max(b,c)+x,max(a,c)+y,max(a,b)+z

print(max(a,b,c))

Submission status: Accepted

Solution code:
n=int(input())
lst=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*3 for i in range(n+1)]      #dpテーブル（二次元）

for i in range(1,n+1):
    for j in range(3):      #jはi-1における遊び方
        for k in range(3):      #kはiにおける遊び方
            if(j==k):           #i-1→iに移るとき，j=kは制限により除外
                continue
            dp[i][k]=max(dp[i][k],dp[i-1][j]+lst[i-1][k])       #dp[i]におけるそれぞれのkについて，i-1のそれぞれのjから移り，最大値を更新していく
print(max(dp[n]))       #dp[i]はそれぞれみっつ（各遊び方に対応）あるので，最大値を出力

Submission status: Accepted

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

def chmax(x,y):
    if x>y:
        return x
    else:
        return y

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

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
abc=[]
for _ in range(n):
      abc.append(list(map(int,input().split())))
dp=np.zeros((n+1,3),np.int64)
# dp[i][0]:i日目でaをとった時の最大。dp[0]=[0,0,0]。求めるのはmax(dp[n])
dp[1]=np.array(abc[0])
for i in range(2,n+1):
      dp[i][0]=abc[i-1][0]+max(dp[i-1][1],dp[i-1][2])
      dp[i][1]=abc[i-1][1]+max(dp[i-1][0],dp[i-1][2])
      dp[i][2]=abc[i-1][2]+max(dp[i-1][0],dp[i-1][1])

print(int(np.max(dp[-1])))

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
tuples = []
for i in range(n):
    a,b,c = map(int,input().split())
    tuples.append((a,b,c))
dp = [defaultdict(int) for _ in range(n+1)]
dp[0][3] = 0
for i in range(n):
    abc = tuples[i]
    for j in range(3):
        for k in dp[i].keys():
            if k != j:
                dp[i+1][j] = max(dp[i][k]+abc[j],dp[i+1][j])
print(max(dp[n].values()))

Submission status: Accepted

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

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
a=[[0],[0],[0]]
n = int(input())
for i in range(n):
    A,B,C = map(int,input().split())
    a[0].append(A)
    a[1].append(B)
    a[2].append(C)
dp = []
for j in range(n+1):
    dp.append([0,0,0])

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

Submission status: Accepted

Solution code:
import sys
n=int(input())
dp=[0,0,0]


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

print(max(dp))

Submission status: Accepted

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

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

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

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]) + act[i][j]


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
l = []
for i in range(N):
    h = [int(x) for x in input().split()]
    l.append(h)
DP=[[0 for i in range(3)] for j in range(N+1)]
for j in range(0,N):
    for i in range(3):
        DP[j+1][i%3] = max(DP[j][(i+1)%3]+l[j][i%3], DP[j][(i+2)%3]+l[j][i%3])
print(max(DP[N][0],DP[N][1],DP[N][2]))

Submission status: Accepted

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