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.

Solution (Python):


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) 

    
EDPC_C_vacation()

Solution (Python):
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]))

Solution (Python):
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]))

Solution (Python):
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]))

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
A = 0 
B = 0 
C = 0 

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

Solution (Python):
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:])))

Solution (Python):
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]))

Solution (Python):
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]))

Solution (Python):
N = int(input())



INF = float('inf')
dp = [[-1 for pattern in range(3)] for _ in range(N+1)]


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


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

Solution (Python):
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(max(S))

Solution (Python):
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]))

Solution (Python):
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]))

Solution (Python):
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]))

Solution (Python):
n = int(input())

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

print(max(dp[-1]))

Solution (Python):
N = int(input())
ABC = []

for n in range(N):
  ABC.append(list(map(int, input().split())))

import numpy as np
ABC = np.array(ABC)


hp=np.zeros((N,3),dtype=int)
hp[0] = ABC[0]

for n in range(1,N):
  for c in range(3): 
    
    if c == 0:
      hp[n][0] = max(hp[n-1][1],hp[n-1][2]) + ABC[n][0]
    elif c == 1:
      hp[n][1] = max(hp[n-1][0],hp[n-1][2]) + ABC[n][1]
    elif c == 2:
      hp[n][2] = max(hp[n-1][0],hp[n-1][1]) + ABC[n][2]


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

Solution (Python):
n=int(input())
a=[]
b=[]
c=[]
for i in range(n):
    x,y,z=map(int,input().split())
    a.append(x)
    b.append(y)
    c.append(z)

INF=float("inf")
dpa=[-INF]*n
dpb=[-INF]*n
dpc=[-INF]*n
dpa[0]=a[0]
dpb[0]=b[0]
dpc[0]=c[0]

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

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

INF=float("inf")
dpa=[-INF]*n
dpb=[-INF]*n
dpc=[-INF]*n
dpa[0]=a[0]
dpb[0]=b[0]
dpc[0]=c[0]

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

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

INF=float("inf")
dpa=[-INF]*n
dpb=[-INF]*n
dpc=[-INF]*n
dpa[0]=a[0]
dpb[0]=b[0]
dpc[0]=c[0]

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

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

INF=float("inf")
dpa=[-INF]*n
dpb=[-INF]*n
dpc=[-INF]*n
dpa[0]=a[0]
dpb[0]=b[0]
dpc[0]=c[0]

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

Solution (Python):

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

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

happy_list = [[0, 0, 0] for i in range(n)]

happy_list[0][0] = mtx[0][0]
happy_list[0][1] = mtx[0][1]
happy_list[0][2] = mtx[0][2]

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

print(max(happy_list[-1]))

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

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[N-1]))

Solution (Python):
import numpy as np
N = int(input())
ABC = np.zeros([N, 3])
for i in range(N):
    ABC[i] = list(map(int, input().split()))

dp = np.zeros([N, 3])
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(int(max(dp[N-1])))

Solution (Python):
def retMax(a,b):
  if a>=b:
    return a
  else:
    return b

n = int(input())
r = []
dpList = [ [0] * 3 for x in range(n)]

for i in range(n):
  r.append(list(map(int,input().split())))

dpList[0][0] = r[0][0]  
dpList[0][1] = r[0][1]  
dpList[0][2] = r[0][2]  

for s in range(1,n):
  
  dpList[s][0] = retMax(dpList[s-1][1]+r[s][0],dpList[s-1][2]+r[s][0])
  
  dpList[s][1] = retMax(dpList[s-1][0]+r[s][1],dpList[s-1][2]+r[s][1])
  
  dpList[s][2] = retMax(dpList[s-1][0]+r[s][2],dpList[s-1][1]+r[s][2])

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    vn = vk = vn_k = 1
    for i in range(1, n+1):
        vn = vn * i % modp
        if i == k:
            vk = vn
        if i == n-k:
            vn_k = vn
    return vn * get_inv(vk, modp) * get_inv(vn_k, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp



def main():
    N = ii()
    sa,sb,sc = 0,0,0
    for _ in range(N):
        a,b,c=mis()
        nsa = max(sb,sc)+a
        nsb = max(sc,sa)+b
        nsc = max(sa,sb)+c
        sa,sb,sc = nsa,nsb,nsc
    print(max(sa,sb,sc))

main()

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

ex = [[1,2], [0,2], [0,1]]
dp = [abc[0]] + [[0]*3 for _ in range(n-1)]

for i in range(n-1):
    for j in range(3):
        dp[i+1][j] = abc[i+1][j] + max([dp[i][k] for k in ex[j]])

print(max(dp[-1]))

Solution (Python):

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


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

dp_a[0] = a[0]
dp_b[0] = b[0]
dp_c[0] = c[0]

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

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

Solution (Python):



import numpy

def main():
  n = int(input())
  actions = numpy.array([[float(x) for x in input().strip().split()] for _ in range(n)]).T
  happiness = numpy.zeros((2, 3))
  for i in range(n):
    id = i%2
    happiness[id, 0] = max(happiness[id-1, 1]+actions[1, i], happiness[id-1, 2]+actions[2, i])
    happiness[id, 1] = max(happiness[id-1, 0]+actions[0, i], happiness[id-1, 2]+actions[2, i])
    happiness[id, 2] = max(happiness[id-1, 0]+actions[0, i], happiness[id-1, 1]+actions[1, i])
  print(int(max(happiness[(n-1)%2])))
  pass

if __name__=='__main__':
  main()

Solution (Python):
N = int(input())
T = [list(map(int, input().split())) for i in range(N)]
dp = [[0 for i in range(3)] for j in range(N+1)]
dp[1] = T[0]
for i in range(2,N+1):
    dp[i][0] = max(dp[i-1][1]+T[i-1][0],dp[i-1][2]+T[i-1][0])
    dp[i][1] = max(dp[i-1][0]+T[i-1][1],dp[i-1][2]+T[i-1][1])
    dp[i][2] = max(dp[i-1][0]+T[i-1][2],dp[i-1][1]+T[i-1][2])
print(max(dp[-1]))

Solution (Python):
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(1, n):
    for j in range(3):
        tmp = 0
        for k in range(3):
            if j != k:
               tmp = max(tmp, dp[i-1][k] + abc[i][j])
        dp[i][j] = tmp

print(max(dp[-1]))

Solution (Python):
N = int(input())
ha = [[0]*3 for _ in range(N+1)]
for i in range(N):
  a = list(map(int, input().split()))
  for k in range(3):
    ha[i+1][k] = a[k]

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

Solution (Python):
N = int(input())
ha = [[0]*3 for _ in range(N+1)]
for i in range(N):
  a = list(map(int, input().split()))
  for k in range(3):
    ha[i+1][k] = a[k]

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

Solution (Python):
n = int(input())
a = [0]*n
b = [0]*n
c = [0]*n

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

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

for i in range(n):
  if i == 0:
    dp_a[i], dp_b[i], dp_c[i] = a[i], b[i], c[i]
  else:
    dp_a[i] = max([a[i]+dp_b[i-1], a[i]+dp_c[i-1]])
    dp_b[i] = max([b[i]+dp_a[i-1], b[i]+dp_c[i-1]])
    dp_c[i] = max([c[i]+dp_b[i-1], c[i]+dp_a[i-1]])
print(max([dp_a[n-1], dp_b[n-1], dp_c[n-1]]))

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

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

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

    dp = [[0, 0, 0] 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):
        for j in [0, 1, 2]:
            score = max(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + ABC[i][j]
            if score > dp[i][j]:
                dp[i][j] += score

    print(max(dp[-1]))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    readline = sys.stdin.readline

    n = int(readline())

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

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

    print(max(dp[n]))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    readline = sys.stdin.readline

    n = int(readline())

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

    print(max(dp[n]))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())

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

Solution (Python):
import sys
input = sys.stdin.readline

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

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

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

import numpy as np
act = np.array(act)
act = np.concatenate([[[0]*3], act])  


dp = np.zeros([N+1, 3], dtype='int')

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

Solution (Python):
N = int(input())
value = [[0]*3 for _ in range(N+1)]
for i in range(N):
  a = list(map(int, input().split()))
  for k in range(3):
    value[i+1][k] = a[k]

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

Solution (Python):

import fractions 
import functools 

def pin(type=int):
    return map(type,input().split())

INF = float("inf")

def Flog_1(N,H):
    dp=[INF for i in range(N)]
    dp[0]=0  
    dp[1]=abs(H[1]-H[0])
    for i in range(2,N):
        hop1=dp[i-1]+abs(H[i-1]-H[i]) 
        hop2=dp[i-2]+abs(H[i-2]-H[i]) 
        
        dp[i]=hop1 if hop1<hop2 else hop2
    return dp
def Flog_1_Another(N,H):
    dp=[INF for i in range(N)]
    dp[0]=0  
    for i in range(0,N):
        for k in [1,2]:
            if i+k <N:
                dp[i+k]=min(dp[i+k],dp[i]+abs(H[i+k]-H[i]))
    return dp

def Flog_2(N,K,H):
    dp=[INF for i in range(N)]
    dp[0]=0  
    for i in range(1,N):
        temp = INF
        for k in range(1,K+1):
            if i-k < 0:break
            else:
                temp = min(temp,(dp[i-k]+abs(H[i-k]-H[i])))
                
        dp[i]=temp
    return dp
def Flog_2_Another(N,K,H):
    dp=[INF for i in range(N)]
    dp[0]=0  
    for i in range(0,N):
        for k in range(1,K+1):
            if i+k <N:
                dp[i+k]=min(dp[i+k],dp[i]+abs(H[i+k]-H[i]))
    return dp
def Flog_2_YETAnother(N,K,H):
    if N == 1:
        return 0
    else:
        map(min,[Flog_2_YETAnother(N-i,K,H) for i in range(1,N+1)])
 
def vacation(N):
   
    dp=[[0]*3 for i in range(N)]
    dp[0]=list(pin())
    for i in range(1,N):
       
        temp=list(pin())
       
        dp[i][0]= max(dp[i-1][1],dp[i-1][2])+temp[0]
        dp[i][1]= max(dp[i-1][2],dp[i-1][0])+temp[1]
        dp[i][2]= max(dp[i-1][0],dp[i-1][1])+temp[2]
        
    return max(dp[-1])

N,=pin()
 

print(vacation(N))

Solution (Python):
N = int(input())
choices = []
for i in range(N):
  choices.append(list(map(int, input().split())))
dp = [[0, 0, 0] for _ in range(N+1)]
for i, choice in enumerate(choices):
  if i==0:
    dp[0]=choice
    continue
  else:
    for j in range(3):
      dp[i][j] = max(dp[i-1][j-1]+choice[j], dp[i-1][j-2]+choice[j])
print(max(dp[N-1]))

Solution (Python):
N = int(input())
choices = []
for i in range(N):
  choices.append(list(map(int, input().split())))
dp = [[0, 0, 0] for _ in range(N+1)]
for i, choice in enumerate(choices):
  if i==0:
    dp[0]=choice
    continue
  else:
    for j in range(3):
      dp[i][j] = max(dp[i-1][j-1]+choice[j], dp[i-1][j-2]+choice[j])
print(max(dp[N-1]))

Solution (Python):
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 _ in range(n)]
dp[0] = [a[0], b[0], c[0]]

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

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

Solution (Python):
n = int(input())
A = []
B = []
C = []
for i in range(n):
    a,b,c = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    
dp = [[0 for i in range(3)] for j in range(n)]

dp[0][0] = A[0]
dp[0][1] = B[0]
dp[0][2] = C[0]

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

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

Solution (Python):
n = int(input())
a=[0] * (n+1)
b=[0] * (n+1)
c=[0] * (n+1)
aux = [ [0] * 5 for _ in range(n+1)]

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

a = [int(i) for i in a]
b = [int(i) for i in b]
c = [int(i) for i in c]

aux[1][1]=a[1]
aux[1][2]=b[1]
aux[1][3]=c[1]



for i in range(2,n+1):
    aux[i][1]+=max(aux[i-1][2],aux[i-1][3])+a[i]
    aux[i][2]+=max(aux[i-1][1],aux[i-1][3])+b[i]
    aux[i][3]+=max(aux[i-1][1],aux[i-1][2])+c[i]

print(max(aux[n][1],aux[n][2],aux[n][3]))

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

Solution (Python):
n=int(input())
if n==1:
    a,b,c=map(int,input().split())
    print(max(a,b,c))
else:
    a=[]
    b=[]
    c=[]
    dp=[[0 for i in range(3)] for j in range(n)]
    temp=n
    i=1
    flag=0
    while n!=0:
        a,b,c=map(int,input().split())
        if n==temp:
            dp[0][0]=a
            dp[0][1]=b
            dp[0][2]=c
        else:
            dp[i][0]=max(dp[i-1][1]+a,dp[i-1][2]+a)
            dp[i][1]=max(dp[i-1][0]+b,dp[i-1][2]+b)
            dp[i][2]=max(dp[i-1][0]+c,dp[i-1][1]+c)
            i+=1
        n-=1

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

Solution (Python):
n = int(raw_input())

mat = []
for i in range(n):
    mat.append(map(int,raw_input().split()))
    
dp = [0,0,0]

for day in range(n):
    ndp = [0,0,0]
    data = mat[day]
    
    for i in range(3):
        for j in range(3):
            if i != j:
                ndp[j] = max(ndp[j], dp[i]+data[j])
    dp = ndp
print max(dp)

Solution (Python):
n = int(input())

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

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

dp[0][0] = data[0][0]
dp[0][1] = data[0][1]
dp[0][2] = data[0][2]

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

print(max(dp[-1]))

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

DP = []
for i in range(N+1):
    DP.append([0]*3)

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



ans = max(DP[N])
print(ans)

Solution (Python):
n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
dp = [[0 for i in range(3)] for i in range(n+10)]


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

Solution (Python):
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

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

a, b, c = na()
dp[0][0], dp[0][1], dp[0][2] = a, b, c

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

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

Solution (Python):
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

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

a, b, c = na()
dp[0][0], dp[0][1], dp[0][2] = a, b, c

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

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

Solution (Python):

N = int(input())

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

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

dp[0][0] = activity[0][0]
dp[0][1] = activity[0][1]
dp[0][2] = activity[0][2]

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

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

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

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

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

print(max(dp[-1]))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = [0] * N
b = [0] * N
c = [0] * N
for i in range(N):
    a[i],b[i],c[i] = [int(i) for i in input().split()]
dp = [[0] * 3 for _ in range(N)]
dp[0] = [a[0],b[0],c[0]]
for i in range(1,N):
    dp[i][0] = a[i] + max(dp[i-1][1],dp[i-1][2])
    dp[i][1] = b[i] + max(dp[i-1][0],dp[i-1][2])
    dp[i][2] = c[i] + max(dp[i-1][0],dp[i-1][1])
dp[N-1].sort()
print(dp[N-1][-1])

Solution (Python):
n = int(input())






dp=[[-1]*3 for _ in range(n+1)]

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

w_L = [[0,0,0]]

for i in range(n):
    tmp = list(map(int,input().split()))
    w_L.append(tmp)


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

print(max(dp[n]))

Solution (Python):
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 _ in range(n)]
dp[0] = [a[0], b[0], c[0]]

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

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

Solution (Python):
n=int(input())
ma,mb,mc=0,0,0
for _ in range(n):
  a,b,c=map(int,input().split())
  x,y,z=ma,mb,mc
  ma=a+max([y,z])
  mb=b+max([z,x])
  mc=c+max([x,y])
print(max([ma,mb,mc]))

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines







def main():
	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][2], dp[i][0]) + b
		dp[i+1][2] = max(dp[i][0], dp[i][1]) + c
		
	print(max(dp[n][0],dp[n][1],dp[n][2]))
	
	
	
if __name__ == "__main__":
	main()