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())
arr=[]
res=[]
for i in range(n):
    inp = list(map(int,input().split()))
    arr.append(inp)
res.append(arr[0][0])
res.append(arr[0][1])
res.append(arr[0][2])
for i in range(1,len(arr)):
    x=[-1,-1,-1]
    x[0]=max(res[1],res[2])+arr[i][0]
    x[1]=max(res[0],res[2])+arr[i][1]
    x[2]=max(res[0],res[1])+arr[i][2]
    res=x
print (max(res))

Solution (Python):
n = int(input())
prev_dp=[0]*3
for _ in range(n):
    arr=[]
    a,b,c = list(map(int,input().split()))
    arr.append((a,b,c))
    curr_dp = [0]*3
    for i in range(3):
        for j in range(3):
            if i!=j:
                
                curr_dp[j] = max(curr_dp[j],prev_dp[i] + arr[0][j])
    prev_dp = curr_dp
print(max(prev_dp[0],prev_dp[1],prev_dp[2]))

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

Solution (Python):
import numpy as np

N = int(input())
a = np.zeros((N,3))
for i in range(N):
  a[i][0],a[i][1],a[i][2] = map(int,input().split())

ans = 0


dp = np.zeros((N+1,3))

for i in range(N):
  for x in range(3):
    for y in range(3):
      if x == y:
        continue
      dp[i+1][y] = max(dp[i+1][y],dp[i][x]+a[i][y])


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

Solution (Python):
import math
from functools import lru_cache
def Frog1():
    n = int(input())
    h = list(map(int,input().split(' ')))
    @lru_cache(None)
    def Solve(i):
        if i==n-1:
            return 0
        if i==n-2:
            return abs(h[i]-h[i+1])
        return min(Solve(i+1)+abs(h[i]-h[i+1]),Solve(i+2)+abs(h[i]-h[i+2]))
    dp = [0]*n
    for i in reversed(range(n)):
        if i==n-1:
            dp[i] = 0
        elif i==n-2:
            dp[i] = abs(h[i]-h[i+1])
        else:
            dp[i] = min(dp[i+1]+abs(h[i]-h[i+1]),dp[i+2]+abs(h[i]-h[i+2]))
    print(dp[0])
def Frog2():
    n,k = input().split(' ')
    n,k = int(n),int(k)
    h = list(map(int, input().split(' ')))
    @lru_cache(None)
    def Solve(i):
        if i==n-1:
            return 0
        ans = math.inf
        for j in range(1,k+1):
            new_i = i+j
            if new_i<=n-1:
                ans = min(ans , Solve(new_i)+abs(h[i]-h[new_i]))
            else:
                break
        return ans

    dp = [0]*n
    for i in reversed(range(n)):
        if i==n-1:
            dp[i] = 0
        else:
            ans = math.inf
            for j in range(1,k+1):
                new_i = i+j
                if new_i<=n-1:
                    ans = min(ans,dp[new_i]+abs(h[i]-h[new_i]))
                else:
                    break
            dp[i] = ans
    print(dp[0])

def Vacation():
    n = int(input())
    gain = []
    for i in range(n):
        a = list(map(int,input().split(' ')))
        gain.append(a)
    @lru_cache(None)
    def Solve(i,prevj):
        if i==n:
            return 0
        ans = -math.inf
        m = list({0,1,2} - {prevj})
        for j in m:
            ans = max(ans,Solve(i+1,j)+gain[i][j])
        return ans

    dp = [[0 for j in range(3)] for i in range(n+1)]
    for i in reversed(range(n+1)):
        for prevj in range(3):
            if i!=n:
                ans = -math.inf
                m = m = list({0,1,2} - {prevj})
                for j in m:
                    ans = max(ans,dp[i+1][j]+gain[i][j])
                dp[i][prevj] = ans
    print(max(dp[0]))
Vacation()

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

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

for i in range(1, N):
    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]+a[i][place])


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

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    abc = [0] * N
    for i in range(N):
        abc[i] = list(map(int, input().split()))

    dp = [[0] * 3 for _ in range(N)]
    dp[0] = abc[0]
    for i, (a, b, c) in enumerate(abc[1:], start=1):
        dp_i = dp[i]
        dp_im = dp[i - 1]
        dp_i[0] = max(dp_im[1], dp_im[2]) + a
        dp_i[1] = max(dp_im[0], dp_im[2]) + b
        dp_i[2] = max(dp_im[0], dp_im[1]) + c

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    abc = [0] * N
    for i in range(N):
        abc[i] = list(map(int, input().split()))

    dp = [[0] * 3 for _ in range(N)]
    dp[0] = abc[0]
    for i, (a, b, c) in enumerate(abc[1:], start=1):
        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)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    abc = [0] * N
    for i in range(N):
        abc[i] = list(map(int, input().split()))

    dp = [[0] * 3 for _ in range(N)]
    dp[0] = abc[0]
    for i, (a, b, c) in enumerate(abc[1:], start=1):
        dp_im = dp[i - 1]
        dp[i][0] = max(dp_im[1], dp_im[2]) + a
        dp[i][1] = max(dp_im[0], dp_im[2]) + b
        dp[i][2] = max(dp_im[0], dp_im[1]) + c

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input=sys.stdin.readline
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=[a[0]]+[None]*(n-1)
dpb=[b[0]]+[None]*(n-1)
dpc=[c[0]]+[None]*(n-1)

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

print(max(dpa[-1],dpb[-1],dpc[-1]))

Solution (Python):
import functools
import threading
import sys


def main():
    @functools.lru_cache(maxsize=None)
    def _solve(n, action):
        if n == 1:
            return Utility[1][action]
        else:
            return max(
                _solve(n - 1, a) + Utility[n][action] for a in range(3) if a != action
            )

    def solve(n):
        return max(_solve(n, a) for a in range(3))

    N = int(input())
    Utility = [[None, None, None]]
    for i in range(N):
        Utility.append([int(x) for x in input().split(" ")])
    print(solve(N))


if __name__ == "__main__":

    sys.setrecursionlimit(1024 * 1024 * 2)
    threading.stack_size(128 * 1024 * 1024 * 2)
    threading.Thread(target=main).start()

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

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

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

Solution (Python):
def readinput():
    n=int(input())
    a=[]
    b=[]
    c=[]
    for _ in range(n):
        aa,bb,cc=list(map(int,input().split()))
        a.append(aa)
        b.append(bb)
        c.append(cc)
    return n,a,b,c

def main(n,a,b,c):
    dp=[]
    dp.append([0]*n)
    dp.append([0]*n)
    dp.append([0]*n)

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

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

if __name__=='__main__':
    n,a,b,c=readinput()
    ans=main(n,a,b,c)
    print(ans)

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

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

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

for i in range(N):
    A,B,C=map(int,input().split())
    S[i+1][0]=A
    S[i+1][1]=B
    S[i+1][2]=C

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

DP[0][0]=0
DP[0][1]=0
DP[0][2]=0
DP[1][0]=S[1][0]
DP[1][1]=S[1][1]
DP[1][2]=S[1][2]

if N==1:
    print(max(DP[1]))
    exit()

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

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

pointA = [0]*N; pointB = [0]*N; pointC = [0]*N
pointA[0] = A[0]; pointB[0] = B[0]; pointC[0] = C[0]
for i in range(1, N):
    pointA[i] = max(pointB[i-1], pointC[i-1]) + A[i]
    pointB[i] = max(pointA[i-1], pointC[i-1]) + B[i]
    pointC[i] = max(pointA[i-1], pointB[i-1]) + C[i]
print(max((pointA[N-1], pointB[N-1], pointC[N-1])))

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

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

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

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

Solution (Python):


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


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


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

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

Solution (Python):
N = int(input())
a1, b1, c1 = map(int, input().split())
dp = [[0, 0, 0] for _ in range(N)]
dp[0][0] = a1
dp[0][1] = b1
dp[0][2] = c1
for i in range(1, N):
    a, b, c = map(int, input().split())
    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])

print(max(dp[-1]))

Solution (Python):


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


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


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

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

Solution (Python):
import numpy as np
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 = np.zeros((3, n+1), dtype=np.int)
for i in range(1, n+1):
    dp[0, i] = max(dp[1,i-1]+b[i-1], dp[2,i-1]+c[i-1])
    dp[1, i] = max(dp[0,i-1]+a[i-1], dp[2,i-1]+c[i-1])
    dp[2, i] = max(dp[0,i-1]+a[i-1], dp[1,i-1]+b[i-1])
print(max(dp[:, n]))

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

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

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

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

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

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

Solution (Python):
class Data:
    def __init__(self,n):
        self.n = n
        self.abc = []
        self.dp = [[0,0,0]]

    def input_abc(self):
        for i in range(self.n):
            self.abc.append(list(map(int,input().split())))
    
    def chmax(self,i,j,k):
        a = self.dp[i-1][j] + self.abc[i-1][k]
        b = self.dp[i][k]
        if (a>b):
            self.dp[i][k] = a
        
def main():
    n = int(input())
    data = Data(n)
    data.input_abc()
    for i in range(1,n+1):
        data.dp.append([0,0,0])
        for j in range(3):
            for k in range(3):
                if j != k:
                    data.chmax(i,j,k)
    print(max(data.dp[i]))

if __name__ == "__main__":
    main()

Solution (Python):

N = int(input())
abc = [list(map(int, input().split())) for _ in range(N)]
dp_a, dp_b, dp_c = [0 for _ in range(N)], [0 for _ in range(N)], [0 for _ in range(N)]
dp_a[0], dp_b[0], dp_c[0] = abc[0][0], abc[0][1], abc[0][2]
for i in range(1, N):
    a, b, c = abc[i]
    dp_a[i] = max(dp_b[i-1] + a, dp_c[i-1] + a)
    dp_b[i] = max(dp_a[i-1] + b, dp_c[i-1] + b)
    dp_c[i] = max(dp_a[i-1] + c, dp_b[i-1] + c)
print(max(dp_a[-1], dp_b[-1], dp_c[-1]))

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

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

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

for i in range(N):
    a = list(map(int,input().split()))
    for j in range(3):
        table[i][j] = a[j]


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

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

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

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

for i in range(N):
    a = list(map(int,input().split()))
    for j in range(3):
        table[i][j] = a[j]


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

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

Solution (Python):


from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  


def debug(*x):
    print(*x)


def solve(N, scores):
    last_score = scores[0]
    for i in range(1, N):
        next_score = [
            max(last_score[1], last_score[2]) + scores[i][0],
            max(last_score[2], last_score[0]) + scores[i][1],
            max(last_score[0], last_score[1]) + scores[i][2],
        ]
        last_score = next_score
    return max(last_score)


T1 = """
3
10 40 70
20 50 80
30 60 90
"""


def main():
    N = int(input())
    scores = []
    for i in range(N):
        scores.append(list(map(int, input().split())))
    print(solve(N, scores))


def _test():
    """
    >>> as_input(T1)
    >>> main()
    210
    """
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
N=int(input())
a=0
b=0
c=0
a_list=[]
b_list=[]
c_list=[]
for i in range(N):
    a,b,c=map(int,input().split())
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)
for i in range(1,N):
    a_list[i]=a_list[i]+max(b_list[i-1],c_list[i-1])
    b_list[i]=b_list[i]+max(a_list[i-1],c_list[i-1])
    c_list[i]=c_list[i]+max(a_list[i-1],b_list[i-1])
print(max(a_list[-1],b_list[-1],c_list[-1]))

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

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

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


print(max(dp[-1]))

Solution (Python):
n = int(input())
x, y, z = 0, 0, 0
for i in range(n):
	a, b, c = map(int,input().split())
	x, y, z = max(y, z)+a, max(z, x)+b, max(x, y)+c
print(max(x, y, z))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def solve(a,lvl,prev,dp):
    if (prev,lvl) in dp: return dp[(prev,lvl)]
    if lvl==len(a)-1:
        if prev==0: return max(a[-1][1],a[-1][2])
        if prev==1: return max(a[-1][0],a[-1][2])
        if prev==2: return max(a[-1][0],a[-1][1])
    if prev==-1:
        p=a[0][0]+solve(a,lvl+1,0,dp)
        q=a[0][1]+solve(a,lvl+1,1,dp)
        r=a[0][2]+solve(a,lvl+1,2,dp)
        return max(p,q,r)
    dp[(prev,lvl)]=max(a[lvl][(prev+1)%3]+solve(a,lvl+1,(prev+1)%3,dp),a[lvl][(prev-1)%3]+solve(a,lvl+1,(prev-1)%3,dp))
    return dp[(prev,lvl)]
if __name__=='__main__':
    n=int(input())
    a=[]
    for i in range(n):
        a.append([int(i) for i in input().split()])
    if n==1:
        print(max(a[0]))
    else:
        print(solve(a,0,-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)]

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

for t in range(n):
    x = input().split()
    a[t] = int(x[0])
    dp[t][0] = a[t]
    b[t] = int(x[1])
    dp[t][1] = b[t]
    c[t] = int(x[2])
    dp[t][2] = c[t]



ans = 0

if a and b and c:
    
    
    
    

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

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

print(ans)

Solution (Python):
from functools import lru_cache

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

@lru_cache(maxsize=None)
def dp(i, a):
    if i == 0:
        return action[0][a]
    else:
        return max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]

import sys
sys.setrecursionlimit(1000000)
print(max([dp(n-1,a) for a in range(3)]))

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

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

memo = []
for i in range(n):
    memo.append([-1]*3)

def dp(i, a):
    if i == 0:
        return action[0][a]
    elif memo[i][a] != -1:
        return memo[i][a]
    else:
        memo[i][a] = max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]
        return memo[i][a]

print(max([dp(n-1,a) for a in range(3)]))

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

memo = []
for i in range(n):
    memo.append([-1]*3)

def dp(i, a):
    if i == 0:
        return action[0][a]
    elif memo[i][a] != -1:
        return memo[i][a]
    else:
        memo[i][a] = max(dp(i-1, (a+1)%3), dp(i-1, (a+2)%3)) + action[i][a]
        return memo[i][a]

import sys
sys.setrecursionlimit(1000000)
print(max([dp(n-1,a) for a in range(3)]))

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

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

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

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

res = 0
for i in range(3):
    res = max(res, dp[N][i])

print(res)

Solution (Python):
import sys


import math


input = sys.stdin.readline



def main():


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


if __name__ == "__main__":
    main()

Solution (Python):


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

dp = [[0,0,0] for i in range(0,N,1)]
dp[0] = abc[0]

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

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

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

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

dp = [[0, 0, 0]] * N
dp[0] = abc[0]

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

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

happiness = [[0,0,0] for i in range(N)]

happiness[0] = day[0]

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

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

Solution (Python):
n = int(input())
li = [-1]*n

for i in range(n):
    li[i] = [int(w) for w in input().split()]

dp = [[-1] * 3 for i in range(n)]
dp[0][0] = li[0][0]
dp[0][1] = li[0][1]
dp[0][2] = li[0][2]


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

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

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

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

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

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

    if idx == N:
        dp[idx][prev] = 0
    elif idx == 0:
        v1 = solve(idx + 1, 0) + a[idx]
        v2 = solve(idx + 1, 1) + b[idx]
        v3 = solve(idx + 1, 2) + c[idx]
        dp[idx][prev] = max(v1, v2, v3)

    
    elif prev == 0:
        
        a1 = solve(idx + 1, 1) + b[idx]
        
        a2 = solve(idx + 1, 2) + c[idx]
        dp[idx][prev] = max(a1, a2)

    
    elif prev == 1:
        
        b1 = solve(idx + 1, 0) + a[idx]
        
        b2 = solve(idx + 1, 2) + c[idx]
        dp[idx][prev] = max(b1, b2)

    
    elif prev == 2:
        
        c1 = solve(idx + 1, 0) + a[idx]
        
        c2 = solve(idx + 1, 1) + b[idx]
        dp[idx][prev] = max(c1, c2)

    return dp[idx][prev]

print(solve(0, 0))

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

felicidade = []

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

dp = []

dp.append([felicidade[0][0],felicidade[0][1],felicidade[0][2]])

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


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


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

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n = inp()
dp = [[0]*3 for i in range(n)]
a,b,c = [],[],[]
for _ in range(n):
    aa,bb,cc = ip()
    a.append(aa)
    b.append(bb)
    c.append(cc)
dp[0] = [a[0],b[0],c[0]]
for i in range(1,n):
    dp[i][0] = a[i] + max(dp[i-1][1],dp[i-1][2])
    dp[i][1] = b[i] + max(dp[i-1][0],dp[i-1][2])
    dp[i][2] = c[i] + max(dp[i-1][0],dp[i-1][1])
print(max(dp[-1]))

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

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

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

Solution (Python):
n = int(input())
value = [[0] * 3 for i in range(n)]
for j in range(n):
    value[j] = list(map(int,input().split()))

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

Solution (Python):

n=int(input())
inf=float("inf")
dp=[[-inf for i in range(3)] for j in range(n+1)]
dp[0][0]=0
dp[0][1]=0
dp[0][2]=0
for i in range(n):
    x=list(map(int,input().split()))
    for j in range(3):
        cst_list=[]
        for k in range(3):
            if j!=k:
                cst_list.append(dp[i][k]+x[j])
        dp[i+1][j]=max(cst_list)
print(max(dp[n]))

Solution (Python):
n = int(input())
x = []
for i in range(n):
    l = list(map(int, input().split()))
    x.append(l)
count = 0
dp = [[0 for j in range(3)] for i in range(n)]
dp[0][0], dp[0][1], dp[0][2] = x[0][0], x[0][1], x[0][2]

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


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

Solution (Python):
def main():

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

    primer_puntos = [0] * 3

    for i in range(len(primer_puntos)):
        primer_puntos[i] = actividad[0][i]

    for i in range(1, n):
        siguiente = [0] * 3
        for j in range(3):
            for k in range(3):
                if j != k :
                    siguiente[j] = max(siguiente[j], primer_puntos[k] + actividad[i][j])
        primer_puntos = siguiente

    print(max(primer_puntos))
if __name__ == "__main__":
    main()

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

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

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


dp_a = [0 for _ in range(N)]
dp_b, dp_c = dp_a.copy(), dp_a.copy()
dp_a[0] = abc[0][0]
dp_b[0] = abc[0][1]
dp_c[0] = abc[0][2]

for i in range(N - 1):
    dp_a[i + 1] = max(dp_b[i], dp_c[i]) + abc[i + 1][0]
    dp_b[i + 1] = max(dp_a[i], dp_c[i]) + abc[i + 1][1]
    dp_c[i + 1] = max(dp_a[i], dp_b[i]) + abc[i + 1][2]
print(max(dp_a[-1], dp_b[-1], dp_c[-1]))

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

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

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

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

n_activivies = len(activies[0])

dp = [[0 for _ in range(n_activivies)] for _ in range(N)]
for i in range(n_activivies):
    dp[0][i] = activies[0][i]

for day in range(1, N):
    for prev_activity in range(n_activivies):
        for cur_activity in range(n_activivies):
            if cur_activity != prev_activity:
                dp[day][cur_activity] = max(
                    dp[day][cur_activity], dp[day-1][prev_activity] + activies[day][cur_activity]
                )

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