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

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

for i in range(n):
    for now in range(3):
        for prev in range(3):
            if now == prev:
                continue

            dp[i+1][now] = max(dp[i+1][now], dp[i][prev] + abc[i][now])

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

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

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]+a[i], dpc[i-1]+a[i])
  dpb[i] = max(dpa[i-1]+b[i], dpc[i-1]+b[i])
  dpc[i] = max(dpa[i-1]+c[i], dpb[i-1]+c[i])
  
print(max(dpa[-1], dpb[-1], dpc[-1]))

Solution (Python):
import sys
def main():
    N=int(sys.stdin.readline())
    a=[]
    for _ in [0]*N:a.append(list(map(int,sys.stdin.readline().split())))
    dp=[[0,0,0] for _ in [0]*N]
    dp[0]=a[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]])+a[i][j]
    print(max(dp[N-1]))
if __name__=='__main__':main()

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

dp=[0]*n
dp[0]=list(map(int,input().split()))

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

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

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

l = [[None] * 3 for _ in range(N)]
for i in range(N):
    l[i] = (ABC[i])

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

for i in range(1, N):
    dp_p = sorted(dp[i - 1])
    a = dp_p[-1]
    b = dp[i - 1].index(a)
    for j in range(3):
        if j == b:
            dp[i][j] = dp_p[-2] + l[i][j]
        else:
            dp[i][j] = a + l[i][j]
ans = max(dp[-1])
print(ans)

Solution (Python):
def main():
    n, factor = getInputs()

    points = []
    for i in range(n):
        points.append([0] * 3)

    
    for pile in range(3):
        points[0][pile] = factor[0][pile]

    for day in range(1, n):
        points[day][0] = max(points[day - 1][1], points[day - 1][2]) + factor[day][0]
        points[day][1] = max(points[day - 1][0], points[day - 1][2]) + factor[day][1]
        points[day][2] = max(points[day - 1][0], points[day - 1][1]) + factor[day][2]

    print(max(points[-1]))

def getInputs():
    n = int(input())

    factor = []
    for i in range(n):
        factor.append(tuple(map(lambda x: int(x), input().split())))

    return n, factor

main()

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

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

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

Solution (Python):
n = int(input())
memo = []
memo1 = [0,0,0]
for i in range(n):
    s = input().split()
    s = [int(s[j]) for j in range(3)]
    if i==0:
        memo = s
    else:
        memo1[0] = max(memo[1],memo[2])+s[0]
        memo1[1] = max(memo[0],memo[2])+s[1]
        memo1[2] = max(memo[0],memo[1])+s[2]
        memo = [1*memo1[j] for j in range(3)]
print(max(memo))

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

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

    dp = [0]*(n+1)
    for x in range(n+1):
        dp[x] = [0, 0, 0]

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

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

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    
    
    

    
    N = int(input())

    dp = []

    for i in range(N):
        vals = list(map(int, input().split()))
        happy = {}
        for j in range(3):
            if dp:
                happy[j] = max([dp[i-1][k] + vals[j]
                                for k in range(3) if k != j])
            else:
                happy[j] = vals[j]
        dp.append(happy)

    print(max(dp[-1].values()))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

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

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

dp = [[0, 0, 0]] * (N+1)

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

Solution (Python):
N = int(input())
a = []*N
b = []*N
c = []*N
for _ in range(N):
    A, B, C = map(int, input().split())
    a.append(A)
    b.append(B)
    c.append(C)

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

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

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

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


for i in range(N):
    for j in range(3):
        if i == 0:
            dp[i][j] = array[i][j]
            continue
        for k in range(3):
            if j != k:
                sum = dp[i - 1][k] + array[i][j]
                dp[i][j] = sum if sum > dp[i][j] else dp[i][j]

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

Solution (Python):
n = int(input())
dp = [[0]*3 for _ 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(n-1):
    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[n-1]))

Solution (Python):
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] = list(map(int, input().split()))

dp = []

for i in range(n):
    dp.append([0, 0, 0])


dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]

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

print(max(dp[-1]))

Solution (Python):
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
lst=[[0,0,0]]
for i in range(a):
  x,y,z=mi()
  lst.append([max(lst[i][1],lst[i][2])+x,max(lst[i][0],lst[i][2])+y,max(lst[i][1],lst[i][0])+z])
print(max(lst[-1]))

Solution (Python):


n=int(input())

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

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

ABC=[[0,0,0]]



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

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

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

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

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

    for i in range(n):
        a, b, c = x[i]
        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)

    res = max(dp[-1])

    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

n = int(input())
a, b, c = [], [], []

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

for i in range(n):
    v1, v2, v3 = map(int, input().split())
    a.append(v1)
    b.append(v2)
    c.append(v3)

dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]

for idx in range(1, n):
    
    a1 = dp[idx - 1][1] + a[idx]
    a2 = dp[idx - 1][2] + a[idx]
    dp[idx][0] = max(a1, a2)

    
    b1 = dp[idx - 1][0] + b[idx]
    b2 = dp[idx - 1][2] + b[idx]
    dp[idx][1] = max(b1, b2)

    
    c1 = dp[idx - 1][0] + c[idx]
    c2 = dp[idx - 1][1] + c[idx]
    dp[idx][2] = max(c1, c2)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

n = int(input())
a, b, c = [], [], []

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

for i in range(n):
    v1, v2, v3 = map(int, input().split())
    a.append(v1)
    b.append(v2)
    c.append(v3)

dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]

def solve(idx, ptn):
    if dp[idx][ptn] > 0:
        return dp[idx][ptn]

    
    if ptn == 0:
        if idx == 0:
            return a[0]
        a1 = solve(idx - 1, 1) + a[idx]
        a2 = solve(idx - 1, 2) + a[idx]
        dp[idx][0] = max(a1, a2)
        return dp[idx][0]

    
    if ptn == 1:
        if idx == 0:
            return b[0]
        b1 = solve(idx - 1, 0) + b[idx]
        b2 = solve(idx - 1, 2) + b[idx]
        dp[idx][1] = max(b1, b2)
        return dp[idx][1]

    
    if ptn == 2:
        if idx == 0:
            return c[0]
        c1 = solve(idx - 1, 0) + c[idx]
        c2 = solve(idx - 1, 1) + c[idx]
        dp[idx][2] = max(c1, c2)
        return dp[idx][2]

ans1 = solve(n-1, 0)
ans2 = solve(n-1, 1)
ans3 = solve(n-1, 2)
print(max(ans1, ans2, ans3))

Solution (Python):


LI = lambda: list(map(int, input().split()))


N = int(input())
ABC = [LI() for _ in range(N)]


def main():
    dp = [[0] * 3 for _ in range(N + 1)]
    for i in range(1, N + 1):
        a, b, c = ABC[i - 1]
        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][0], dp[i - 1][1])
    ans = max(dp[-1])
    print(ans)



if __name__ == "__main__":
    main()

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

n = int(input());
arr = [];
for i in range(n):
    tarr = get_array();
    arr.append(tarr);
dp = [[0,0,0] for i in range(n)];
dp[0][0]=arr[0][0];
dp[0][1]=arr[0][1];
dp[0][2]=arr[0][2];
for i in range(1,n):
    for j in range(3):
        dp[i][j]=arr[i][j]+max(dp[i-1][(j+1)%3],dp[i-1][(j+2)%3]);
print(max(dp[n-1]));

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

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

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

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

Solution (Python):

n = int(input())
vac = []
for i in range(n):
    vac.append(tuple(map(int,input().split())))

dp1 = [vac[0][0]] + [0] * (n-1)
dp2 = [vac[0][1]] + [0] * (n-1)
dp3 = [vac[0][2]] + [0] * (n-1)

for i in range(1,n):
    dp1[i] = max((vac[i][0]+dp2[i-1]),(vac[i][0]+dp3[i-1]))
    dp2[i] = max((vac[i][1]+dp1[i-1]),(vac[i][1]+dp3[i-1]))
    dp3[i] = max((vac[i][2]+dp2[i-1]),(vac[i][2]+dp1[i-1]))
    
    
print(max(dp1[-1],dp2[-1],dp3[-1]))

Solution (Python):
import sys

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

N = int(readline())
m = map(int, read().split())
dp = [0, 0, 0]
for a, b, c in zip(m, m, m):
    dp = [max(dp[1], dp[2]) + a, max(dp[0], dp[2]) + b, max(dp[0], dp[1]) + c]

print(max(dp))

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

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


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

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

for i in range(n - 1):
    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] + a[i + 1][j])
            else:
                continue
                
print(max(max(dp[n - 1][0], dp[n - 1][1]),dp[n - 1][2]))

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

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

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

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

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

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


for i in range(1, N+1):
  for place in range(3):
    for place_y in range(3):
      if (place == place_y): continue
      dp[i][place] = max(
        dp[i][place],
        dp[i-1][place_y] + H[i-1][place]
      )

print(max(dp[-1]))

Solution (Python):
n = int(input())
hap = []
for i in range(n):
    l = [int(x) for x in input().split()]
    hap += [l]
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0] = hap[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])+hap[i][j]
print(max(dp[-1]))

Solution (Python):
import sys
INF = 10**18

if __name__ == "__main__":
    n = int(input())
    h = []
    for i in range(n):
        a,b,c = map(int,input().split())
        h.append([a,b,c])
    dp = [[0]*3 for i in range(n)]
    for i in range(n):
        if i == 0:
            dp[i][0] = h[i][0]
            dp[i][1] = h[i][1]
            dp[i][2] = h[i][2]
        else:
            for j in range(3):
                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][0] + h[i][1],dp[i-1][2] + 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, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*3)

dp = [[0]*3 for _ in range(N)]
for i, (a, b, c) in enumerate(A):
    if i == 0:
        dp[i] = [a, b, c]
        continue

    da, db, dc = dp[i-1]
    dp[i][0] = max(dp[i][0], max(db, dc)+a)
    dp[i][1] = max(dp[i][1], max(dc, da)+b)
    dp[i][2] = max(dp[i][2], max(da, db)+c)

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

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

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

Solution (Python):






import sys
input = sys.stdin.readline


import heapq 
import copy
import math
import decimal











 



 

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

def pr_list(a):
	print(*a, sep=" ")
def main():
	
	tests = 1
	mod = 998244353
	limit = 10**18
	ans = 0
	for test in range(tests):
		n = inp()
		val = []
		for i in range(n):
			a = inlt()
			val.append(a)
		dp = [[0 for i in range(n)] for j in range(3)]
		dp[0][0] = val[0][0]
		dp[1][0] = val[0][1]
		dp[2][0] = val[0][2]
		for i in range(1,n):
			for j in range(3):
				dp[j][i] = val[i][j] + max(dp[(j+1)%3][i-1],dp[(j+2)%3][i-1])
		print(max(dp[0][n-1] , dp[1][n-1]  , dp[2][n-1] ))
if __name__== "__main__":
	main()

Solution (Python):
def i():
	return int(input())
def i2():
	return map(int,input().split())
def s():
	return str(input())
def l():
	return list(input())
def intl():
	return list(int(k) for k in input().split())

n = i()
h = [intl() for _ in range(n)]

dp = [[0]*3 for _ in range(n)]
for i in range(n):
    if i == 0:
        dp[i][0] = h[i][0]
        dp[i][1] = h[i][1]
        dp[i][2] = h[i][2]
    else:
        for j in range(3):
           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][0] + h[i][1], dp[i-1][2] + h[i][1] )
           dp[i][2] = max( dp[i-1][0] + h[i][2], dp[i-1][1] + h[i][2] )
print( max(dp[n-1]) )

Solution (Python):
N=int(input())
dp=[0]*3
flag=0
for _ in range(N):
    a=list(map(int,input().split()))
    if flag==0:
        dp[0]=a[0]
        dp[1]=a[1]
        dp[2]=a[2]
        flag=1
    else:
        a0=dp[0]
        a1=dp[1]
        a2=dp[2]
        dp[0]=max(a[0]+a1,a[0]+a2)
        dp[1]=max(a[1]+a0,a[1]+a2)
        dp[2]=max(a[2]+a0,a[2]+a1)
print(max(dp))

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):
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    n = I()
    a = [Intl() for _ in range(n)]
    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:pass
                else:
                    dp[i+1][k] = max(dp[i+1][k],dp[i][j] + a[i][k])
    print(max(dp[-1]))

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

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

Solution (Python):
n=int(input())
dp=[0]*3
for i in range(n):
    val=[int(x) for x in input().split()]
    temp=[0]*3
    for p in range(3):
        for k in range(3):
            if p!=k:
                temp[k]=max(temp[k],dp[p]+val[k])
        
    dp=temp[:]

print(max(dp))

Solution (Python):
N = int(input())
abc = [[int(j) for j in input().split()] for i in range(N)]
dp = [[0] * 3]
for i in range(N):
    dp += [[max([dp[-1][p] + abc[i][n] for p in range(3) if p != n]) for n in range(3)]]
print(max(dp[-1]))

Solution (Python):
N = int(input())
abc = [[int(j) for j in input().split()] for i in range(N)]
dp = [[0] * 3]
for day in range(N):
    dp += [[max([dp[-1][p] + abc[day][n] for p in range(3) if p != n]) for n in range(3)]]
print(max(dp[-1]))

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

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


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):
INF = float('inf')
def f_dp(x, a, b, c):
    dp = [[0] * (x + 1) for i in range(3)]
    dp[0][0] = a[0]
    dp[1][0] = b[0]
    dp[2][0] = c[0]

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

    return dp

if __name__ == "__main__":
    n = int(input())
    abc = [map(int, input().split()) for _ in range(n)]
    a, b, c = [list(i) for i in zip(*abc)]
    dp = f_dp(n, a, b, c)

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

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

print(max(dp[n]))

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

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

Solution (Python):

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


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

N=int(input())

for i in range(N):
    L=list(map(int,input().split()))
    for j in range(len(L)):
        S[i][j]=L[j]

for i in range(N):
    for j in range(3):
        for k in range(3):
            if j==k:
                pass
            else:
                if DP[i+1][k]<DP[i][j]+S[i][k]:
                    DP[i+1][k]=DP[i][j]+S[i][k]

ans=0
for j in range(3):
    if ans<DP[N][j]:
        ans=DP[N][j]
print(ans)

Solution (Python):
from sys import stdin
import numpy as np

n = int(stdin.readline().strip())
abc_lst = []

for i in range(n):
  abc = [int(x) for x in stdin.readline().strip().split()]
  abc_lst.append(abc)
  
hapiness_mat = np.zeros((n, 3))
hapiness_mat[0] = abc_lst[0]

for i in range(1, n):
  hapiness_mat[i][0] = max(hapiness_mat[i-1][1],hapiness_mat[i-1][2]) + abc_lst[i][0]
  hapiness_mat[i][1] = max(hapiness_mat[i-1][0],hapiness_mat[i-1][2]) + abc_lst[i][1]
  hapiness_mat[i][2] = max(hapiness_mat[i-1][0],hapiness_mat[i-1][1]) + abc_lst[i][2]
  
print(int(max(hapiness_mat[-1])))

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

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

Solution (Python):
n = int(input())
abc  = [[], [], []]

for i in range(n): 
    tmp_1, tmp_2, tmp_3 = map(int, input().split())
    abc[0].append(tmp_1)
    abc[1].append(tmp_2)
    abc[2].append(tmp_3)


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


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

print(max(dp[-1]))

Solution (Python):
n = int(input())
abc  = [[], [], []]

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


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

print(max(dp[-1]))

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N = int(readline().rstrip())
L = []
for _ in range(N):
    a, b, c = map(int, readline().split())
    L.append((a, b, c))


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

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

da = db = dc = 0

for i in range(n):
    a, b, c = map(int, input().split())
    da, db, dc = max(db, dc) + a, max(da, dc) + b, max(da, db) + c
print(max(da, db, dc))

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

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

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

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

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

Solution (Python):


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

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

Solution (Python):



def main():
    N = int(input())
    dp = [[0]*3 for i 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]+a, dp[i-1][2]+a, dp[i][0])
        dp[i][1] = max(dp[i-1][2]+b, dp[i-1][0]+b, dp[i][1])
        dp[i][2] = max(dp[i-1][0]+c, dp[i-1][1]+c, dp[i][2])

    print(max(dp[N]))

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
aa = []
bb = []
cc = []
aDP = [0]*N
bDP = [0]*N
cDP = [0]*N
for i in range(N):
    a,b,c = [int(x) for x in input().split()]
    aa.append(a)
    bb.append(b)
    cc.append(c)
aDP[0] = aa[0]
bDP[0] = bb[0]
cDP[0] = cc[0]
for i in range(1,N):
    aDP[i] = max(bDP[i-1] + aa[i],cDP[i-1]+aa[i])
    bDP[i] = max(aDP[i-1] + bb[i],cDP[i-1]+bb[i])
    cDP[i] = max(bDP[i-1] + cc[i],aDP[i-1]+cc[i])
print(max(max(aDP[N-1],bDP[N-1]),cDP[N-1]))

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