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:
import numpy as np
N = int(input())
h_list = []
for i in range(N):
    h_list.append([i for i in map(int,input().split())])

#print(h_list)

dp = np.zeros((N,3))
dp[0] = h_list[0]
for i in range(1,N):
    dp[i,0] = max(dp[i-1,1], dp[i-1,2]) + h_list[i][0]
    dp[i,1] = max(dp[i-1,0], dp[i-1,2]) + h_list[i][1]
    dp[i,2] = max(dp[i-1,0], dp[i-1,1]) + h_list[i][2]

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

Submission status: Accepted

Solution code:
n=int(input())
A=[]
for i in range(n):
  A.append(list(map(int,input().split())))
  
#dp[i][0,1,2]:=i日目までに最高
dp=[[0,0,0] for i in range(n)]
dp[0]=A[0]
for i in range(1,n):
  dp[i][0]=max(dp[i-1][1]+A[i][0] , dp[i-1][2]+A[i][0])
  dp[i][1]=max(dp[i-1][0]+A[i][1],dp[i-1][2]+A[i][1])
  dp[i][2]=max(dp[i-1][0]+A[i][2],dp[i-1][1]+A[i][2])
print(max(dp[n-1]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
ABC=[tuple(map(int,input().split())) for i in range(n)]
dp=[[0]*3 for i in range(n+1)]
for i in range(n):
  ai,bi,ci = ABC[i]
  dp[i+1][0]=max(dp[i][1],dp[i][2])+ai
  dp[i+1][1]=max(dp[i][0],dp[i][2])+bi
  dp[i+1][2]=max(dp[i][1],dp[i][0])+ci
print(max(dp[n]))

Submission status: Accepted

Solution code:
N = int(input())
dp = [[0,0,0] for i 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[N-1]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
n=ii()
a,b,c=[],[],[]

for i in range(n):
    x,y,z=mii()
    a.append(x)
    b.append(y)
    c.append(z)

dp=[[0]*n for i in range(3)]
dp[0][0],dp[1][0],dp[2][0]=a[0],b[0],c[0]
for i in range(1,n):
    for j in [0,1,2]:
        if j==0:dp[0][i]=max(dp[1][i-1]+a[i],dp[2][i-1]+a[i])
        elif j==1:dp[1][i]=max(dp[0][i-1]+b[i],dp[2][i-1]+b[i])
        elif j==2:dp[2][i]=max(dp[1][i-1]+c[i],dp[0][i-1]+c[i])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())

ab = []
for _ in range(n):
    a, b, c = (int(x) for x in input().split())
    ab.append([a, b, c])

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

print(max(dp[n]))

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

N=int(input())

inp=[]

for _ in range(N):
    try:
        inp.append(list(map(int, input().split())))
    except:
        quit();
        #または、quit(),os.exit()をして止める。

abc=[]

for i in range(N):
    abc.append([0,0,0])

for i in range(N):
    for j in range(3):

        if i-1>=0:
            max_1= -float('inf')
            for k in range(3):
                kou=abc[i - 1][k]
                if k != j and kou >=max_1:
                    max_1 = kou
            abc[i][j] = inp[i][j] + max_1
        else:
            abc[i][j] = inp[i][j]

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

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): #startline--------------------------------------------
    n = int(input())
    abc = [list(map(int,input().split())) for i in range(n)]

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

    print(max(dp[n]))
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
n=int(input())
lst=[]
for i in range(n):
  a,b,c=map(int,input().split())
  lst.append([a,b,c])
C=[]
for i in range(n):
    C.append([float('inf')]*3)
C[0][0]=lst[0][0]
C[0][1]=lst[0][1]
C[0][2]=lst[0][2]
D=[0,1,2]
for i in range(n-1):
  for j in [0,1,2]:
    del D[j]
    C[i+1][j]=max(C[i][D[0]]+lst[i+1][j],C[i][D[1]]+lst[i+1][j])
    D=[0,1,2]
print(max(C[n-1]))

Submission status: Accepted

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

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

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

print(max(dp[-1]))

Submission status: Accepted

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

dp = [[float('inf')] * 3 for _ in range(N+1)]
dp[0] = [0, 0, 0]
for i in range(1, N+1):
    dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + H[i-1][0] 
    dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + H[i-1][1]
    dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + H[i-1][2]
print(max(dp[N]))

Submission status: Accepted

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

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

for i, a in enumerate(a):
  dp_1 = dp[i-1]
  dp[i][0] = max(dp_1[1], dp_1[2]) + a[0]
  dp[i][1] = max(dp_1[0], dp_1[2]) + a[1]
  dp[i][2] = max(dp_1[0], dp_1[1]) + a[2]

print(max(dp[n]))

Submission status: Accepted

Solution code:
n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]
#table A = 0, B = 1, C = 2
dp = [[0] * (3) for i in range(n+1)]

def choice_max(a, b):
    if a > b:
        return a
    else:
        return b


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

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,  = get_nums_l()
abc = list(map(lambda s: list(map(int, s.split())), sys.stdin.readlines()))

dp_a = [0] * (n)
dp_b = [0] * (n)
dp_c = [0] * (n)

dp_a[0] = abc[0][0]
dp_b[0] = abc[0][1]
dp_c[0] = abc[0][2]

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

print(max(dp_a[n-1], dp_b[n-1], dp_c[n-1]))

Submission status: Accepted

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

    dp[0][0] = table[0][0] # a0
    dp[0][1] = table[0][1] # b0
    dp[0][2] = table[0][2] # c0

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

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    dpa=[]
    dpb=[]
    dpc=[]
    dpa.append(a[0])
    dpb.append(b[0])
    dpc.append(c[0])
    for i in range(1,N):
        dpa.append(max(dpb[i-1], dpc[i-1])+a[i])
        dpb.append(max(dpa[i-1], dpc[i-1])+b[i])
        dpc.append(max(dpa[i-1], dpb[i-1])+c[i])
    print(max(dpa[N-1], dpb[N-1], dpc[N-1]))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, a, b, c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

for i in range(3):
  dp[i]=days[0][i]
  
#rint(dp)
for cday in range(1,n):
  pday = cday-1
  t = [0]*3
  for i in range(3):
    max_val = dp[i]
    for j in range(3):
      if i!=j:
        cur_val = dp[j] + days[cday][i]
        if cur_val>max_val:
          max_val=cur_val
    
    t[i] = max_val
  dp=t
  #rint(dp)
  	
print(max(dp))

Submission status: Accepted

Solution code:
# C - Vacation

N = int(input()) # days
happy_list = [] # action cost list
for i in range(N):
    happy_action = list(map(int, input().split()))
    happy_list.append(happy_action)

happy_cost_max = 0 # result prepare
happy_cost_list = [ [0]*3 for i in range(N+1)] # DP list

# DP loop
for i in range(N):
    happy_action = happy_list[i]
    for j in range(3):
        pre_cost = happy_cost_list[i][j]
        for k in range(3):
            if not j==k:
                new_cost = max(happy_cost_list[i+1][k], pre_cost+happy_action[j])
                happy_cost_list[i+1][k] = new_cost

happy_cost_max = max(happy_cost_list[N])
print(happy_cost_max)

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



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


if __name__ == "__main__":
    main() #endline===============================================

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):
    dp[i+1][0] = max(dp[i][1]+ABC[i][0], dp[i][2]+ABC[i][0])
    dp[i+1][1] = max(dp[i][0]+ABC[i][1], dp[i][2]+ABC[i][1])
    dp[i+1][2] = max(dp[i][0]+ABC[i][2], dp[i][1]+ABC[i][2])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())
h = [] #happiness
for i in range(n):
  a_input, b_input, c_input = map(int, input().split())
  h.append([a_input, b_input, c_input])

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 and dp[i][j] < dp[i-1][k] + h[i-1][j]:
        dp[i][j] = dp[i-1][k] + h[i-1][j]

ans = 0
for j in range(3):
  if ans < dp[n][j]:
    ans = dp[n][j]

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

n = int(input())
a = [-1 for _ in range(n)]
b = [-1 for _ in range(n)]
c = [-1 for _ in range(n)]

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

#dp = [['' for _ in range(n)] for _ in range(3)] 
dp = [['' for _ in range(3)] for _ in range(n)] 
dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]

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

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

#print("dp[%d][0] = %d" % (n-1, dp[n-1][0]))
#print("dp[%d][1] = %d" % (n-1, dp[n-1][1]))
#print("dp[%d][2] = %d" % (n-1, dp[n-1][2]))

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from functools import lru_cache
from heapq import heappop,heappush
import time
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
#main

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

Submission status: Accepted

Solution code:
def main(n,lst):
    #dp[N][V]:N日目にVを選択する場合の幸福度の最大値
    dp = [[0]*3 for _ in range(n+1)]
    for i in range(n):
        #i+1日目にA
        a = lst[i][0]
        dp[i+1][0] = max(dp[i][1]+a, dp[i][2]+a)
        #i+1日目にB
        b = lst[i][1]
        dp[i+1][1] = max(dp[i][0]+b, dp[i][2]+b)
        #i+1日目にC
        c = lst[i][2]
        dp[i+1][2] = max(dp[i][0]+c, dp[i][1]+c)
    #dp[n]の最大値
    return max(dp[n])

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

Submission status: Accepted

Solution code:
N  = int(input())

plans = []

for _ in range(N):
  a, b, c = map(int, input().split())
  plans.append((a, b, c))
  
memo = [[0] * (N + 1) for _ in range(3)]

for day, plan in enumerate(plans, 1):
  memo[0][day] = max(memo[1][day - 1], memo[2][day - 1]) + plan[0]
  memo[1][day] = max(memo[0][day - 1], memo[2][day - 1]) + plan[1]
  memo[2][day] = max(memo[0][day - 1], memo[1][day - 1]) + plan[2]
    
print(max(memo[0][N], memo[1][N], memo[2][N]))

Submission status: Accepted

Solution code:
n = int(input())
dp = [[0, 0, 0] for _ in range(n + 1)] #dp[i日目][abcどれをやる]
dp[0][0], dp[0][1], dp[0][2] = 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] + a, dp[i - 1][2] + a)
    dp[i][1] = max(dp[i - 1][2] + b, dp[i - 1][0] + b)
    dp[i][2] = max(dp[i - 1][0] + c, dp[i - 1][1] + c)

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

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)
dp = [[0]*3 for i 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]+A[i],dp[i-1][2]+A[i])
    dp[i][1] = max(dp[i-1][0]+B[i],dp[i-1][2]+B[i])
    dp[i][2] = max(dp[i-1][0]+C[i],dp[i-1][1]+C[i])
print(max(dp[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(0, N):
    for j, value in enumerate(ACTIVITIES[i]):
        DP[i+1][j] = max(DP[i][k] if j != k else 0 for k in range(3)) + value

print(max(DP[N]))

Submission status: Accepted

Solution code:
N = int(input())

a_b_c_list = []

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

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

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            if dp[i+1][k] < dp[i][j] + a_b_c_list[i][k]:
                dp[i+1][k] = dp[i][j] + a_b_c_list[i][k]

print(max(dp[N]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

def EDPC_B_flog():
    """
    5 3
    10 30 40 50 20
    ans 30
    0 20 30 40 30
    
    3 1
    10 20 10
    ans 20
    
    2 100
    10 10
    ans 0
    
    10 4
    40 10 20 70 80 10 20 70 80 60
    ans 40
    0 30 20 30 40 30 20 30 40 40
    """
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    k = min(n-1, k)
    a = np.array(a)
    dp = np.concatenate([np.abs(a - a[0])[:k+1], np.zeros(n-k-1, dtype="int")])
    for i in range(k+1, n):
        dp[i] = np.min(dp[i-k:i] + np.abs(a[i-k:i] - a[i]))
    print(dp[-1])



def EDPC_C_vacation():
    """
    3
    10 40 70
    20 50 80
    30 60 90
    ans 210
    
    1
    100 10 1
    ans 100
    
    7
    6 7 8
    8 8 3
    2 5 2
    7 8 6
    4 6 8
    2 3 4
    7 5 1
    ans 46
    8, 8, 5, 8, 8, 4, 7 -> 48
    8, 8, 5, 7, 8, 3, 7 -> 46
    """
    n = int(input())
    a = np.array([list(map(int, input().split())) for i in range(n)])  
    arr = a
    dp = [[0, 0, 0] for _ in range(n)]
    dp[0] = arr[0]
    for i in range(1, n):
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]
        dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + arr[i][1]
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]
    print (max(dp[-1]))


def EDPC_D_knapsack():
    """
    3 8
    3 30
    4 50
    5 60
    ans 90
    
    5 5
    1 1000000000
    1 1000000000
    1 1000000000
    1 1000000000
    1 1000000000
    ans 5000000000(>int32)
    
    6 15
    6 5
    5 6
    6 4
    6 6
    3 5
    7 2
    ans 17
    """
    N, W = map(int, input().split())
    WV = np.array([tuple(map(int, input().split())) for _ in range(N)], dtype="int64")
    dp = np.zeros(W + 1, dtype="int64")
    for w, v in WV:
        dp[W:w-1:-1] = np.max(np.vstack([dp[W:w-1:-1], dp[W-w::-1] + v]), axis=0)
    print(dp[-1])


def EDPC_E_knapsack():
    """
    3 8
    3 3
    4 5
    5 6
    ans 9
    
    6 15
    6 5
    5 6
    6 4
    6 6
    3 5
    7 2
    ans 17
    
    N<100, W<10*9
    wi<10**9, vi<10**3 
    """
    N, W = map(int, input().split())
    WV = np.array([tuple(map(int, input().split())) for _ in range(N)], dtype="int64")
    Wsum = np.sum(WV[:, 0])
    Vsum = np.sum(WV[:, 1])
    
    dp = np.full(Vsum+1, Wsum, dtype="int64")
    for w, v in WV:
        dp[:Vsum-v+1] = np.min(np.vstack([dp[:Vsum-v+1], dp[v:] - w]), axis=0)
    
    print(dp[dp < W+1].size - 1) # == np.where(dp < W+1)[0][-1]

    
EDPC_C_vacation()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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(max(dp[n-1]))

Submission status: Accepted

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

N = int(input())
A = 0 #直前にAを選んだときの最大値
B = 0 #直前にBを選んだときの最大値
C = 0 #直前にCを選んだときの最大値

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

print (max(A, B, C))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
X = []
for i in range(N):
  X += list(map(int, input().split()))
X = np.array(X).reshape(N, 3)

dp = np.zeros((N+1,4))
for i in range(N):
  for j in range(3):
    for k in range(3):
      if j == k: continue
      dp[i+1,k+1] = max(dp[i+1,k+1], dp[i,j+1]+X[i,k])
print(int(np.max(dp[-1,1:])))

Submission status: Accepted

Solution code:
n = int(input())
h = []
for i in range(n):
  	h.append([int(x) for x in input().split(" ")])

dp = [[-float("inf")] *3 for i in range(n)]
for i in range(3):
  	dp[0][i] = h[0][i]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

# dpテーブル考える
# 最小化するのでINFで設定する
INF = float('inf')
dp = [[-1 for pattern in range(3)] for _ in range(N+1)]

# スタートは0で設定
dp[0][0] = 0
dp[0][1] = 0
dp[0][2] = 0

# 貰うdpで考える
for n in range(1, N+1) :
    # 1行取得する
    day = list(map(int, input().split()))
    
    for i in range(3): 
        for j in range(3):
            # 2日連続同じことはしない
            if (i == j): continue
            dp[n][i] = max(dp[n][i], dp[n-1][j] + day[i])
    
print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())
S = [0,0,0]
for n in range(N):
    a,b,c = [int(i) for i in input().rstrip().split()]
    S = [max(S[1],S[2])+a,max(S[0],S[2])+b,max(S[1],S[0])+c]
    #print(S)
print(max(S))

Submission status: Accepted

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

activities = 3
schedules = [[None for _ in range(activities)] for _ in range(N)]
schedules[0] = vacation[0]

for i in range(1, N):
    for j in range(activities):
        schedules[i][j] = max(schedules[i - 1][(j + 1) % 3], schedules[i - 1][(j + 2) % 3]) + vacation[i][j]

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

Submission status: Accepted

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