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 sys
input = sys.stdin.readline
I = lambda : list(map(int,input().split()))

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

Solution (Python):
def vacation(n, a):
  dp = [0]*3

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

    
  for i in range(1, n):
    temp = [0]*3
    for j in range(3):
      for k in range(3):
        if(j!=k):
          temp[j] = max(temp[j], dp[k]+a[i][j])
    dp = temp
  return max(dp)
    


n = int(input())
a = []
for i in range(n):
  g = list(map(int, input().split()))
  a.append(g)
print(vacation(n, a))

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

N = int(input())

dp = [[0, 0, 0] for i in range(N)]
dp[0] = [int(i) for i in input().split()]
for i in range(1, N):
    V = [int(i) for i in input().split()]
    dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + V[0]
    dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + V[1]
    dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + V[2]

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

Solution (Python):
n=int(input())
dp=[]
for i in range(n):
    a=[int(i) for i in input().split()]
    dp.append(a)
for i in range(1,n):
    for j in range(3):
        m=0
        for k in range(3):
            if k!=j:
                m=max(dp[i][j]+dp[i-1][k],m)
        dp[i][j]=m
print(max(dp[n-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] = map(int,input().split())

dpa = [a[0]]+[0]*(n-1)
dpb = [b[0]]+[0]*(n-1)
dpc = [c[0]]+[0]*(n-1)
for i in range(1,n):
    dpa[i] = max(dpb[i-1],dpc[i-1]) + a[i]
    dpb[i] = max(dpc[i-1],dpa[i-1]) + b[i]
    dpc[i] = max(dpa[i-1],dpb[i-1]) + c[i]
print(max(dpa[-1],dpb[-1],dpc[-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]*3 for i in range(n)]
dp[0][0] = A[0]
dp[0][1] = B[0]
dp[0][2] = C[0]

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

Solution (Python):

n = int(input())
matrix = []
for _ in range(n):
    matrix.append([int(i) for i in input().split()])
dp = [[0 for i in range(3)] for j in range(n)]
for i in range(3):
    dp[0][i] = matrix[0][i]
for i in range(1,n):
    for j in range(3):
        if j == 0:
            dp[i][j] = max(dp[i-1][j+1],dp[i-1][j+2])+matrix[i][j]
        elif j == 1:
            dp[i][j] = max(dp[i-1][j+1],dp[i-1][j-1])+matrix[i][j]
        else:
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j-2]) + matrix[i][j]
print(max(dp[-1]))

Solution (Python):

def hapi(N,H):
    DP = [[0]*3 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][j] = chmax(DP[i][j],DP[i-1][k]+H[i-1][j])
    return DP

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

if __name__ == '__main__':
    N = int(input())
    H = [[0]*3 for i in range(N)]
    for i in range(N):   
        lst = list(map(int,input().split()))
        H[i] = lst
    ans = hapi(N,H)
    print(max(ans[-1]))

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

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

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

Solution (Python):
def main():
    n, *abc = map(int, open(0).read().split())
    dp = [0] * ((n + 1) * 3)
    a = 0
    b = 1
    c = 2
    for i in range(0, n * 3, 3):
        dp[i + a + 3] = max(dp[i + b], dp[i + c]) + abc[i + a]
        dp[i + b + 3] = max(dp[i + c], dp[i + a]) + abc[i + b]
        dp[i + c + 3] = max(dp[i + a], dp[i + b]) + abc[i + c]
        a,b,c = b,c,a
    
    print(max(dp[-1], dp[-2], dp[-3]))

main()

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

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

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

    elif j==1:
      dp[i+1][j]=max(dp[i][0],dp[i][2])+abc[i+1][j]

    else:
      dp[i+1][j]=max(dp[i][1],dp[i][0])+abc[i+1][j]

print(max(dp[n]))

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

INF = 1 << 20
dp = [[INF] * (n + 1) for _ in range(3)]


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

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

print(max(list(zip(*dp))[n - 1]))

Solution (Python):
def resolve():
	
	N = int(input())
	
	ABC = [
		map(int, input().split())
		for _ in range(N)
	]
	
	Va, Vb, Vc = ABC.pop()
	for _ in range(N-1):
		a, b, c = ABC.pop()
		Va, Vb, Vc = max(Vb, Vc) + a, max(Va, Vc) + b, max(Va, Vb) + c
	print(max(Va, Vb, Vc))
resolve()

Solution (Python):
def resolve():
	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_A = [0] * N
	dp_B = [0] * N
	dp_C = [0] * N
	dp_A[0], dp_B[0], dp_C[0] = A[0], B[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_B[i-1], dp_A[i-1]) + C[i]
	print(max(dp_A[N-1], dp_B[N-1], dp_C[N-1]))
    
resolve()

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

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

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

N=int(input())

abc=[]
kohuku=[]

for k in range(N):
    abc=list(map(int,input().split()))

    if k==0:
        kohuku.append(abc)
    else:
        tuika=[0,0,0]
        tuika[0]=max(kohuku[k-1][1],kohuku[k-1][2])+abc[0]
        tuika[1]=max(kohuku[k-1][0],kohuku[k-1][2])+abc[1]
        tuika[2]=max(kohuku[k-1][0],kohuku[k-1][1])+abc[2]
        kohuku.append(tuika)

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

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

Solution (Python):
from copy import deepcopy
n = int(input())
eff = [list(map(int, input().split())) for _ in range(n)]

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

dp[0] = deepcopy(eff[0])

for i in range(1, n):
    for yi in range(3):
        for ti in range(3):
            if yi != ti:
                dp[i][ti] = max(dp[i][ti], dp[i-1][yi] + eff[i][ti])

print(max(dp[-1]))

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

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

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

from copy import deepcopy

dp[0] = deepcopy(eff[0])

for i in range(1, n):
    for yi in range(3):
        for ti in range(3):
            if yi != ti:
                dp[i][ti] = max(dp[i][ti], dp[i-1][yi] + eff[i][ti])

print(max(dp[-1]))

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


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

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

print(max(dp[-1]))

Solution (Python):
def solve(N,abc):
    dp=[[0]*3 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 range(3):
            dp[i][j]=max(dp[i-1][(j+1)%3]+abc[i][j],dp[i-1][(j+2)%3]+abc[i][j])
    return max([dp[N-1][i] for i in range(3)])

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

Solution (Python):
n = int(input())
abc = [tuple(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):
    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]))

Solution (Python):
def solve(n,a1):
    dp=[[0 for i in range(3)]for j in range(n)]
    dp[0][0]=a1[0][0]
    dp[0][1]=a1[0][1]
    dp[0][2]=a1[0][2]
    for i in range(1,n):
        dp[i][0]=a1[i][0]+max(dp[i-1][1],dp[i-1][2])
        dp[i][1]=a1[i][1]+max(dp[i-1][2],dp[i-1][0])
        dp[i][2]=a1[i][2]+max(dp[i-1][1],dp[i-1][0])
        
    return max(dp[n-1][0],dp[n-1][1],dp[n-1][2])
    


n=int(input())
a1=[[int(i) for i in input().split()]for j in range(n)]

print(solve(n,a1))

Solution (Python):
N = int(input())
abc = [list(map(int,input().split())) for _ in range(N)]
dp = [[0]*3 for _ in range(N)]
a,b,c = abc[0]
dp[0][0] = a
dp[0][1] = b
dp[0][2] = c

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

Solution (Python):




import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)


N = int(input())
abc = int_mtx(N)



dp = np.array([[0,0,0]]*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):
    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[N-1]))

Solution (Python):
n = int(input())
act = []

for i in range(n):
    act.append(list(map(int, input().split())))
    
dp = [[0]*n for i in range(3)]
dp[0][0] = act[0][0]
dp[1][0] = act[0][1]
dp[2][0] = act[0][2]

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

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

dp=list(map(int,input().split()))
for day in range(1,n):
    m=[0]*3
    day_points=list(map(int, input().split()))
    for i in range(3):
        for j in range(3):
            if i!=j:
                 m[i]=max(m[i],day_points[i]+dp[j])
    dp=m
print(max(dp))

Solution (Python):
import sys

stdin = sys.stdin

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

n = ni()
a = [0]*n
b = [0]*n
c = [0]*n
for i in range(n):
  a[i],b[i],c[i] = na()
dpa = [a[0]]+[0]*(n-1)
dpb = [b[0]]+[0]*(n-1)
dpc = [c[0]]+[0]*(n-1)

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

Solution (Python):
n=int(input())
abc=[]
for i in range(n):
    x=tuple(map(int,input().split()))
    abc.append(x)
dp=[[0]*n for _ in range(3)]
for i in range(3):
    dp[i][0]=abc[0][i]

for i in range(1,n):
    x=abc[i]
    for j in range(3):
        dp[j][i]=max(dp[j][i],dp[(j+1)%3][i-1]+x[j],dp[(j+2)%3][i-1]+x[j])

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

Solution (Python):
import sys
def maxcost(li,n):
    dp=[[-1 for j in range(3)] for i in range(n)]
    dp[n-1][0],dp[n-1][1],dp[n-1][2]=li[n-1][0],li[n-1][1],li[n-1][2]
    for i in range(n-2,-1,-1):
        for j in range(3):
            mx=-sys.maxsize
            for k in range(3):
                if j!=k:
                    mx=max(mx,dp[i+1][k]+li[i][j])
            dp[i][j]=mx
    return max(dp[0][0],dp[0][1],dp[0][2])

n=int(input())
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
print(maxcost(li,n))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def maxcost(li,n,i,strt,dp):
    if i==(n-1):
        return li[i][strt]
    mx=-sys.maxsize
    for l in range(3):
        if l!=strt:
            if dp[i+1][l]==-1:
                cost=maxcost(li,n,i+1,l,dp)
                dp[i+1][l]=cost
            else:
                cost=dp[i+1][l]
            mx=max(mx,cost+li[i][strt])
    return mx


n=int(input())
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
dp=[[-1 for j in range(3)] for i in range(n)]
print(max(maxcost(li,n,0,0,dp),maxcost(li,n,0,1,dp),maxcost(li,n,0,2,dp)))

Solution (Python):
days = int(input())
total = [[int(happy) for happy in input().split()]]
for i in range(1, days):
    nums = [int(happy) for happy in input().split()]
    today = [max([total[i-1][1]+nums[0], total[i-1][2]+nums[0]]), max([total[i-1][0]+nums[1], total[i-1][2]+nums[1]]), max([total[i-1][0]+nums[2], total[i-1][1]+nums[2]])]
    total.append(today)
print(max(total[days-1]))

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):
    for y in range(3):
        for t in range(3):
            if y != t:
                dp[i + 1][t] = max(dp[i + 1][t], dp[i][y] + abc[i][t])

print(max(dp[N][:]))

Solution (Python):
def solve(n,d):
    big = float('inf')
    small = float('-inf')
    for s in range(n - 2,-1,-1):
        row = [0,0,0]
        for j in range(3):
            i = s + 1
            if j == 0:
                row[j] = max(d[i][1],d[i][2]) + d[s][j]
            elif j == 1:
                row[j] = max(d[i][0],d[i][2]) + d[s][j]
            else:
                row[j] = max(d[i][1],d[i][0]) + d[s][j]
        d[s] = row

    return max(d[0])


def main():
    t = int(input())
    board = []
    for i in range(t):
        
        d = input()
        d = [int(i) for i in d.split()]
        board.append(d)
    ans = solve(t,board)
    print(ans)
        
main()

Solution (Python):
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


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

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

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

print(max(dp[-1]))

Solution (Python):
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
x,y,z = 0,0,0 
for i in range(N):
  a,b,c = map(int, readline().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,b,c=map(int,input().split())
dp=[[a,b,c]]
for i in range(1,n):
    a,b,c=map(int,input().split())
    el0=max(dp[i-1][1],dp[i-1][2])+a
    el1=max(dp[i-1][0],dp[i-1][2])+b
    el2=max(dp[i-1][0],dp[i-1][1])+c
    dp.append([el0,el1,el2])
print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))

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 j==k:
                continue

            dp[i+1][j]=max(dp[i+1][j],dp[i][k]+happiness[i][j])

print(max(dp[N]))

Solution (Python):
N = int(input().strip())
h = [[0] * (N+1) for i in range(3)]
for i in range(1, N+1):
    a, b, c = map(int, input().split(" "))
    h[0][i] = max(h[1][i-1], h[2][i-1]) + a
    h[1][i] = max(h[0][i-1], h[2][i-1]) + b
    h[2][i] = max(h[0][i-1], h[1][i-1]) + c

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

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

Solution (Python):
import sys
readline = sys.stdin.readline
N = int(readline())
dp = [[0,0,0] for i in range(N)]
dp[0] = list(map(int,readline().split()))
for i in range(1,N):
    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][0],dp[i-1][2]) + b
    dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + c
print(max(dp[N-1]))

Solution (Python):
import sys
readline = sys.stdin.readline
N = int(readline())
dp = [[0]*3 for i in range(N)]
dp[0] = list(map(int,readline().split()))
for i in range(1,N):
    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][0],dp[i-1][2]) + b
    dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + c
print(max(dp[N-1]))

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

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


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

select_action = [[1,2], [0,2], [0,1]]
for i in range(1,N):
    for j in range(3):
        abc1 = select_action[j][0]
        abc2 = select_action[j][1]

        dp[i][j] = max(dp[i-1][abc1], dp[i-1][abc2]) + ABC[i][j]


print(max(dp[-1]))

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

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

print(max(dp[n]))

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


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

    


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

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


dp = [[0 for j in range(3)] for i in range(N)]
for p in range(3):
    dp[0][p] = profit[0][p]


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

Solution (Python):
N = int(input())
a = []
b = []
c = []
for _ in range(N):
    abc = list(map(int, input().split()))
    a.append(abc[0])
    b.append(abc[1])
    c.append(abc[2])

dp = [[a[0], b[0], c[0]]]

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

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

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

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

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

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

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

Solution (Python):
def RA():
    return list(map(int, input().split()))

def solve():
    n = int(input())
    bestEnding = RA()
    for i in range(n - 1):
        a = RA()
        newBestEnding = [
            max(bestEnding[1], bestEnding[2]) + a[0],
            max(bestEnding[0], bestEnding[2]) + a[1],
            max(bestEnding[0], bestEnding[1]) + a[2]
        ]
        bestEnding = newBestEnding
    print(max(bestEnding))


solve()

Solution (Python):
import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    
    a.append(x)
    b.append(y)
    c.append(z)
li=[[-1 for i in range(4)]for j in range(n)]
for i in range(n):
   for j in range(4):
        if i==0:
            if j==0:
                li[i][j]=a[i]
            if j==1:
                li[i][j]=b[i]
            if j==2:
                li[i][j]=c[i]
            if j==3:
                li[i][j] = 0
            continue
        if j==0:
            li[i][j] = max(a[i] + li[i-1][1] ,a[i] + li[i - 1][2])
        if j==1:
            li[i][j] = max(b[i] + li[i - 1][0], b[i] +li[i - 1][2])
        if j==2:
            li[i][j] = max(c[i] + li[i - 1][1], c[i] + li[i - 1][0])
        if j==3:
            li[i][3] = (max(li[i - 1][2],li[i - 1][1], li[i - 1][0]))
print(max(li[n-1]))

Solution (Python):
import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    
    a.append(x)
    b.append(y)
    c.append(z)
li=[[-1 for i in range(3)]for j in range(n)]
li[0][0],li[0][1],li[0][2]=a[0],b[0],c[0]
for i in range(1,n):


        li[i][0] = max(a[i] + li[i-1][1] ,a[i] + li[i - 1][2])

        li[i][1] = max(b[i] + li[i - 1][0], b[i] +li[i - 1][2])

        li[i][2] = max(c[i] + li[i - 1][1], c[i] + li[i - 1][0])
print(max(li[n-1]))

Solution (Python):
def main():
    N = int(input())
    h = {}

    for i in range(N):
        a, b, c = map(int, input().split())
        if i == 0:
            h['a', i] = a
            h['b', i] = b
            h['c', i] = c
        else:
            h['a', i] = a + max(h['b', i-1], h['c', i-1])
            h['b', i] = b + max(h['c', i-1], h['a', i-1])
            h['c', i] = c + max(h['a', i-1], h['b', i-1])

    print(max(h['a', N-1], h['b', N-1], h['c', N-1]))



if __name__ == "__main__":
    main()

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

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

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

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

print(max(dp[n-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][0] = abc[0][0]
dp[0][1] = abc[0][1]
dp[0][2] = abc[0][2]

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

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)

ha=[0 for _ in range(N)]
hb=[0 for _ in range(N)]
hc=[0 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])))