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())
vals = []
for i in range(n):
    vals.append(list(map(int, input().split())))

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

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


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

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

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

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)

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

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

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

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

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


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


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

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

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

felicidade = []

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

DP = [0,0,0]

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

else:

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


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

    print(max(DP))

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

Solution (Python):
import sys


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


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


def frog_1(arr, n, k):

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

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

    return dp[n]


def vacation(mat, n):

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


    return max(mat[n - 1])








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

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

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

Solution (Python):
import sys


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


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


def frog_1(arr, n, k):

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

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

    return dp[n]


def vacation(mat, n):

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


    return max(mat[n])








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

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

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

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

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

print(max(dp[N]))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

print(max(dp[N]))

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

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


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


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


if n == 0: 
	print 0
	


inf = 2 ** 31

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

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

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

print max(dp[-1])

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

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

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

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

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

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

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

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

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

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

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

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

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

print(max(dp[N]))

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

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

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

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

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

    print(max(a, b, c))

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

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

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

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

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

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

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

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

Solution (Python):

import sys
input = sys.stdin.readline



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


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


def nCr(n, k): 
    if(k > n - k): 
        k = n - k 
    res = 1
    for i in range(k): 
        res = res * (n - i) 
        res = res / (i + 1) 
    return res 


def upper_bound(a, x, lo=0):
    hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x:
            lo = mid+1
        else:
            hi = mid
    return lo


def primefs(n):
    
    primes = {}
    while(n%2 == 0):
        primes[2] = primes.get(2, 0) + 1
        n = n//2
    for i in range(3, int(n**0.5)+2, 2):
        while(n%i == 0):
            primes[i] = primes.get(i, 0) + 1
            n = n//i
    if n > 2:
        primes[n] = primes.get(n, 0) + 1
    
    
    return primes


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


def swap(a,b):
    temp = a
    a = b
    b = temp
    return a,b









def find(x, link):
    p = x;
    while( p != link[p]):
        p = link[p];
    
    while( x != p):
        nex = link[x];
        link[x] = p;
        x = nex;
    return p;




def union(x, y, link, size):
    x = find(x, link)
    y = find(y, link)
    if size[x] < size[y]:
        x,y = swap(x,y)
    if x != y:
        size[x] += size[y]
        link[y] = x


def sieve(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return prime


MAXN = int(1e6 + 5)
def spf_sieve():
    spf[1] = 1;
    for i in range(2, MAXN):
        spf[i] = i;
    for i in range(4, MAXN, 2):
        spf[i] = 2;
    for i in range(3, ceil(MAXN ** 0.5), 2):
        if spf[i] == i:
            for j in range(i*i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i;
    




def factoriazation(x):
    ret = {};
    while x != 1:
        ret[spf[x]] = ret.get(spf[x], 0) + 1;
        x = x//spf[x]
    return ret
    
    


def int_array():
    return list(map(int, input().strip().split()))

def str_array():
    return input().strip().split();


MOD = int(1e9)+7;
CMOD = 998244353;
INF = float('inf'); NINF = -float('inf');



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

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

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











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




dp[0] = happiness[0]
for index in range(1,len(happiness)):
    
    for acivity in [0,1,2]:
        if acivity ==0:
            max_h =  max(dp[index-1][1],dp[index-1][2])
            dp[index][0] = happiness[index][0]+ max_h
            

        elif acivity ==1:

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

Solution (Python):
"""
arr = list(map(int, input().split()))
n,k=map(int, input().split())
"""
import math
import sys



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

n = int(input())
matrix = []

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

Solution (Python):
"""
arr = list(map(int, input().split()))
n,k=map(int, input().split())
"""
import math
import sys



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

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    ABC=[tuple(map(int,input().split())) for i in range(n)]
    dp=[[0,0,0]for _ in range(n+1)] 
    for i in range(n):
        ni=i+1
        dp[ni][0]=max(dp[i][1],dp[i][2])+ABC[ni-1][0]
        dp[ni][1]=max(dp[i][0],dp[i][2])+ABC[ni-1][1]
        dp[ni][2]=max(dp[i][0],dp[i][1])+ABC[ni-1][2]
    print(max(dp[n]))

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    ABC=[tuple(map(int,input().split())) for i in range(n)]
    dp=[[0,0,0]for _ in range(n+1)] 
    for i in range(n):
        ni=i+1
        dp[ni][0]=max(dp[i][1],dp[i][2])+ABC[ni-1][0]
        dp[ni][1]=max(dp[i][0],dp[i][2])+ABC[ni-1][1]
        dp[ni][2]=max(dp[i][0],dp[i][1])+ABC[ni-1][2]
    print(max(dp[n]))

if __name__=='__main__':
    main()

Solution (Python):


n = int(input())

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

dp = [acts[0][0], acts[0][1], acts[0][2]]

for i in range(1, n):
    act = acts[i]
    m = [0] * 3
    
    
    for i in range(3): 
        temp = []
        for j in range(3):
            if i != j:
                temp.append(act[i] + dp[j])
        m[i] = max(temp)
    dp = m
print(max(dp))

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

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  a=[]
  b=[]
  c=[]
  for _ in range(n):
    x,y,z=LI()
    a.append(x)
    b.append(y)
    c.append(z)

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

  return max(dp[0][n],dp[1][n],dp[2][n])


print(main())

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

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

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

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

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

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

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

Solution (Python):
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N = I()
A = [LI() for _ in range(N)]
dp = [[0]*3 for _ in range(N)]
dp[0] = A[0]
for i,j,k in itertools.product(range(1,N),[0,1,2],[0,1,2]):
    if j==k:
        continue
    dp[i][j] = max(dp[i][j],dp[i-1][k]+A[i][j])
print(max(dp[-1]))

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

def chmax(a,b):
    if a >= b:
        return a
    else:
        return b
dp = [[0]*(3) for _ in range(N+2)]
for i in range(N):
    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] + h[i][k])

print(max(dp[N]))

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import bisect
import numpy as np

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

dp = np.ones((N, 3))*-float("inf")

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

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

Solution (Python):
n=int(input())
l=[[None for i in range(3) ] for i in range(n)]
for i in range(n):
    a,b,c=list(map(int,input().split()))
    l[i][0]=a
    l[i][1]=b
    l[i][2]=c
l1=[[None for i in range(3) ] for i in range(n)]
a=l1[0][0]=l[0][0]
b=l1[0][1]=l[0][1]
c=l1[0][2]=l[0][2]
q=max(a,b,c)
for i in range(1,n):
    a=l1[i][0]=l[i][0]+max(l1[i-1][1],l1[i-1][2])
    b=l1[i][1]=l[i][1]+max(l1[i-1][0],l1[i-1][2])
    c=l1[i][2]=l[i][2]+max(l1[i-1][1],l1[i-1][0])
    if q<max(a,b,c):
        q=max(a,b,c)
print(q)

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

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

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

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

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())
A=[0]*(N+1)
B=[0]*(N+1)
C=[0]*(N+1)

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

for i in range(1,N+1):
  a,b,c=map(int,input().split())
  A[i]=a
  B[i]=b
  C[i]=c


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

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000) 

def main():
    input = sys.stdin.readline  
    N = int(input())
    act_list = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        act_list.append((a, b, c))

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

    for i in range(1, N):
        for j in range(3):
            dp[i][j] = max(dp[i-1][(j+1) % 3], dp[i-1][(j+2) % 3]) + act_list[i][j]
    print(max(dp[N-1]))

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
action = []
for i in range(n):
    action.append(list(map(int, input().split())))
DP = [[0, 0, 0] for i in range(n + 1)]

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

print(max(DP[-1]))

Solution (Python):
import itertools
n = int(input())
lst = [[0,0,0]]

for _ in range(n):
  l = list(map(int, input().split()))
  lst.append(l)
  
hp = [[0] * 3 for _ in range(n+1)]

plst = list(itertools.permutations([_ for _ in range(3)], 2))

for _ in range(0, n):
    for i in plst:
      hp[_+1][i[1]] = max(hp[_][i[0]] + lst[_+1][i[1]], hp[_+1][i[1]])

print(max(hp[n]))

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

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

    
    dp[0] = abc[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]+abc[i][j])

    print(max(dp[-1]))

if __name__ == '__main__':
    main()

Solution (Python):


n = int(input())
h_list = [[int(x) for x in input().split()] for i in range(n)]

dp = [[float("-Inf")] * n for i in range(3)]

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

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

Solution (Python):
n = int(input())
happiness = [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 i == 0:
                dp[i + 1][k] = happiness[i][k]
            elif j == k:
                continue
            else:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][k] + happiness[i][j])

print(max(dp[-1]))

Solution (Python):
n = int(input())
happiness = [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 i == 0:
                dp[i + 1][k] = happiness[i][k]
            elif j == k:
                continue
            else:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][k] + happiness[i][j])

print(max(dp[-1]))