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

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

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

cost = h[-1]

for day in range(N-2, -1, -1):
    today_cost = []
    today_cost.append(h[day][0] + max(cost[1], cost[2]))
    today_cost.append(h[day][1] + max(cost[0], cost[2]))
    today_cost.append(h[day][2] + max(cost[0], cost[1]))
    cost = today_cost

print(max(cost))

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

cost = h[-1]

for day in range(N-2, -1, -1):
    today_cost = [0 for i in range(3)]
    today_cost[0] = h[day][0] + max(cost[1], cost[2])
    today_cost[1] = h[day][1] + max(cost[0], cost[2])
    today_cost[2] = h[day][2] + max(cost[0], cost[1])
    cost = today_cost

print(max(cost))

Solution (Python):

def dp_solve(dp0, dp1, dp2, n):
    for i in range(1, n):
        dp0[i] = max(dp1[i-1], dp2[i-1])+ax[i]
        dp1[i] = max(dp0[i-1], dp2[i-1])+bx[i]
        dp2[i] = max(dp0[i-1], dp1[i-1])+cx[i]
    return max(dp0[-1], dp1[-1], dp2[-1])


if __name__ == "__main__":
    n = int(input())
    ax = []
    bx = []
    cx = []
    for i in range(n):
        a, b, c = map(int, input().split())
        ax.append(a)
        bx.append(b)
        cx.append(c)

    dp0 = [ax[0]]+[0]*(n-1)
    dp1 = [bx[0]]+[0]*(n-1)
    dp2 = [cx[0]]+[0]*(n-1)
    print(dp_solve(dp0, dp1, dp2, n))

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


def solve():

    dp = [[0]*3 for _ in range(n)] 
    for i in range(n):
        if i == 0:
            dp[i] = [h[0][j] for j in range(3)]
            continue
        for j in range(3):
            dp[i][j] = max([dp[i-1][jk] for jk in ({0,1,2} - {j}) ]) + h[i][j]
            
    print(max(dp[n-1]))

solve()

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
mo=998244353
n=int(input())
dp=list(map(int,input().split()))
for i in range(1,n):
    a,b,c=list(map(int,input().split()))
    dp=[a+max(dp[1],dp[2]),b+max(dp[0],dp[2]),c+max(dp[0],dp[1])]
print(max(dp))

Solution (Python):
N = int(input())
a = [0 for _ in range(N)]
b = [0 for _ in range(N)]
c = [0 for _ in range(N)]

for i in range(N):
    a[i], b[i], c[i] = map(int, input().split(" "))
happy = [[0 for _ in range(3)] for _ in range(N)]
for i in range(N):
    if i == 0:
        happy[i][0] = a[i]
        happy[i][1] = b[i]
        happy[i][2] = c[i]
    else:
        happy[i][0] = max(happy[i-1][1]+a[i], happy[i-1][2]+a[i])
        happy[i][1] = max(happy[i-1][0]+b[i], happy[i-1][2]+b[i])
        happy[i][2] = max(happy[i-1][0]+c[i], happy[i-1][1]+c[i])
print(max(happy[-1]))

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret






























N = read_a_int()
ABC = read_matrix(N)


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


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

for i in range(N - 1):

    for j in range(3):
        dp[i+1][j] = max([dp[i][k] + ABC[i+1][j] for k in range(3) if k != j])

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

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret












N = read_a_int()


















ABC = read_matrix(N)


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


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

for i in range(N - 1):

    for j in range(3):
        iterlist = [0, 1, 2]
        iterlist.remove(j)
        dp[i+1][j] = max([dp[i][k] + ABC[i+1][j] for k in iterlist])


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

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

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

for i, abc in enumerate(ABC):
  if i == 0:
    for j in range(3):
      DP[i][j] = abc[j]
  else:
    for j in range(3):
      DP[i][j] = max(DP[i-1][k] + abc[j] for k in range(3) if j != k)

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

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

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

for step in range(len(points)):
    
    for act in range(3):
        for next_act in range(3):
            if act == next_act:
                continue
            dp[step + 1][next_act] = max(points[step][next_act]+dp[step][act], dp[step + 1][next_act])


print(max(dp[N]))

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

dp = [[0, 0, 0] for i 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]+a[i][k])

print(max(dp[-1]))

Solution (Python):
n = int(input())
ans = [0] * 3

for i in range(n):
    t1 = list(map(int, input().split()))
    t2 = [0] * 3
    for i in range(3):
        for j in range(3):
            if i != j:
                t2[j] = max(t2[j], ans[i] + t1[j])
    ans = t2
print(max(ans))

Solution (Python):
n = int(input())
ans = [0] * 3

for i in range(n):
    t1 = list(map(int, input().split()))
    t2 = [0] * 3
    for i in range(3):
        for j in range(3):
            if i != j:
                t2[j] = max(t2[j], ans[i] + t1[j])
    ans = t2
print(max(ans))

Solution (Python):
n=int(input())
dp=[[0 for i in range(n+1)] for j in range(3)]
for i in range(1,n+1):
    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],dp[1][n],dp[2][n]))

Solution (Python):
N = int(input())
Action = [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):
        dp[i + 1][(j + 1) % 3] = max(dp[i + 1][(j + 1) % 3], dp[i][j] + Action[i][j])
        dp[i + 1][(j + 2) % 3] = max(dp[i + 1][(j + 2) % 3], dp[i][j] + Action[i][j])

print(max(dp[-1]))

Solution (Python):
n=int(input())
dp=[[0 for i in range(n+1)] for j in range(3)]
for i in range(1,n+1):
  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],dp[1][n],dp[2][n]))

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

dp = [row for row in abc]
for i in range(1,N):
    for a in range(3):
        dp[i][a] = abc[i][a] + max(dp[i-1][:a]+dp[i-1][a+1:])
print(max(dp[-1]))

Solution (Python):
from collections import Counter
from functools import reduce
import fractions
import math
import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]  
def LF(): return [float(x) for x in sys.stdin.readline().split()]  
def LS(): return sys.stdin.readline().split()  
def MI(): return map(int, sys.stdin.readline().split())  
def II(): return int(sys.stdin.readline())  
def IS(): return input()  
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):  
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):  
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


n = II()
happiness = [LI() for _ in range(n)]
dp = [[0 for i in range(3)] for i in range(n+1)]
for i in range(n):
    dp[i+1][0] = max(dp[i][1]+happiness[i][0], dp[i][2]+happiness[i][0])
    dp[i+1][1] = max(dp[i][0]+happiness[i][1], dp[i][2]+happiness[i][1])
    dp[i+1][2] = max(dp[i][0]+happiness[i][2], dp[i][1]+happiness[i][2])
P(max(dp[-1]))

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

scores = []
for i in range(0, n):
  a, b, c = [int(elem) for elem in input().split()]
  if not scores == []:
    prev_a, prev_b, prev_c = scores[-1] 
    if max(prev_b, prev_c) == prev_b:
      if max(prev_a, prev_c) == prev_a:
        if max(prev_a, prev_b) == prev_b:
          scores.append((a + prev_b, b + prev_a, c + prev_b))
        else:
          scores.append((a + prev_b, b + prev_a, c + prev_a))
      else:
        if max(prev_a, prev_b) == prev_b:
          scores.append((a + prev_b, b + prev_c, c + prev_b))
        else:
          scores.append((a + prev_b, b + prev_c, c + prev_a))
    else:
      if max(prev_a, prev_c) == prev_a:
        if max(prev_a, prev_b) == prev_b:
          scores.append((a + prev_c, b + prev_a, c + prev_b))
        else:
          scores.append((a + prev_c, b + prev_a, c + prev_a))
      else:
        if max(prev_a, prev_b) == prev_b:
          scores.append((a + prev_c, b + prev_c, c + prev_b))
        else:
          scores.append((a + prev_c, b + prev_c, c + prev_a))      
  else:
    scores.append((a, b, c))

print(max(scores[-1]))

Solution (Python):
if __name__ == '__main__':
    days = int(input())
    acts = []
    happiness = [[0, 0, 0] for _ in range(days)]
    for day in range(days):
        acts.append(list(map(int, input().split())))

    for day in range(days):
        if day == 0:
            happiness[day] = [acts[0][0], acts[0][1], acts[0][2]]
        else:
            for act in range(3):
                happiness[day][act] = max(happiness[day - 1][(act + 1) % 3] + acts[day][act],
                                          happiness[day - 1][(act + 2) % 3] + acts[day][act])
    print(max(happiness[days - 1]))

Solution (Python):

n = int(input())
lista = []
for i in range(n):
    arr = list(map(int,input().split()))
    lista.append(arr)

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

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

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

ans = 0
for i in range(3):
    ans = max(ans ,dp[n-1][i])
print(ans)

Solution (Python):
import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nms = lambda: map(str, sys.stdin.readline().split())
nl = lambda: list(nm())

n = ni()
l = [nl() for i in range(n)]
dp = [[-1, -1, -1] for i in range(n + 1)]
dp[0] = [0, 0, 0]
dp[1] = [l[0][0], l[0][1], l[0][2]]

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

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

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

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

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

print(max(dp[-1]))

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

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

Solution (Python):
N = int(input())
ABC = [[int(i) for i in input().split()]for _ in range(N)]

dp = [[0]*4 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][j] = max(dp[i+1][j], dp[i][k]+ABC[i][j])
print(max(dp[N]))

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a,b,c = map(int,input().split())

dpa = [a]+[0]*(n-1)
dpb = [b]+[0]*(n-1)
dpc = [c]+[0]*(n-1)

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

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

dp = [[0]*3 for i 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[-1]))

Solution (Python):
import sys

n = int(sys.stdin.readline())

arr = [[]] * 3
dp = [0] * 3

for i in range(n):
    arr = list(map(int, sys.stdin.readline().split()))
    new_dp = [0] * 3
    for j in range(3):

        for k in range(3):

            if j != k:

                new_dp[k] = max(new_dp[k], dp[j] + arr[k])
    dp = new_dp

print(max(dp))

Solution (Python):
N = int(input())
dp = [[0] * 3 for j in range(N)]
d = []
for i in range(N):
    a, b, c = map(int, input().split())
    if i == 0:
        dp[0][0] = a
        dp[0][1] = b
        dp[0][2] = c
    else:
        d.append((a, b, c))


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

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

Solution (Python):


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

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

    for i in range(0, N):
        todo = tuple(map(int, input().split()))

        for k in range(3):
            dp[k][i+1] = max(dp[j][i] for j in range(3) if j != k) + todo[k]

    print(max(dp[k][N] for k in range(3)))


if __name__ == '__main__':
    main()

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,0,0] for i in range(N+1)]
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):
def main():
  N = int(input())
  ABC = [[int(i) for i in 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:
          continue
        dp[i+1][k] = max(dp[i+1][k], dp[i][j]+ABC[i][k])
  print(max(dp[N]))

if __name__ == "__main__":
  main()

Solution (Python):
import sys
import numpy as np


input = sys.stdin.readline


vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]


arr_happiness_a = np.array([lst_happiness[i][0] for i in range(vacation)])
arr_happiness_b = np.array([lst_happiness[i][1] for i in range(vacation)])
arr_happiness_c = np.array([lst_happiness[i][2] for i in range(vacation)])


dp_a = np.zeros(vacation, dtype=int)
dp_b = np.zeros(vacation, dtype=int)
dp_c = np.zeros(vacation, dtype=int)


dp_a[0] = arr_happiness_a[0]
dp_b[0] = arr_happiness_b[0]
dp_c[0] = arr_happiness_c[0]

for i in range(1, vacation):
    dp_a[i] += max(dp_b[i-1], dp_c[i-1]) + arr_happiness_a[i]
    dp_b[i] += max(dp_a[i-1], dp_c[i-1]) + arr_happiness_b[i]
    dp_c[i] += max(dp_a[i-1], dp_b[i-1]) + arr_happiness_c[i]

ans = max(dp_a[vacation-1], dp_b[vacation-1], dp_c[vacation-1])
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**5+10)


input = sys.stdin.readline


vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]



dp = [[0 for i in range(3)] for j in range(vacation+1)]


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


def rec(i):
    
    for j in range(3):
        if dp[i][j] > 0:
            break
        
        
        if i == 0:
            dp[i][j] = 0
            break
        
        
        res = 0
        for k in range(3):
            if j == k:
                continue
            res = chmax(res, rec(i-1)[k] + lst_happiness[i-1][k])
            
            dp[i][j] = res
    
    return dp[i]

ans = rec(vacation)
ans = max(ans)
print(ans)

Solution (Python):
import sys


input = sys.stdin.readline


vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]



dp = [[0 for i in range(3)] for j in range(vacation+1)]

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









for i in range(1, vacation+1):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i][k] = chmax(dp[i][k], dp[i-1][j] + lst_happiness[i-1][k])


ans = 0
for i in range(3):
    ans = chmax(ans, dp[vacation][i])

print(ans)

Solution (Python):
import sys


input = sys.stdin.readline


vacation = int(input())
lst_happiness = [list(map(int, input().split())) for i in range(vacation)]



dp = [[0 for i in range(3)] for j in range(vacation+1)]

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









for i in range(vacation):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + lst_happiness[i][k])


ans = 0
for i in range(3):
    ans = chmax(ans, dp[vacation][i])

print(ans)

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

Solution (Python):

import sys

def main():
	N = int(input())
	hpp = []
	for _ in range(N):
		a, b, c = map(int, input().split())
		hpp.append((a, b, c))
			
	DP = [[-1 for _ in range(3)] for _ in range(N+1)]
	DP[0][0] = 0
	DP[0][1] = 0
	DP[0][2] = 0
	
	for i, val in enumerate(hpp):
		a, b, c = val
		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][2], DP[N][0], DP[N][1]))
	
if __name__ == "__main__":
	main()

Solution (Python):
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
cost=[[0 for i in range(3)]for j in range(n+1)]
for i in range(n):
    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            cost[i+1][k]=max(cost[i+1][k],cost[i][j]+a[i][k])
print(max(cost[n]))

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

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

idx = [[1,2],[2,0],[0,1]]

for i in range(3):
    dp[0][i] = a[0][i]
    
for i in range(1,N):
    for j in range(3):
        dp[i][j] = max(dp[i-1][idx[j][0]],dp[i-1][idx[j][1]])+a[i][j]
    
print(max(dp[N-1]))

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

n=int(input())
a,b,c=map(int,input().split())
for _ in range(n-1):
    a1, b1, c1 = map(int, input().split())
    a,b,c=a1+max(b,c),b1+max(a,c),c1+max(a,b)
print(max(a,b,c))

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

n=int(input())
a,b,c=map(int,input().split())
for i in range(n-1):
    a1, b1, c1 = map(int, input().split())
    a,b,c=a1+max(b,c),b1+max(a,c),c1+max(a,b)
print(max(a,b,c))

Solution (Python):
n=int(input())
a,b,c=map(int,input().split())
for i in range(n-1):
    a1, b1, c1 = map(int, input().split())
    a,b,c=a1+max(b,c),b1+max(a,c),c1+max(a,b)
print(max(a,b,c))

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

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

Solution (Python):
N = int(input())
A = [[int(i) for i in input().split()] for _ in range(N)]

x = y = z = 0
for a, b, c in A:
  x, y, z = max(y, z)+a, max(x,z)+b, max(x,y)+c
print(max(x, y, z))

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

x = y = z = 0
for a,b,c in A:
  x,y,z = max(y,z)+a,max(x,z)+b,max(x,y)+c
print(max(x,y,z))

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

Solution (Python):
n=int(input())
action=[list(map(int,input().split())) for _ 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]+action[i-1][j])

print(max(happy[n]))

Solution (Python):
N = int(input())
abcs = [tuple(map(int, input().split())) for i in range(N)]
dp = [[0, 0, 0] for i in range(N)]

for i, abc in enumerate(abcs):
    if i == 0:
        dp[i][0] = abc[0]
        dp[i][1] = abc[1]
        dp[i][2] = abc[2]
    else:
        dp[i][0] = max(dp[i-1][1] + abc[0], dp[i-1][2] + abc[0])
        dp[i][1] = max(dp[i-1][0] + abc[1], dp[i-1][2] + abc[1])
        dp[i][2] = max(dp[i-1][0] + abc[2], dp[i-1][1] + abc[2])

print(max(dp[-1]))

Solution (Python):
def solve():
  N = int(input())
  ABC = [[int(i) for i in input().split()] for i in range(N)]
  dp = [[0, 0, 0] for i in range(N)]
  dp[0] = ABC[0]
  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]
  return max(dp[N - 1])

print(solve())

Solution (Python):
n = int(input())
dp = [[0 for _ in range(3)] for __ in range(n)]

for i in range(n):
  tmp = list(map(int, input().split()))
  if i == 0:
    dp[i] = tmp
    continue
  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] + tmp[k])

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

Solution (Python):
N = int(input())
u = [[0 for i in range(3)] for j in range(N)]
for i in range(N):
    u[i] = [int(j) for j in input().split()]

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

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

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

Solution (Python):
n = int(input())
dp = [[0, 0, 0] for _ in range(n)]
dp[0][0], dp[0][1], dp[0][2] = map(int, input().split())

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

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

Solution (Python):



def main():
    
    
    
    
    
    
    
    
    
    
    import sys
    N = int(sys.stdin.readline()[:-1])
    data = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    
    dp = [[0, 0, 0] for _ in range(N)]
    dp[0] = data[0]
    for i in range(1, N):
        dp[i][0] = max(dp[i-1][1:]) + data[i][0]
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + data[i][1]
        dp[i][2] = max(dp[i-1][:2]) + data[i][2]
    print(max(dp[N-1]))

main()

Solution (Python):
import math
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right


def s_inpl(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
INF = float("inf")

N = int(input())
act = []
for _ in range(N):
    act_i = inpl()
    act.append(act_i)

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

ans = 0
for k in range(3):
    ans = max(ans, dp[N][k])

print(ans)

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

Solution (Python):
N = int(input())
L = []
for _ in range(N):
    l = list(map(int,input().split()))
    L.append(l)
dp = [[0 for _ in range(3)] for _ in range(N+1)]

for day in range(N):
    for i in range(3):
        for new in range(3):
            if i != new:
                dp[day+1][new] = max(dp[day][i]+L[day][new] ,dp[day+1][new])
ans = 0
for i in range(3):
    ans = max(ans,dp[N][i])
print(ans)

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

print(max(dp[-1]))

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

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

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

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

print(max(dp[N]))

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
H=[tuple(map(int,input().split())) for _ in range(n)]
DP=[[0]*3 for _ in range(n)]
DP[0]=H[0]
for i in range(1,n):
    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            DP[i][j]=max(DP[i][j],DP[i-1][k]+H[i][j])
print(max(DP[-1]))

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

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

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

Solution (Python):
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] = 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][1], dp[i][0])
print(max(dp[n]))

Solution (Python):
n = int(input())
aa, bb, cc = [], [], []
hs = []
for i in range(n):
  a, b, c = map(int, input().split())
  hs.append({})
  hs[i]['a'] = a
  hs[i]['b'] = b
  hs[i]['c'] = c

dp = []
dp.append({})
for x in 'abc':
  dp[0][x] = 0

for i in range(1, n+1):
  dp.append({})
  for current in 'abc':
    vals = []
    for before in 'abc':
      if current == before:
        continue
      vals.append(dp[i-1][before] + hs[i-1][current])
    dp[i][current] = max(vals)

print(max(dp[n].values()))

Solution (Python):
N = int(input())
util = [[int(i) for i in input().split()] for _ in range(N)]
"""
memo = [0 for _ in range(N + 1)]
def dp(i, u, rem_i):
    if i == N:
        return u
    elif i == 0:
        ret = max(dp(i + 1, u+util[i][0], 0), dp(i + 1, u+util[i][1], 1), dp(i + 1, util[i][2], 2))
    else:
        index = list({0, 1, 2} - {rem_i})
        ret = max(dp(i + 1, u+util[i][index[0]], index[0]), dp(i + 1, u+util[i][index[1]], index[1]))
    memo[i] = ret
    print(memo)
    return ret

print(dp(0, 0, 3))
"""

memo = [{} for i in range(N)]
for i in range(3):
    memo[-1][i] = util[-1][i]
for i in range(N-2, -1, -1):
    for j in range(3):
        memo[i][j] = util[i][j] + max(memo[i+1][k] for k in range(3) if j != k)
print(max(memo[0].values()))