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())
A = B = C = 0
for _ in range(n):
  a, b, c = map(int, input().split())
  A, B, C = max(B, C)+a, max(A, C)+b, max(A, B)+c
print(max(A, B, C))

Solution (Python):
n = int(input())
dpa = [0 for i in range(n)]
dpb = [0 for i in range(n)]
dpc = [0 for i in range(n)]
a,b,c = map(int, input().split())
dpa[0] = a
dpb[0] = b
dpc[0] = c
for i in range(1,n):
    a, b, c = map(int, input().split(" "))
    dpa[i] = max(dpb[i-1], dpc[i-1]) + a
    dpb[i] = max(dpa[i-1],dpc[i-1]) + b
    dpc[i] = max(dpb[i-1], dpa[i-1]) + c
print(max(dpa[n-1], dpb[n-1], dpc[n-1]))

Solution (Python):
import sys
import fractions
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
a = []
b = []
c = []
for i in range(n):
    a1, b1, c1 = MAP()
    a.append(a1)
    b.append(b1)
    c.append(c1)

dp0 = [0]*3
dp1 = [0]*3
dps = [dp0, dp1]
dp = [0]*n
abc = [a, b, c]

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

dp[0] = max(dps[0])

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

print(dp[n-1])

Solution (Python):
n = int(input())
a, b, c = map(int, input().split())

for i in range(n-1):
    ai, bi, ci = map(int, input().split())
    ai += max(b, c)
    bi += max(a, c)
    ci += max(a, b)
    a, b, c = ai, bi, ci

print(max(a, b, c))

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

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

dp = [[0]*3 for _ in range(N)]
for j in range(3):
    dp[0][j] = abc[0][j]
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])+abc[i][j]
print(max(dp[N-1]))

Solution (Python):
n = int(input())
dp = [{"a":0,"b":0,"c":0} for _ in range(n+1)]

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

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

Solution (Python):
import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
INF = float('inf')


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

for i in range(N):
    dp[i] = inpl()

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


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

Solution (Python):
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n = INT()
a = [MAP() 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[n]))

Solution (Python):
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n = INT()
a = [MAP() 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[n]))

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

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

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


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

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 j in range(N)] for k in range(3)]

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

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

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

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

print(max(dp[N]))

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

Solution (Python):

n=int(input())
data=[list(map(int,input().split())) for _ in range(n)]
fa=[data[0][0]]
fb=[data[0][1]]
fc=[data[0][2]]
for i in range(1,n):
    fa.append(max(fb[i-1],fc[i-1])+data[i][0])
    fb.append(max(fa[i-1],fc[i-1])+data[i][1])
    fc.append(max(fb[i-1],fa[i-1])+data[i][2])
print(max(fa[-1],fb[-1],fc[-1]))

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

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

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

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
dp = [[0]*3 for _ in range(n+1)]
for i in range(n):
    a,b,c = LI()
    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[-1]))

Solution (Python):

import sys


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    dp = [[0 for _ in range(3)] for _ in range(N)]

    H = list(zip(a,b,c))

    for j in range(3):
        dp[0][j] = H[0][j]

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

    print(max(dp[-1]))


    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N)  
    b = [int()] * (N)  
    c = [int()] * (N)  
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, a, b, c)

if __name__ == '__main__':
    main()

Solution (Python):
N, *abc = map(int, open(0).read().split())
plan = list(zip(*[iter(abc)]*3))
profit = [[0]*3 for _ in range(N)]
profit[0] = [p for p in plan[0]]

for day in range(1, N):
    
    for n_plan in range(3):
        max_plofit = max([pr + plan[day][n_plan]
            if n_plan != i
            else 0
            for i, pr in enumerate(profit[day-1])])
        profit[day][n_plan] = max_plofit      
print(max(profit[N-1]))

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

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

for i in range(1,n):
  for j in range(3):
    s = 0 
    for k in range(3):
      s = max(s,(dp[i-1][k]+Act[i][j])*int(j!=k))
    dp[i][j] = s

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

Solution (Python):
import numpy as np
n = int(input())
ary = [list(map(int,input().split())) for _ in range(n)]
ary = np.array(ary)
dp = np.zeros((n,3))
dp[0] = ary[0]
for i in range(n-1):
    for j in range(3):
        for k in range(3):
            if k == j:continue
            check = dp[i][j] + ary[i+1][k]
            if check > dp[i+1][k]:
                dp[i+1][k] = check
print(int(max(dp[n-1])))

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

a=0
b=0
c=0

for _ in range(n):
  aa,bb,cc=map(int,input().split())
  
  a1=max(b,c)+aa
  b1=max(a,c)+bb
  c1=max(b,a)+cc
  a=a1
  b=b1
  c=c1
  
  
print(max(a,b,c))

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

Solution (Python):
def vacation():
    N = int(input())
    d = list(input().split() for _ in range(N))

    happiness=list()

    if N==1:
        return max(d[0])

    for i in range(N):
        day = list()
        if i == 0:
            for c in range(3):
                day.append(int(d[0][c]))
        else:
            for c in range(3):
                tmp = list()
                for bc in range(3):
                    if c != bc:
                        tmp.append(int(happiness[i-1][bc])+int(d[i][c]))
                day.append(max(tmp))

        happiness.append(day)
    return max(happiness[-1])


if __name__ == "__main__":
    print(vacation())

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

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

Solution (Python):
import sys
n = int(sys.stdin.readline())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]


dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0] = L[0].copy()

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

print(max(dp[-1]))

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7



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 for _ in range(3)] for _ in range(N+1) ]

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

print(max(dp[N]))

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
dp = [[0, 0, 0] for i in range(N+1)]
A = [[0, 0, 0] for i in range(N+1)]
for i in range(N):
    a, b, c = [int(_) for _ in stdin.readline().rstrip().split()]
    A[i][0], A[i][1], A[i][2] = a, b, c 

for i in range(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]+A[i][j])
print(max(dp[N-1]))

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

dp = [[0]*3 for i in range(N+1)]
A = [list(map(int, input().split())) for i in range(N)]

for i in range(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]+A[i][j])

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

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

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

for i in range(1, N+1):
  acitivities = list(map(int, input().split()))
  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]+acitivities[j])

print(max(dp[N]))

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

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

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

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]) + Data[i][j]
        elif j == 1:
            dp[i][j] = max(dp[i-1][0], dp[i-1][2]) + Data[i][j]
        else:
            dp[i][j] = max(dp[i-1][0], dp[i-1][1]) + Data[i][j]

print(max(dp[-1]))

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

A = [0] * (N+1)
B = [0] * (N+1)
C = [0] * (N+1)

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

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

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

Solution (Python):

import sys
sys.setrecursionlimit(300000)


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    v = [a, b, c]
    dp = [[0] * 3 for _ in range(N + 1)]
    dp[1] = [a[0], b[0], c[0]]
    for i in range(1, N):
        for j in range(3):
            for k in [1, 2]:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][(j + k) % 3] + v[j][i])
    print(max(dp[N]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N)  
    b = [int()] * (N)  
    c = [int()] * (N)  
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, a, b, c)

if __name__ == '__main__':
    main()

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):
        dp[i + 1][j] = max(dp[i][(j + 1) % 3] + a[i][j], dp[i][(j + 2) % 3] + a[i][j])

print(max(dp[n]))

Solution (Python):
import copy
N = int(input())
dp = [0]*3
for _ in range(N):
  tmp = [int(n) for n in input().split()]
  tmp_dp = copy.deepcopy(dp)
  tmp_dp[0] = max(dp[1],dp[2]) + tmp[0]
  tmp_dp[1] = max(dp[0],dp[2]) + tmp[1]
  tmp_dp[2] = max(dp[0],dp[1]) + tmp[2]
  dp = tmp_dp
print(max(dp))

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

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

for i in range(1, N):
    dp.append([0, 0, 0])
    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][1], dp[i-1][0]) + c[i]
    
print(max(dp[N-1]))

Solution (Python):

N = int(input())

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

Solution (Python):

N = int(input())

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

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = []
b = []
c = []
for _ in range(N):
    a_val , b_val , c_val = map(int , input().split())
    a.append(a_val)
    b.append(b_val)
    c.append(c_val)

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

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

i=n-2
while i>-1:
	a[i]+=max(b[i+1],c[i+1])
	b[i]+=max(a[i+1],c[i+1])
	c[i]+=max(b[i+1],a[i+1])
	i=i-1
print(max([a[0],b[0],c[0]]))

Solution (Python):
n = int(input())
li = []
while True:
    try:
        li.append(list(map(int,input().split())))
    except:
        break

f_inf = float('inf')
dpa=[li[0][0]]+[0]*(n-1)
dpb=[li[0][1]]+[0]*(n-1)
dpc=[li[0][2]]+[0]*(n-1)

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

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

Solution (Python):
n = int(input())
li = []
while True:
    try:
        li.append(list(map(int,input().split())))
    except:
        break

f_inf = float('inf')
dpa=[li[0][0]]+[0]*(n-1)
dpb=[li[0][1]]+[0]*(n-1)
dpc=[li[0][2]]+[0]*(n-1)

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

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

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

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

dpa = [abc[0][0]]+[0]*(n-1)
dpb = [abc[0][1]]+[0]*(n-1)
dpc = [abc[0][2]]+[0]*(n-1)

for i in range(1, n):
    dpa[i]=max(dpb[i-1],dpc[i-1])+abc[i][0]
    dpb[i]=max(dpc[i-1],dpa[i-1])+abc[i][1]
    dpc[i]=max(dpa[i-1],dpb[i-1])+abc[i][2]

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

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

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

dpa = [abc[0][0]]+[0]*(n-1)
dpb = [abc[0][1]]+[0]*(n-1)
dpc = [abc[0][2]]+[0]*(n-1)

for i in range(1, n):
    dpa[i]=max(dpb[i-1],dpc[i-1])+abc[i][0]
    dpb[i]=max(dpc[i-1],dpa[i-1])+abc[i][1]
    dpc[i]=max(dpa[i-1],dpb[i-1])+abc[i][2]

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

Solution (Python):
class Solver(object):
    def __init__(self, N, happy):
        self.dp = [[99999999 for _ in range(3)] for _ in range(N)]
        self.N = N
        self.happy = happy

    def solve(self):
        happy_list = self.happy
        self.dp[0] = happy_list[0]
        for i in range(1, self.N):
            self.dp[i][0] = max(happy_list[i][0] + self.dp[i-1][1],
                                happy_list[i][0] + self.dp[i-1][2])
            self.dp[i][1] = max(happy_list[i][1] + self.dp[i-1][0],
                                happy_list[i][1] + self.dp[i-1][2])
            self.dp[i][2] = max(happy_list[i][2] + self.dp[i-1][0],
                                happy_list[i][2] + self.dp[i - 1][1])
        return max(self.dp[-1])


def main():
    N = int(input())
    happy = [[int(i) for i in input().split()] for _ in range(N)]
    solver = Solver(N, happy)
    print(solver.solve())


if __name__ == "__main__":
    main()

Solution (Python):
import sys
n = int(sys.stdin.readline())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

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

p[0] = L[0].copy()



for d in range(1, n):
    for i in range(3):
        if i ==0:
            p[d][0] = max(p[d-1][1], p[d-1][2]) + L[d][0]
        elif i ==1:
            p[d][1] = max(p[d-1][0], p[d-1][2]) + L[d][1]
        elif i==2:
            p[d][2] = max(p[d-1][0], p[d-1][1]) + L[d][2]

print(max(p[-1]))

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

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

print(max(dp[-1]))

Solution (Python):
N=int(input())
li=[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:
        for j in range(3):
            dp[i][j] = li[i][j]
    else:
        for j in range(3):
            if j == 0:
                dp[i][j] = li[i][0] + dp[i-1][1] if dp[i-1][1] >= dp[i-1][2] else li[i][0] + dp[i-1][2]
            if j == 1:
                dp[i][j] = li[i][1] + dp[i-1][0] if dp[i-1][0] >= dp[i-1][2] else li[i][1] + dp[i-1][2]
            if j == 2:
                dp[i][j] = li[i][2] + dp[i-1][0] if dp[i-1][0] >= dp[i-1][1] else li[i][2] + dp[i-1][1]
print(max(dp[N-1]))

Solution (Python):
import sys
from collections import defaultdict, deque

input = sys.stdin.readline


def main():
    N = int(input())
    f_inf = float('inf')
    
    MAX_N = 110000
    dp = [[]] * N
    for i in range(N):
        a, b, c = map(int, input().split())
        if i == 0:
            dp[i] = [a, b, c]
        else:
            dp[i] = [max(dp[i-1][1], dp[i-1][2]) + a, max(dp[i-1][0], dp[i-1][2]) + b, max(dp[i-1][0], dp[i-1][1]) + c]
    print(max(dp[N-1]))


if __name__ == '__main__':
    main()

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

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

DP = [0, 0, 0]

DP[0], DP[1], DP[2] = list(map(int, input().split()))

for _ in range(N-1):
    next = [0, 0, 0]
    W = list(map(int, input().split()))
    next[0] = W[0] + max(DP[1], DP[2])
    next[1] = W[1] + max(DP[0], DP[2])
    next[2] = W[2] + max(DP[0], DP[1])
    DP = next

print(max(DP))

Solution (Python):
import sys
import heapq

input = sys.stdin.readline
N = int(input())

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

Solution (Python):
n = int(input())
v = tuple(tuple(map(int, input().split())) for _ in range(n))
e = tuple(zip(*v))



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



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

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

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

dp = [0] * 3
for _ in range(N):
    a = [int(x) for x in input().split()]
    dp = [a[i] + max([dp[j] for j in range(3) if j != i]) for i in range(3)]
print(max(dp))

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

l = [0] * 3
for i in range(N):
    a = [int(x) for x in input().split()]
    c = [a[0] + max(l[1], l[2]), a[1] + max(l[2], l[0]), a[2] + max(l[0], l[1])]
    l = c
print(max(l))

Solution (Python):
import sys

stdin = sys.stdin

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

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

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

dp_a = [abc[0][0]] + [0]*(n-1)
dp_b = [abc[0][1]] + [0]*(n-1)
dp_c = [abc[0][2]] + [0]*(n-1)

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]

ans = max(dp_a[-1],dp_b[-1],dp_c[-1])
print(ans)

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

for _ in range(N):
	a, b, c = list(map(int, input().split()))
	happy[0].append(a)
	happy[1].append(b)
	happy[2].append(c)
	
dp = [[0 for _ in range(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]) + happy[0][i - 1]
	dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + happy[1][i - 1]
	dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + happy[2][i - 1]
print(max(dp[N]))

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

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

for i in range(1, n+1):
    for j in range(3):
        l = list(range(3))
        l.remove(j)
        x, y = l
        
        dp[i][j] = max(dp[i-1][x], dp[i-1][y]) + h[i-1][j]

print(max(dp[n]))

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

dp = [[0]*3 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],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[n-1]))

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

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

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

Solution (Python):
n = int(input())
e = tuple(tuple(map(int, input().split())) for _ in range(n))

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

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

print(max(dp[n]))

Solution (Python):


n=int(input())
a=[]
b=[]
c=[]
for i in range(n):
    ak,bk,ck=map(int,input().split())
    a.append(ak)
    b.append(bk)
    c.append(ck)
hy=[]
for i in range(n):
    hy.append([0,0,0])


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

    
for i in range(1,n):

    hy[i][0] = max(hy[i-1][1]+a[i],hy[i-1][2]+a[i])
    hy[i][1] = max(hy[i-1][0]+b[i],hy[i-1][2]+b[i])
    hy[i][2] = max(hy[i-1][0]+c[i],hy[i-1][1]+c[i])

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

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

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

for i in range(N):
    v1, v2, v3 = map(int, input().split())
    vals[i][0] = v1
    vals[i][1] = v2
    vals[i][2] = v3

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

dp[0][0] = vals[0][0]
dp[0][1] = vals[0][1]
dp[0][2] = vals[0][2]

for i in range(1, N):
    for activity in range(3):
        for pastActivity in range(3):
            if activity == pastActivity: continue
            
            dp[i][activity] = max(dp[i][activity],
                                  dp[i-1][pastActivity] + vals[i][activity])

print(max(dp[-1]))

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

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

for i in range(1, N):
    for j in range(3):
        a = dp[i-1][(j+1) % 3]
        b = dp[i-1][(j+2) % 3]
        dp[i][j] = a+ary[i][j] if a > b else b + ary[i][j]

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

Solution (Python):
import numpy as np

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

dp = np.zeros((n, 3))

dp[0, :] = abc[0, :]

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

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

print(int(np.max(dp[-1, :])))

Solution (Python):
N = int(input())
A,B,C=[],[],[]
for i in range(N):
    a,b,c = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
dpa,dpb,dpc = A[0],B[0],C[0]
for i in range(1,N):
    a,b,c = dpa,dpb,dpc
    dpa = max(c,b)+A[i]
    dpb = max(c,a)+B[i]
    dpc = max(a,b)+C[i]
print(max(dpa,dpb,dpc))

Solution (Python):


N = int(input())
day=[[int(i) for i in input().split()] for _ in range(N)]

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

dp[0][0]=day[0][0]
dp[1][0]=day[0][1]
dp[2][0]=day[0][2]

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

Solution (Python):
N = int(input())
dp = [0] * 3

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

print(max(dp))