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

Submission status: Accepted

Solution code:
import numpy as np
def dprint(*args):
  if debug:
    if len(args)==1:
      print(args[0])
    else:
      print(args)

debug = False
if debug:
  N=3
  ABC=[[10, 40, 70], [20, 50, 80], [30, 60, 90]]
else:
  N = int(input())
  ABC=[]
  for i in range(N):
    ABC.append(list(map(int,input().split())))

dprint(N,ABC)

# i -> 1 to N
# ABC -> 012

H = np.zeros((N,3))
H[0]=ABC[0]

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

print(int(max(H[-1])))

Submission status: Accepted

Solution code:
def vacation(mat):
    temp = [0] * 3
    dp = mat[0]
    for i in range(1, len(mat)):
        temp[0] = mat[i][0] + max(dp[1], dp[2])
        temp[1] = mat[i][1] + max(dp[0], dp[2])
        temp[2] = mat[i][2] + max(dp[0], dp[1])
        dp = temp[:]
    return max(dp)


if __name__ == '__main__':
    n = int(input())
    mat = [[0] * 3 for _ in range(n)]
    for i in range(n):
        mat[i] = list(map(int, input().split()))

    print(vacation(mat))

Submission status: Accepted

Solution code:
N = int(input())
List = [list(map(int,input().split())) for x in range(N)]
List2 = []
for n in range(N):
  if n == 0:
    List2.append(List[0])
  else:
    a = List[n][0] + max(List2[n-1][1],List2[n-1][2])
    b = List[n][1] + max(List2[n-1][0],List2[n-1][2])
    c = List[n][2] + max(List2[n-1][0],List2[n-1][1])
    List2.append([a,b,c])

print(max(List2[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    # N = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    A = [list(map(int, input().split())) for i in range(n)]

    Happy = [[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:
                    Happy[i][j] = max(Happy[i][j], Happy[i-1][k] + A[i-1][j])

    print(max(Happy[n]))
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    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[i][j] := i日目までの活動履歴のうち、最終日であるi日目には活動j(0:A,1:B,2:C)を選んだ場合の、得られる幸福度の最大値
    dp = [[0]*3 for _ in range(N)]
    dp[0] = (a[0],b[0],c[0])
    for i in range(1,N):
        dp[i][0] = max(dp[i-1][2]+a[i], dp[i-1][1]+a[i])
        dp[i][1] = max(dp[i-1][2]+b[i], dp[i-1][0]+b[i])
        dp[i][2] = max(dp[i-1][1]+c[i], dp[i-1][0]+c[i])
    print(max(dp[-1]))


main()

Submission status: Accepted

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

for i in range(1,l):
    z = list(map(int,input().split()))
    x[i][0] = max(z[0]+x[i-1][1],z[0]+x[i-1][2])
    x[i][1] = max(z[1]+x[i-1][0],z[1]+x[i-1][2])
    x[i][2] = max(z[2]+x[i-1][0],z[2]+x[i-1][1])

print(max(x[-1]))

Submission status: Accepted

Solution code:
N = int(input())
l = []

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

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

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

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


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-1][j] + A[i][k], dp[i][k])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    dp=[0]*3
    ndp=copy(dp)
    for i in range(N):
        a,b,c=S[i]
        ndp[0]=max(dp[1]+a,dp[2]+a)
        ndp[1]=max(dp[0]+b,dp[2]+b)
        ndp[2]=max(dp[1]+c,dp[0]+c)
        ndp,dp=dp,ndp
    print(max(dp))



if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
memo = [[0,0,0] for i in range(N)]#a, b, cに対応
for i in range(N):
    a, b, c = map(int, input().split())
    if i ==0:
        memo[i][0] = a
        memo[i][1] = b
        memo[i][2] = c
    else:
        memo[i][0] = max(memo[i-1][1]+a, memo[i-1][2]+a)#do a
        memo[i][1] = max(memo[i-1][0]+b, memo[i-1][2]+b)
        memo[i][2] = max(memo[i-1][0]+c, memo[i-1][1]+c)
print(max(memo[N-1]))

Submission status: Accepted

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

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

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


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

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

Submission status: Accepted

Solution code:
import sys
def solve():
    N = int(input())
    points = []
    for i in range(N):
        arr = list(map(int, input().split()))
        points.append(arr)
    dp = [[0 for i in range(3)] for j in range(N)]
    dp[0] = points[0]
    for i in range(1, N):
        for j in range(3):
            prev_max = -sys.maxsize
            if j == 0:
                prev_max = max(prev_max, dp[i-1][1], dp[i-1][2])
            elif j == 1:
                prev_max = max(prev_max, dp[i-1][0], dp[i-1][2])
            else:
                prev_max = max(prev_max, dp[i-1][1], dp[i-1][0])
            dp[i][j] = points[i][j] + prev_max
    print(max(dp[N-1]))
solve()

Submission status: Accepted

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

Ha = [-1 for _ in range(N)]
Hb = [-1 for _ in range(N)]
Hc = [-1 for _ in range(N)]

Ha[0] = A[0]
Hb[0] = B[0]
Hc[0] = C[0]

for i in range(1, N):
  Ha[i] = max(Hb[i-1] + A[i], Hc[i-1] + A[i])
  Hb[i] = max(Ha[i-1] + B[i], Hc[i-1] + B[i])
  Hc[i] = max(Ha[i-1] + C[i], Hb[i-1] + C[i])

print(max(Ha[N-1], Hb[N-1], Hc[N-1]))

Submission status: Accepted

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

# initialize
dp = [[-float("inf")]*3 for i in range(N+1)]
for i in range(3):
    dp[0][i] = 0

# dp    
for i in range(N+1):
    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            try:
                dp[i+1][k] = max(dp[i+1][k], dp[i][j] + abc[i][k])
            except:
                pass

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

Submission status: Accepted

Solution code:
n = int(input())

felicidade = []

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

DP = [0,0,0]

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

else:

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


    for dia in range(1,n):
        m = [0] * 3
        for x  in range(3):
            for y  in range(3):
                if x != y:
                    m[x] = max(m[x], DP[y] + felicidade[dia][x])
        DP = m

    print(max(DP))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys


def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))


def get_array(): return list(map(int, sys.stdin.readline().strip().split()))


def frog_1(arr, n, k):

    dp = [0] * (n + 1)
    dp[1] = 0

    for i in range(2, n+1):
        dp[i] = float("inf")
        for j in range(1, k+1):
            if i - j >= 1:
                dp[i] = min(dp[i], dp[i - j] + abs(arr[i - 1] - arr[i - j - 1]))

    return dp[n]


def vacation(mat, n):

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


    return max(mat[n - 1])



# n, k = get_ints()
# arr = get_array()

# sys.stdout.write(str(frog_1(arr, n, k)))

n = int(sys.stdin.readline())
mat = []

for i in range(n):
    mat.append(list(map(int, sys.stdin.readline().strip().split())))

sys.stdout.write(str(vacation(mat, n)))

Submission status: Accepted

Solution code:
import sys


def get_ints(): return list(map(int, sys.stdin.readline().strip().split()))


def get_array(): return list(map(int, sys.stdin.readline().strip().split()))


def frog_1(arr, n, k):

    dp = [0] * (n + 1)
    dp[1] = 0

    for i in range(2, n+1):
        dp[i] = float("inf")
        for j in range(1, k+1):
            if i - j >= 1:
                dp[i] = min(dp[i], dp[i - j] + abs(arr[i - 1] - arr[i - j - 1]))

    return dp[n]


def vacation(mat, n):

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


    return max(mat[n])



# n, k = get_ints()
# arr = get_array()

# sys.stdout.write(str(frog_1(arr, n, k)))

n = int(sys.stdin.readline())
mat = [[0 for i in range(3)]]

for i in range(n):
    mat.append(list(map(int, sys.stdin.readline().strip().split())))

sys.stdout.write(str(vacation(mat, n)))

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
dp = FILL2(0,N+1,3)
H = LI2(N)
for i in range(N):
    for j in range(3):
        for k in range(3):
            if j!=k:
                dp[i+1][j] = max(dp[i+1][j],dp[i][k] + H[i][j])

print(max(dp[N]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

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

memo=[[-1,-1,-1] for _ in range(n+1)]
memo[0][0]=0
memo[0][1]=0
memo[0][2]=0
def dp(i,j):
    if memo[i][j]!=-1:
        return memo[i][j]
    else:
        memo[i][j]=max(dp(i-1,(j+1)%3)+l[i][j],dp(i-1,(j+2)%3)+l[i][j])
        return memo[i][j]
s1=dp(n,0)
s2=dp(n,1)
s3=dp(n,2)
print(max(s1,s2,s3))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

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

memo=[[-1,-1,-1] for _ in range(n+1)]
memo[0][0]=0
memo[0][1]=0
memo[0][2]=0
def dp(i,j):
    if memo[i][j]!=-1:
        return memo[i][j]
    else:
        memo[i][j]=max(dp(i-1,(j+1)%3)+l[i][j],dp(i-1,(j+2)%3)+l[i][j])
        return memo[i][j]
print(max(dp(n,0),dp(n,1),dp(n,2)))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
lst=[[] for f in range(N)]
ans=[[0 for e in range(3)] for f in range(N)]
for i in range(N):
 lst[i]=list(map(int,input().split()))
ans[0][0]=lst[0][0]
ans[0][1]=lst[0][1]
ans[0][2]=lst[0][2]
if N>1 :
 for i in range(1,N):
  ans[i][0]=max(ans[i-1][1],ans[i-1][2])+lst[i][0]
  ans[i][1]=max(ans[i-1][0],ans[i-1][2])+lst[i][1]
  ans[i][2]=max(ans[i-1][1],ans[i-1][0])+lst[i][2]
print(max(ans[N-1]))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

print(max(dp[N]))

Submission status: Accepted

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

Submission status: Accepted

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

############ ---- Input Functions ---- ############
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))


n = inp()
scores = []
for i in range(n):
	scores.append(inlt())
#stones = inlt()

if n == 0: 
	print 0
	
#print n, kk

inf = 2 ** 31
# dp[i][j] states the maximum scores to day i with last step chose j 
dp = [[0, 0, 0] for _ in range(len(scores))]

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

for i in range(1, len(dp)):
	for choice in range(3):
		for lastCho in range(3):
			if choice != lastCho: 
				dp[i][choice] = max(dp[i][choice], dp[i-1][lastCho] + scores[i][choice])

print max(dp[-1])

Submission status: Accepted

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

dp = [[0 for i in range(0,3)] for j in range(n)]
dp[0][0] = days[0][0]
dp[0][1] = days[0][1]
dp[0][2] = days[0][2]

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

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

Submission status: Accepted

Solution code:
import numpy as np
N =int(input())
action = [[int(a) for a in input().split()]]
for n in range(N-1):
    action.append([int(a) for a in input().split()])
action = np.array(action)
dp = np.full((N,3),10**10,dtype=int)
dp[0] = action[0]
for i in range(1,N):
    for a in range(3):
        if a ==0:
            dp[i][0] = action[i][0] + max(dp[i-1][1],dp[i-1][2])
        if a ==1:
            dp[i][1] = action[i][1] + max(dp[i-1][0],dp[i-1][2])
        if a ==2:
            dp[i][2] = action[i][2] + max(dp[i-1][1],dp[i-1][0])

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

Submission status: Accepted

Solution code:
N = int(input())

dp = [[0]*3 for _ in range(N+1)]
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(max(dp[N]))

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
x = int(input())
arr = []
for i in range(x):
  arr.append(list(map(int,input().split())))
  
dp =[[0,0,0] for i in range(len(arr))]
dp[0][0],dp[0][1],dp[0][2] = arr[0][0],arr[0][1],arr[0][2]

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

Submission status: Accepted

Solution code:
N = int(input())

max_a = [0] * N
max_b = [0] * N
max_c = [0] * N
if N>1:
    for i in range(0, N):
        a, b, c = map(int, input().split())
        max_a[i] = max(max_b[i - 1] + a, max_c[i-1] + a)
        max_b[i] = max(max_a[i - 1] + b, max_c[i - 1] + b)
        max_c[i] = max(max_a[i - 1] + c, max_b[i - 1] + c)

    print(max(max_a[-1], max_b[-1], max_c[-1]))
else:
    a, b, c = map(int, input().split())

    print(max(a, b, c))

Submission status: Accepted

Solution code:
N = int(input())

As , Bs, Cs = [], [], []

for _ in range(N):
  a, b, c = map(int, input().split())
  As.append(a)
  Bs.append(b)
  Cs.append(c)

Ha = [-1 for _ in range(N)]
Hb = [-1 for _ in range(N)]
Hc = [-1 for _ in range(N)]

Ha[0] = As[0]
Hb[0] = Bs[0]
Hc[0] = Cs[0]

for i in range(1, N):
  Ha[i] = max(Hb[i-1] + As[i], Hc[i-1] + As[i])
  Hb[i] = max(Ha[i-1] + Bs[i], Hc[i-1] + Bs[i])
  Hc[i] = max(Ha[i-1] + Cs[i], Hb[i-1] + Cs[i])

print(max(Ha[N-1], Hb[N-1], Hc[N-1]))

Submission status: Accepted

Solution code:
def chmax(DP,b,i,j):
    if DP[i+1][j] < b:
        DP[i+1][j] = b
        return True
    return False
N = int(input())
A = []
for i in range(N):
    L = [i for i in map(int,input().split())]
    A.append(L)
DP = [[0] * 3 for i in range(2*N)]
for i in range(N):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            chmax(DP,DP[i][k] + A[i][j],i,j)
res = 0
for i in range(3):
    res = max(res,DP[N][i]) 
print(res)

Submission status: Accepted

Solution code:
## necessary imports
import sys
input = sys.stdin.readline
#from math import log2, log, ceil

# swap_array function
def swaparr(arr, a,b):
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp

## gcd function
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a, a)

## nCr function efficient using Binomial Cofficient
def nCr(n, k): 
    if(k > n - k): 
        k = n - k 
    res = 1
    for i in range(k): 
        res = res * (n - i) 
        res = res / (i + 1) 
    return res 

## upper bound function code -- such that e in a[:i] e < x;
def upper_bound(a, x, lo=0):
    hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x:
            lo = mid+1
        else:
            hi = mid
    return lo

## prime factorization
def primefs(n):
    ## if n == 1    ## calculating primes
    primes = {}
    while(n%2 == 0):
        primes[2] = primes.get(2, 0) + 1
        n = n//2
    for i in range(3, int(n**0.5)+2, 2):
        while(n%i == 0):
            primes[i] = primes.get(i, 0) + 1
            n = n//i
    if n > 2:
        primes[n] = primes.get(n, 0) + 1
    ## prime factoriazation of n is stored in dictionary
    ## primes and can be accesed. O(sqrt n)
    return primes

## MODULAR EXPONENTIATION FUNCTION
def power(x, y, p): 
    res = 1
    x = x % p  
    if (x == 0) : 
        return 0
    while (y > 0) : 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
        y = y >> 1      
        x = (x * x) % p 
    return res 

## DISJOINT SET UNINON FUNCTIONS
def swap(a,b):
    temp = a
    a = b
    b = temp
    return a,b

# find function with path compression included (recursive)
# def find(x, link):
#     if link[x] == x:
#         return x
#     link[x] = find(link[x], link);
#     return link[x];

# find function with path compression (ITERATIVE)
def find(x, link):
    p = x;
    while( p != link[p]):
        p = link[p];
    
    while( x != p):
        nex = link[x];
        link[x] = p;
        x = nex;
    return p;


# the union function which makes union(x,y)
# of two nodes x and y
def union(x, y, link, size):
    x = find(x, link)
    y = find(y, link)
    if size[x] < size[y]:
        x,y = swap(x,y)
    if x != y:
        size[x] += size[y]
        link[y] = x

## returns an array of boolean if primes or not USING SIEVE OF ERATOSTHANES
def sieve(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return prime

#### PRIME FACTORIZATION IN O(log n) using Sieve ####
MAXN = int(1e6 + 5)
def spf_sieve():
    spf[1] = 1;
    for i in range(2, MAXN):
        spf[i] = i;
    for i in range(4, MAXN, 2):
        spf[i] = 2;
    for i in range(3, ceil(MAXN ** 0.5), 2):
        if spf[i] == i:
            for j in range(i*i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i;
    ## function for storing smallest prime factors (spf) in the array

################## un-comment below 2 lines when using factorization #################
# spf = [0 for i in range(MAXN)]
# spf_sieve() 
def factoriazation(x):
    ret = {};
    while x != 1:
        ret[spf[x]] = ret.get(spf[x], 0) + 1;
        x = x//spf[x]
    return ret
    ## this function is useful for multiple queries only, o/w use
    ## primefs function above. complexity O(log n)

## taking integer array input
def int_array():
    return list(map(int, input().strip().split()))
## taking string array input
def str_array():
    return input().strip().split();

#defining a couple constants
MOD = int(1e9)+7;
CMOD = 998244353;
INF = float('inf'); NINF = -float('inf');

################### ---------------- TEMPLATE ENDS HERE ---------------- ###################

n = int(input());
xx,yy,zz = 0,0,0;
for _ in range(n):
    a,b,c = int_array();
    x = a + max(yy, zz);
    y = b + max(xx, zz);
    z = c + max(xx, yy);
    xx, yy, zz = x, y, z;
print(max(xx, yy, zz));

Submission status: Accepted

Solution code:
days = N = int(input())

happiness =  []
for _ in range(N):
    h =  list(map(int , input().split(' ')))
    #print(h)
    happiness.append(h)
    #print(happiness)

# N=  3
# happiness = [[10, 40, 70], 
#             [20, 50, 80], 
#          [30, 60, 90]]

# N=  1
# happiness = [[100, 10, 1]]


#print('dd',happiness)
dp=[]
for _ in range(N):
    dp.append([0,0,0])

# dp = [ [0]*3]*N
#print(dp)

dp[0] = happiness[0]
for index in range(1,len(happiness)):
    #print(dp)
    for acivity in [0,1,2]:
        if acivity ==0:
            max_h =  max(dp[index-1][1],dp[index-1][2])
            dp[index][0] = happiness[index][0]+ max_h
            #print(f'acivity:{acivity},index:{index} , dp:{dp}')

        elif acivity ==1:

            max_h =  max(dp[index-1][2],dp[index-1][0])
            dp[index][1] = happiness[index][1]+ max_h
            #print(f'acivity:{acivity},index:{index} , dp:{dp}')
         
        elif acivity ==2:
            max_h =  max(dp[index-1][1],dp[index-1][0])
            dp[index][2] = happiness[index][2]+ max_h
            #print(f'acivity:{acivity},index:{index} , dp:{dp}')
print(max(dp[N-1]))

Submission status: Accepted

Solution code:
"""
arr = list(map(int, input().split()))
n,k=map(int, input().split())
"""
import math
import sys
# input = sys.stdin.readline

############ ---- Input Functions ---- ############
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

n = int(input())
matrix = []
#Essentially I'm checking every row element with the previous row's opposing elements and seeing the maximum
for _ in range(n):
    temp = inlt()
    matrix.append(temp)
dp = matrix[0]
m = [0]*3
for i in range(n - 1):
    for j in range(3):
        m[j] = max(dp[(j+1)%3]  + matrix[i+1][j], dp[(j+2)% 3]+ matrix[i+1][j])
    dp = m
    m = [0] * 3
    #print('dp:', dp, ' | ', 'm:', m)
print(max(dp))

Submission status: Accepted

Solution code:
"""
arr = list(map(int, input().split()))
n,k=map(int, input().split())
"""
import math
import sys
# input = sys.stdin.readline

############ ---- Input Functions ---- ############
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

n = int(input())
matrix = []
for _ in range(n):
    temp = inlt()
    matrix.append(temp)
dp = matrix[0]
m = [0]*3
for i in range(n - 1):
    for j in range(3):
        m[j] = max(dp[(j+1)%3]  + matrix[i+1][j], dp[(j+2)% 3]+ matrix[i+1][j])
    dp = m
    m = [0] * 3
print(max(dp))