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


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase




from bisect import bisect_right as br
from bisect import bisect







BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)







mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  


def out(var): sys.stdout.write(str(var))  


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  


def testcase(t):
    for p in range(t):
        solve()


from random import randint

from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count

def isvalid(n,i):
    if i>=n or i<0:
        return False
    return True


def solve():
    n=int(inp())
    ar=[]
    for i in range(n):
        ar.append(lis())
    dp=[[-1]*3 for _ in range(n+5)]
    dp[0][0]=ar[0][0]
    dp[0][1] = ar[0][1]
    dp[0][2] = ar[0][2]
    for i in range(1,n):
        for j in range(3):
            s=0
            for k in range(3):
                if k!=j:
                    s=max(s,dp[i-1][k]+ar[i][j])
            dp[i][j]=s
    print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))




solve()

Solution (Python):
def maxPoints(a,b,c,N):
    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][1],dp[i-1][0])
    
    return max(dp[N-1])

n = int(input())
a = [0] * n
b = a.copy()
c = a.copy()
for i in range(n):
    a[i],b[i],c[i] = map(int,input().split())
print(maxPoints(a,b,c,n))

Solution (Python):
def maxPoints(a,b,c,N):
    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][1],dp[i-1][0])
    
    return max(dp[N-1])

n = int(input())
a = [0] * n
b = a.copy()
c = a.copy()
for i in range(n):
    a[i],b[i],c[i] = map(int,input().split())
print(maxPoints(a,b,c,n))

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

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

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
dp=l.copy()
for i in range(n-1):

	dp1=dp.copy()
	l=list(map(int,input().split()))
	for j in range(3):
		ans=float('-inf')
		for k in range(3):
			if(j!=k):
				ans=max(ans,l[j]+dp[k])
		dp1[j]=ans
	dp=dp1.copy()
print(max(dp))

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

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

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

print(max(dp[N]))

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

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

happy[0] = [int(x) for x in input().split()]

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

ans = max(happy[N - 1])

print(ans)

Solution (Python):

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

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

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

Solution (Python):
N = int(input())
a, b, c = [0], [0], [0]
for i in range(N):
    a_i, b_i, c_i = map(int, input().split())
    a.append(a_i)
    b.append(b_i)
    c.append(c_i)
DP = [[0 for j in range(3)] for i in range(N+1)]
for days in range(1, N+1):
    for ABC in range(3):
        if ABC == 0:
            DP[days][ABC] = max(DP[days-1][1], DP[days-1][2]) + a[days]
        elif ABC == 1:
            DP[days][ABC] = max(DP[days-1][0], DP[days-1][2]) + b[days]
        elif ABC == 2:
            DP[days][ABC] = max(DP[days-1][0], DP[days-1][1]) + c[days]
print(max(DP[N]))

Solution (Python):
def solve(n,a,b,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):
        for j in range(3):
            if j == 0:
                dp[i][j] = max(dp[i-1][1],dp[i-1][2]) + a[i]
            if j == 1:
                dp[i][j] = max(dp[i-1][0],dp[i-1][2]) + b[i]
            if j == 2:
                dp[i][j] = max(dp[i-1][0],dp[i-1][1]) + c[i]

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








if __name__ == '__main__':
    n = int(input())
    a = []
    b = []
    c = []
    for i in range(n):
        t1,t2,t3 = map(int,input().split())
        a.append(t1)
        b.append(t2)
        c.append(t3)

    solve(n,a,b,c)

Solution (Python):


n = int(input())


memo = [[-1] * 3 for i in range(n)]
a = []
b = []
c = []


def dp(i):
    if i != 0:
        memo[i][0] = max(memo[i - 1][1], memo[i - 1][2]) + a[i]
        memo[i][1] = max(memo[i - 1][0], memo[i - 1][2]) + b[i]
        memo[i][2] = max(memo[i - 1][0], memo[i - 1][1]) + c[i]
    return max(memo[i][0], memo[i][1], memo[i][2])


for i in range(n):
    a_in, b_in, c_in = map(int, input().split())
    a.append(a_in)
    b.append(b_in)
    c.append(c_in)
    if i == 0:
        memo[0][0] = a_in
        memo[0][1] = b_in
        memo[0][2] = c_in
    else:
        ans = dp(i)


ans = dp(n - 1)

print("{}".format(ans))

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

N=int(input())
actions=[[int(x) for x in input().split()] for i in range(N)]
dp=np.zeros((N,3),dtype=int)
dp[0]=actions[0]
for i in range(1,N):
  dp[i][0]=max(dp[i-1][1],dp[i-1][2])+actions[i][0]
  dp[i][1]=max(dp[i-1][0],dp[i-1][2])+actions[i][1]
  dp[i][2]=max(dp[i-1][1],dp[i-1][0])+actions[i][2]
print(max(dp[N-1]))

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

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

for i in range(N):
  for j in range(3):
    if i == 0:
      dp[i][j] = abc[i][j]
      continue
    op1, op2 = [(1,2),(0,2),(0,1)][j]
    dp[i][j] = max(dp[i-1][op1], dp[i-1][op2])+abc[i][j]
    
print(max(dp[-1]))

Solution (Python):
n=int(input())
a=[]
for i in range(n):
    a.append([int(s) for s in input().split()])
x=a[0]
for i in range(1,n):
    
    x=[max(x[1],x[2])+a[i][0],max(x[0],x[2])+a[i][1],max(x[0],x[1])+a[i][2]]
    
print(max(x))

Solution (Python):
import math


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


def chmin(a, b):
    if a <= b:
        return a
    return b


def main():
    nn = int(input())
    arr = [list(map(int, input().split())) for l in range(nn)]
    dp = [[0] * 3 for i in range(nn+1)]

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

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


main()

Solution (Python):
n = int(input())
a = []
b = []
c = []
for i in range(n):
    ai,bi,ci = [int(x) for x in input().split()]
    a.append(ai)
    b.append(bi)
    c.append(ci)

dp = []
for i in range(n):
    dp.append([-float('inf')]*3)

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

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

Solution (Python):
n = int(input())
a,b,c = map(int,input().split())
for i in range(1,n):
    aa,bb,cc = map(int,input().split())
    aaa,bbb,ccc = a,b,c
    a = max(aa+bbb,aa+ccc)
    b = max(bb+ccc,bb+aaa)
    c = max(cc+aaa,cc+bbb)
print(max(a,b,c))

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

Solution (Python):
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time

starttime = time.time()

mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    
    sys.stdin = open("input.txt", "r")
    
except:
    pass

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

endtime = time.time()

Solution (Python):
am = int(input())
val = [[0]*(am+5),[0]*(am+5),[0]*(am+5)]
dp = [[0]*(am+5),[0]*(am+5),[0]*(am+5)]
for i in range(am):
    A,B,C = list(map(int,input().split()))
    val[0][i] = A
    val[1][i] = B
    val[2][i] = C

for i in range(0,am):
    for g in range(3):
        for j in range(3):
            if g!=j:
                dp[g][i+1] = max(dp[g][i+1],dp[j][i]+val[g][i])

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

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

solution=[[0,0,0] for _ in range(n)]

solution[0][0]=happines[0][0]
solution[0][1]=happines[0][1]
solution[0][2]=happines[0][2]

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

print(max(solution[-1]))

Solution (Python):
import numpy as np

N = int(input())
a = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,3])

for i in range(1,N+1):
    for j in range(3):
        dp[i][j] = a[i-1][j]+np.maximum(dp[i-1][(1+j)%3],dp[i-1][(2+j)%3])
print(int(max(dp[N])))

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

Solution (Python):
from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
d = [0]
for i in range(n):
    d.append(gil())
dp = [[0 for _ in range(3)] for _ in range(n+1)]
for dx in range(1, n+1):
    ndp = dp[dx]
    
    for i in range(3):
        for j in range(3):
            if i == j:
                continue
            ndp[i] = max(ndp[i], d[dx][i] + dp[dx-1][j])
    dp[dx] = ndp

print(max(dp[-1]))

Solution (Python):
from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
d = []
for i in range(n):
    d.append(gil())
dp = [[0,0,0]]
for dz in range(n):
    ndp = [0] * 3
    for i in range(3):
        for j in range(3):
            if i != j:
                ndp[i] = max(ndp[i], dp[dz][j] + d[dz][i])
    dp.append(ndp)

print(max(dp[-1]))

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

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

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

Solution (Python):
from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
a, b, c = [], [], []
for i in range(n):
    x,y,z = gil()
    a.append(x)
    b.append(y)
    c.append(z)
    
mem = [[-1 for _ in range(3)] for _ in range(n+1)]
def rp(i, p):
    global a,b,c,n
    if i >= n:
        return 0
    if mem[i][p] != -1:
        return mem[i][p]
    av = [a[i] + rp(i+1, 0), b[i] + rp(i+1, 1), c[i] + rp(i+1, 2)]
    if p != -1:
        av[p] = 0
    ans = max(av)
    mem[i][p] = ans
    return ans
ans = rp(0, -1)
print(ans)

Solution (Python):
from sys import stdin,stdout,setrecursionlimit
from collections import Counter as C
setrecursionlimit(10**6)
M = 1000000007
input = stdin.readline
def write(n,sep="\n"):
	stdout.write(str(n))
	stdout.write(sep)
def gil():
	return list(map(int, input().split()))
	
n = int(input())
a, b, c = [], [], []
for i in range(n):
    x,y,z = gil()
    a.append(x)
    b.append(y)
    c.append(z)
    
mem = [[-1 for _ in range(3)] for _ in range(n+1)]
def rp(i, p):
    global a,b,c,n
    if i >= n:
        return 0
    if mem[i][p] != -1:
        return mem[i][p]
    av = [a[i] + rp(i+1, 0), b[i] + rp(i+1, 1), c[i] + rp(i+1, 2)]
    if p != -1:
        av[p] = 0
    ans = max(av)
    mem[i][p] = ans
    return ans
ans = rp(0, -1)
print(ans)

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

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

Solution (Python):
import numpy as np

N = int(input())
a = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,3])

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

Solution (Python):
n = int(input())
dp = [0, 0, 0]
for x in range(n):
    new_dp = [0]*3
    happy = [int(x) for x in input().split()]
    for y in range(3):
        for z in range(3):
            if y != z:
                new_dp[y] = max(new_dp[y], dp[z] + happy[y])
    dp = new_dp
print(max(dp[0], dp[1], dp[2]))

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

dp[0][0],dp[1][0],dp[2][0] = map(int,input().split())
for i in range(1,N):
    act= list(map(int,input().split()))
    for k in range(3):
        dp[k][i] = max(dp[(k+1)%3][i-1],dp[(k+2)%3][i-1])+act[k%3]
ans = 0
for k in range(3):
    ans = max(ans,dp[k][-1])
print(ans)

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

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

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

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

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


for i in range(1, N + 1):
    if i == 1:
        dp[i][0] = abc[1][0]
        dp[i][1] = abc[1][1]
        dp[i][2] = abc[1][2]
    else:
        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[-1]))

Solution (Python):
import sys

input = sys.stdin.readline
x = [0, 0, 0]
for _ in range(int(input())):
    a, b, c = map(int, input().split())
    a += max(x[1], x[2])
    b += max(x[0], x[2])
    c += max(x[0], x[1])
    x = [a, b, c]
print(max(x))

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

dp=[0,0,0]
for i in range(n):
    nextdp=[]
    for j in range(3):
        x=dp[j+1:]+dp[:j]
        nextdp.append(max(x)+l[i][j])
    dp=nextdp

print(max(dp))

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

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

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


  
for _ in range(n):
  d=list(map(int,input().split()))
  a.append(d)
  
for x in range(n):
  for y in range(3):
    for z in range(3):
      if y!=z:
        dp[x+1][z]=max(dp[x+1][z],dp[x][y]+a[x][z])
        
print(max(dp[n][0],dp[n][1],dp[n][2]))

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

Solution (Python):
n=int(input())
happy=[list(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=happy[i]
    DP[i+1][0]=max(DP[i][1],DP[i][2])+a
    DP[i+1][1]=max(DP[i][2],DP[i][0])+b
    DP[i+1][2]=max(DP[i][0],DP[i][1])+c
print(max(DP[-1]))

Solution (Python):
n = int(input())
a = [None]*n
b = [None]*n
c = [None]*n
for i in range(n):
    a[i],b[i],c[i] = list(map(int,input().split(' ')))

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

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

Solution (Python):
n = int(input())
a = [None]*n
b = [None]*n
c = [None]*n
for i in range(n):
    a[i],b[i],c[i] = list(map(int,input().split(' ')))

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

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

Solution (Python):

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

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

    for i in range(N):
        for j in range(3):
            for k in range(3):
                if j == k: continue 
                tmp_cost = dp[i][j] + p_list[i][k]
                if dp[i + 1][k] < tmp_cost:
                    dp[i + 1][k] = tmp_cost

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

if __name__ == "__main__":
    main()

Solution (Python):

A = 0
B = 1
C = 2


N = int(input())
a = list()
b = list()
c = list()

dp = list()

for i in range (0, N):
	happiness = list(map(int, input().split()))
	a.append(happiness[A])
	b.append(happiness[B])
	c.append(happiness[C])

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


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



print(max(dp[N][A], dp[N][B], dp[N][C]))

Solution (Python):
import math
from decimal import *

arr = []
n = int(input())
for _ in range(n):
    arr.append(list(map(int, input().split())))
dp = [[0 for i in range(3)] 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):
        for x in range(3):
            if(x!= j):
                dp[i][j] = max(arr[i][j]+ dp[i-1][x], dp[i][j])
ans = max(dp[n-1][0], dp[n-1][1], dp[n-1][2])
print(ans)

Solution (Python):
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]
n = I()
act = [[0,0,0]] + LLI(n)
dp = [[-10**10,-10**10,-10**10] for _ in range(n+1)]




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

Solution (Python):

def main():
    days = int(input())
    happiness = [[int(x) for x in input().split()] for _ in range(days)]

    dp = [[0] * 3 for _ in range(days)]
    
    dp[0] = happiness[0]
    selection = set((0, 1, 2))
    for i in range(1, days):
        for sel in selection:
            dp[i][sel] = max(
                dp[i - 1][not_sel] for not_sel in selection - set((sel,))
            ) + happiness[i][sel]
    print(max(dp[days - 1][sel] for sel in selection))


if __name__ == '__main__':
    main()

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

Solution (Python):
import numpy as np

N = int(input())
plans = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0] * (N + 1) for _ in range(3)]

for j in range(N):
    for i_1 in range(3):
        for i_2 in range(3):
            if i_1 == i_2:
                continue
            dp[i_2][j+1] = max(dp[i_2][j+1], dp[i_1][j] + plans[j][i_2])

ans = np.array(dp)
print(ans[:, N].max())

Solution (Python):
import sys
sys.setrecursionlimit(10**5 + 9)
from collections import defaultdict
dp=defaultdict(lambda:0)
n=int(input())
ar,br,cr=[0]*n,[0]*n,[0]*n

for i in range(n):
	ar[i],br[i],cr[i]=map(int,input().split())
if n==1:
	print(max(ar[0],br[0],cr[0]))
	exit()
def points(i,pv):
	if dp[(i,pv)] != 0:
		return dp[(i,pv)]
	if pv==1:
		x,y=br[i],cr[i]
		a,b=2,3
	elif pv==2:
		x,y=ar[i],cr[i]
		a,b=1,3
	else:
		x,y=ar[i],br[i]
		a,b=1,2
	if i==n-1:
		return max(x,y)
	ax=points(i+1,a)+x
	by=points(i+1,b)+y
	ans=max(by,ax)
	dp[(i,pv)]=ans
	return ans
p=points(1,1)+ar[0]
q=points(1,2)+br[0]
r=points(1,3)+cr[0]
print(max(p,q,r))

Solution (Python):
import sys
sys.setrecursionlimit(10**5 + 9)
from collections import defaultdict
dp=defaultdict(lambda:0)
n=int(input())
ar,br,cr=[0]*n,[0]*n,[0]*n

for i in range(n):
	ar[i],br[i],cr[i]=map(int,input().split())
if n==1:
	print(max(ar[0],br[0],cr[0]))
	exit()
def points(i,pv):
	if dp[(i,pv)] != 0:
		return dp[(i,pv)]
	if pv==1:
		x,y=br[i],cr[i]
		a,b=2,3
	elif pv==2:
		x,y=ar[i],cr[i]
		a,b=1,3
	else:
		x,y=ar[i],br[i]
		a,b=1,2
	if i==n-1:
		return max(x,y)
	ax=points(i+1,a)+x
	by=points(i+1,b)+y
	ans=max(by,ax)
	dp[(i,pv)]=ans
	return ans
p=points(1,1)+ar[0]
q=points(1,2)+br[0]
r=points(1,3)+cr[0]
print(max(p,q,r))

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

print(max(dp[-1]))

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

print(max(dp[-1]))

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

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

print(max(dp[-1]))