Problem:
 Score : 100 points    Problem Statement Taro's summer vacation starts tomorrow, and he has decided to make plans for it now.  The vacation consists of N days.
For each i ( 1 \leq i \leq N ), Taro will choose one of the following activities and do it on the i -th day:   A: Swim in the sea. Gain a_i points of happiness.  B: Catch bugs in the mountains. Gain b_i points of happiness.  C: Do homework at home. Gain c_i points of happiness.   As Taro gets bored easily, he cannot do the same activities for two or more consecutive days.  Find the maximum possible total points of happiness that Taro gains.      Constraints  All values in input are integers.  1 \leq N \leq 10^5  1 \leq a_i, b_i, c_i \leq 10^4         Input Input is given from Standard Input in the following format:  N  a_1  b_1  c_1  a_2  b_2  c_2  :  a_N  b_N  c_N       Output Print the maximum possible total points of happiness that Taro gains.        Sample Input 1 3
10 40 70
20 50 80
30 60 90      Sample Output 1 210  If Taro does activities in the order C, B, C, he will gain 70 + 50 + 90 = 210 points of happiness.       Sample Input 2 1
100 10 1      Sample Output 2 100       Sample Input 3 7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1      Sample Output 3 46  Taro should do activities in the order C, A, B, A, C, B, A.

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def main():
    N = int(readline())
    abc = map(int, read().split())
    x, y, z = 0, 0, 0
    for a, b, c in zip(abc, abc, abc):
        x, y, z = max(y, z) + a, max(x, z) + b, max(x, y) + c

    print(max(x, y, z))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import functools
from collections import deque
sin = sys.stdin

n = int(sin.readline())
a = []
b = []
c = []
for i in range(n):
    values = sin.readline().split()
    a.append(int(values[0]))
    b.append(int(values[1]))
    c.append(int(values[2]))

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

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

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

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

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

def Main(N, V):
    dp = [[0 for _ in range(3)] for _ 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+1][j], dp[i][k] + V[i][j])
    return max(dp[N])

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input().rstrip())
    old_dp = [0 for i in range(3)]
    for i in range(n):
        new_dp = [0 for i in range(3)]
        c = list(map(int, input().rstrip().split()))
        for i in range(3):
            for j in range(3):
                if i!=j:
                    new_dp[j] = max(new_dp[j], old_dp[i] + c[j])

        old_dp = new_dp
    print(max(old_dp[0], old_dp[1], old_dp[2]))

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
n=int(input())
H=[]
for i in range(n):
    a,b,c=map(int,input().split())
    H.append([a,b,c])

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

dp[0][0]=H[0][0]
dp[0][1]=H[0][1]
dp[0][2]=H[0][2]

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

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

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

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


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

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


if __name__ == '__main__':
    main()

Solution (Python):


N=int(input())
l=[[0]*3 for i in range(N)]
A,B,C=map(int,input().split())
l[0][0]=A
l[0][1]=B
l[0][2]=C


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

print(max(l[-1]))

Solution (Python):

n=int(input())
x=[]
for i in range(n):
    x.append(list(map(int,input().split())))
def changemax(a,b):
    if a<b:
        a=b
        return a
    return a
dp=[]
dp.append([0,0,0])
for i in range(1,n+1):
    dp.append([0,0,0])
for m in range(n):
    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            dp[m+1][k]=changemax(dp[m+1][k],dp[m][j]+x[m][k])
print(max(dp[n]))

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

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

Solution (Python):
def run():
  N = int(input())
  abc_li = [tuple(map(int, input().split())) for n in range(N)]
  dp = [[0]*3 for n in range(N)]
  dp[0] = abc_li[0]
  for n in range(1, N):
    for pre_i in range(3):
      for i in range(3):
        if pre_i == i: continue
        dp[n][i] = max(dp[n][i], dp[n-1][pre_i] + abc_li[n][i])
  print(max(dp[-1]))
  
if __name__ == '__main__':
  run()

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

Solution (Python):
import bisect
def main():
    n=int(input())
    happiness=[list(map(int,input().split(' '))) for i in range(n)]
    ans = 0
    def rec(x,num):
        if num ==0:
            return happiness[0][x]
        else:
            a=[0,1,2]
            a.remove(x)
            return max(rec(a[0],num-1),rec(a[1],num-1))+happiness[num][x]
    dp=[[0 for i in range(n)] for j in range(3)]
    dp[0][0]=happiness[0][0]
    dp[1][0]=happiness[0][1]
    dp[2][0]=happiness[0][2]
    for i in range(1,n):
        for j in range(3):
            b=[0,1,2]
            b.remove(j)
            dp[j][i]=max(dp[b[0]][i-1],dp[b[1]][i-1])+happiness[i][j]
    print(max(dp[0][n-1],dp[1][n-1],dp[2][n-1]))


if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
abc=[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]+abc[i][k])
print(max(dp[N]))

Solution (Python):
N = int(input())
activity = [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 k in range(3):
        dp[i+1][k] = max(
            dp[i][k-1] + activity[i][k],
            dp[i][k-2] + activity[i][k]
        )
print(max(dp[N]))

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

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_A = [0]*N
dp_B = [0]*N
dp_C = [0]*N

dp_A[0] = A[0]
dp_B[0] = B[0]
dp_C[0] = C[0]

for i in range(1, N):
    dp_A[i] = A[i] + max(dp_B[i-1], dp_C[i-1])
    dp_B[i] = B[i] + max(dp_C[i-1], dp_A[i-1])
    dp_C[i] = C[i] + max(dp_A[i-1], dp_B[i-1])
    
print(max(dp_A[N-1], dp_B[N-1], dp_C[N-1]))

Solution (Python):
N = int(input())
a = [0] * N
b = [0] * N
c = [0] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
    
Dpa = [0]*N
Dpb = [0]*N
Dpc = [0]*N

Dpa[0] = a[0]
Dpb[0] = b[0]
Dpc[0] = c[0]


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

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

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

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

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

Solution (Python):
from sys import stdin

n = int(stdin.readline().rstrip())
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]

dp = [[-1 for p in range(3)] for q in range(n+1)]
for a in range(3):
    dp[0][a] = 0
for i in range(1,n+1):
    for j in range(3):
        lin = []
        for k in range(3):
            if j != k:
                lin.append((dp[i-1][k]+li[i-1][j]))
        dp[i][j] = max(lin)
print(max(dp[-1]))

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


def vacation():
    n = int(input())
    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] = [a + max(dp[i-1][1], dp[i-1][2]), b + max(dp[i-1][0], dp[i-1][2]), c + max(dp[i-1][0], dp[i-1][1])]
    print(max(dp[-1]))


if __name__ == '__main__':
    vacation()

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


if __name__ == '__main__':
    vacation()

Solution (Python):
n=int(input())
l=[tuple(map(int,input().split())) for i in range(n)]
k=[[None,None,None] for i in range(n)]
k[0][0]=l[0][0]
k[0][1]=l[0][1]
k[0][2]=l[0][2]

for i,(a,b,c) in enumerate(l[1:]):
    k[i+1][0]=max(k[i][1],k[i][2])+a
    k[i+1][1]=max(k[i][0],k[i][2])+b
    k[i+1][2]=max(k[i][1],k[i][0])+c
print(max(k[n-1][0],k[n-1][1],k[n-1][2]))

Solution (Python):
n = int(input())
a = []
b = []
c = []

for _ in range(n):
    x, y, z = [int(e) for e in input().split()]
    a.append(x)
    b.append(y)
    c.append(z)

q, w, r = a[0], b[0], c[0]
for i in range(1, n):
    q, w, r = a[i] + max(w, r), b[i] + max(q, r), c[i] + max(q, w)
ans = max(q, w, r)
print(ans)

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


res = [[None,None,None] for _ in range(n)]
res[0][0] = data[0][0]
res[0][1] = data[0][1]
res[0][2] = data[0][2] 

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

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

for day in range(n):
     points=list(map(int,input().split()))

     new_dp=[0]*3
     for i in range(3):
          for j in range(3):
               if j!=i:
                    new_dp[j]= max(new_dp[j],dp[i]+points[j])
     dp=new_dp
print(max(dp))

Solution (Python):
N = int(input())
dp = [{ "A": 0, "B": 0, "C": 0 }]
for i in range(N):
  a, b, c = map(int, input().split())
  d = dp[i]
  d2 = {}
  d2["A"] = a+max(d["B"], d["C"])
  d2["B"] = b+max(d["C"], d["A"])
  d2["C"] = c+max(d["A"], d["B"])
  dp.append(d2)
r = max(dp[N].values())
print(r)

Solution (Python):

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

x, y, z = [0] * n, [0] * n, [0] * n
x[0], y[0], z[0] = a[0], b[0], c[0]
for i in range(1, n):
    x[i] = max(y[i-1]+a[i], z[i-1]+a[i])
    y[i] = max(x[i-1]+b[i], z[i-1]+b[i])
    z[i] = max(y[i-1]+c[i], x[i-1]+c[i])

ans = max(x[n-1], y[n-1], z[n-1])
print(ans)

Solution (Python):

N = int(input())

p = [list(map(int,input().split())) for l in range(N)]
dp = [[0,0,0]]*N
dp[0] = p[0]

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


print(max(max(dp)))

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

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

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

print(max(a,b,c))

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

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

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

Solution (Python):


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

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


for day in range(n):
  for j in range(3):
    for k in range(3):
      
      if j==k:
        continue
      
      dp[day+1][k] = max(dp[day+1][k],dp[day][j]+happiness[day][k])


print(max(dp[n]))

Solution (Python):
def main(n, choices):
    results = [[0, 0, 0] for _ in range(n)]
    results[0] = choices[0]
    for i in range(1, n):
        results[i][0] = choices[i][0] + max(results[i - 1][1], results[i - 1][2])
        results[i][1] = choices[i][1] + max(results[i - 1][0], results[i - 1][2])
        results[i][2] = choices[i][2] + max(results[i - 1][0], results[i - 1][1])
    return max(results[-1])


if __name__ == '__main__':
    N = int(input())
    C = []
    for _ in range(N):
        C.append(list(map(int, input().split())))
    print(main(N, C))

Solution (Python):
def main():
    N = int(input())
    A = [0]
    B = [0]
    C = [0]
    for i in range(N):
        a, b, c = (int(i) for i in input().split())
        A.append(a)
        B.append(b)
        C.append(c)
    dp = [[0 for _ in range(N+1)] for _ in range(3)]
    dp[0][1] = A[1]
    dp[1][1] = B[1]
    dp[2][1] = C[1]

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

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


if __name__ == '__main__':
    main()

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)]
DP[0][0] = abc[0][0]
DP[0][1] = abc[0][1]
DP[0][2] = abc[0][2]
preA = DP[0][0]
preB = DP[0][1]
preC = DP[0][2]

for i in range(1,N):
    DP[i][0] = max(preB,preC)+abc[i][0]
    DP[i][1] = max(preA,preC)+abc[i][1]
    DP[i][2] = max(preA,preB)+abc[i][2]
    preA = DP[i][0]
    preB = DP[i][1]
    preC = DP[i][2]
print(max(DP[N-1]))

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

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

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

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

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

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

print(max(dp[-1]))

Solution (Python):
import numpy as np
n=int(input())
temp=[]
p=n
while p:
    p-=1
    temp.append(list(map(int,input().split())))
arr=(np.array(temp)).transpose()
dp=np.zeros((3,n))
dp[0][0]=arr[0][0]
dp[1][0]=arr[1][0]
dp[2][0]=arr[2][0]
for i in range(1,n):
    dp[0][i]=max(dp[1][i-1],dp[2][i-1])+arr[0][i]
    dp[1][i]=max(dp[0][i-1],dp[2][i-1])+arr[1][i]
    dp[2][i]=max(dp[1][i-1],dp[0][i-1])+arr[2][i]
print(int(max(dp.transpose()[n-1])))

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

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

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

Solution (Python):
import sys

n = int(sys.stdin.readline().strip())
arr = []
for _ in range(n):
    a,b,c = map(int, sys.stdin.readline().strip().split(' '))
    arr.append((a,b,c))


dp = [[-1, -1, -1] for _ 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):
    dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + arr[i][0]
    dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + arr[i][1]
    dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + arr[i][2]

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

Solution (Python):
N = int(input())
A, B, C = list(map(int, input().split()))

for i in range(N - 1):
    a, b, c = list(map(int, input().split()))
    nA = max(B, C) + a   
    nB = max(A, C) + b 
    nC = max(A, B) + c
    A, B, C = nA, nB, nC
print(max(A, B, C))

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
a0,b0,c0=0,0,0
for i in range(n):
    a,b,c=map(int,input().split())
    a1,b1,c1=a0,b0,c0
    a0=a+(b1 if b1>c1 else c1)
    b0=b+(a1 if a1>c1 else c1)
    c0=c+(b1 if b1>a1 else a1)
print(max(a0,b0,c0))

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

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

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

Solution (Python):
import sys

N = int(input())
a = [0 for i in range(N)]
b = [0 for i in range(N)]
c = [0 for i in range(N)]

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

sa = [0 for i in range(N)]
sb = [0 for i in range(N)]
sc = [0 for i in range(N)]

sa[0] = a[0]
sb[0] = b[0]
sc[0] = c[0]

for i in range(1,N):
    sa[i] = max(sb[i-1], sc[i-1]) + a[i]
    sb[i] = max(sa[i-1], sc[i-1]) + b[i]
    sc[i] = max(sa[i-1], sb[i-1]) + c[i]


print(max(sa[N-1], sb[N-1], sc[N-1]))

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

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

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

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

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

ans = max(dp[N-1])

print(ans)

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

def main():
    N = int(input())
    a1,b1,c1 = 0,0,0
    for _ in range(N):
        a,b,c = map(int, input().split())
        a0,b0,c0 = a1,b1,c1
        a1 = a + (b0 if b0 > c0 else c0)
        b1 = b + (a0 if a0 > c0 else c0)
        c1 = c + (a0 if a0 > b0 else b0)

    print(max(a1,b1,c1))

if __name__ == '__main__':
    main()

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

def main():
    N = int(input())
    a1,b1,c1 = 0,0,0
    for _ in range(N):
        a,b,c = map(int, input().split())
        a0,b0,c0 = a1,b1,c1
        a1 = max(b0, c0) + a 
        b1 = max(a0, c0) + b 
        c1 = max(a0, b0) + c 

    print(max(a1,b1,c1))

if __name__ == '__main__':
    main()

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
n = int(input())
arr = []
for i in range(n):
    arr.append([int(i) for i in input().split()])

dp = [[-1 for i in range(n+2)] for i in range(3)]

def cal(i,action):

    if i>=len(arr):
        return 0

    if dp[action][i]==-1:
        if action==0:
            dp[action][i] = max(cal(i+1,1)+arr[i][1],cal(i+1,2)+arr[i][2])

        elif action==1:
            dp[action][i] = max(cal(i+1,0)+arr[i][0],cal(i+1,2)+arr[i][2]) 
        
        else:
            dp[action][i] = max(cal(i+1,1)+arr[i][1],cal(i+1,0)+arr[i][0])
        
    return dp[action][i]
print(max(cal(0,0),cal(0,1),cal(0,2)))

Solution (Python):
import copy
def main():
    n = int(input())
    act3 = [0]*3
    for i in range(n):
        if i==0:
            act1 = list(map(int, input().split()))
        else:
            act2 = list(map(int, input().split()))
            for j, act in enumerate(act2):
                act3[j] = max(act1[j-1] + act, act1[j-2] + act)
            act1 = copy.copy(act3)
    print(max(act1))

main()

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

def calculate(infos,n):
    dp=[[0]*3 for i in range(n)]
    dp[0] = infos[0][:]
    for i in range(1,n):
        a,b,c = dp[i-1]
        dp[i] = [infos[i][0]+max(b,c),infos[i][1]+max(a,c),infos[i][2]+max(a,b)]
    return max(dp[-1])

print(calculate(infos,n))

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

def calculate(infos,n):
    dp=[[0]*3 for i in range(n)]
    dp[0] = infos[0][:]
    for i in range(1,n):
        a,b,c = dp[i-1]
        dp[i] = [infos[i][0]+max(b,c),infos[i][1]+max(a,c),infos[i][2]+max(a,b)]
    return max(dp[-1])

print(calculate(infos,n))

Solution (Python):
n = int(input())
vac = []
for i in range(n):
    arr =  [int(x) for x in input().strip().split()]
    vac.append(arr)
dp = [[None, None, None] for _ in range(n)]
dp[0] = vac[0]
for i in range(1,n):
    dp[i][0] = max(dp[i-1][1], dp[i-1][2])+vac[i][0]
    dp[i][1] = max(dp[i-1][0], dp[i-1][2])+vac[i][1]
    dp[i][2] = max(dp[i-1][1], dp[i-1][0])+vac[i][2]

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

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

def dp(n,l,memo):
    memo[0] = l[0]
    for i in range(1,n):
        memo[i][0] = max(memo[i-1][1],memo[i-1][2]) + l[i][0]
        memo[i][1] = max(memo[i-1][0],memo[i-1][2]) + l[i][1]
        memo[i][2] = max(memo[i-1][0],memo[i-1][1]) + l[i][2]
        
    return memo

ans = dp(n,l,memo)
print(max(ans[n-1]))

Solution (Python):
n = int(input())
dp = [[0,0,0]]*n
a,b,c = map(int, input().split())
dp[0]=[a,b,c]

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

Solution (Python):
n = int(input())
dp = [[0,0,0]]*n
a,b,c = map(int, input().split())
dp[0]=[a,b,c]
for i in range(1,n):
    abc = list(map(int, input().split()))
    dp0= abc[0]+max(dp[i-1][1], dp[i-1][2])
    dp1= abc[1]+max(dp[i-1][2], dp[i-1][0])
    dp2= abc[2]+max(dp[i-1][0], dp[i-1][1])
    dp[i]=[dp0,dp1,dp2]
ans = dp[-1]
print(max(ans))

Solution (Python):
INF = 1000000
n = int(input())
t = [[int(i) for i in input().split()] for j in range(n)]
dp = [[-INF for i in range(3)] for j in range(n)]
for j in range(3):
    dp[0][j] = t[0][j]
a = [0, 1, 2]

for i in range(1, n):
    for j in range(3):
        k = list(set(a).difference(set([j])))
        dp[i][j] = max(dp[i - 1][k[0]], dp[i - 1][k[1]]) + t[i][j]

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

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

for i in range(0,N):
    new_dp=[]
    for i in range(0,3):
        new_dp.append(0)
    costs=[int(j) for j in input().split()]
    for k in range(0,3):
        for j in range(0,3):
            if(k!=j):
                new_dp[j]=max(new_dp[j],dp[k]+costs[j])
    dp=new_dp
print(max(dp[0],dp[1],dp[2]))

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

Solution (Python):


N = int(input())
a, b, c = [], [], []
for _ in range(N):
    ai, bi, ci = map(int, input().split())
    a.append(ai); b.append(bi); c.append(ci)


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

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

print(max(dp[h][N-1] for h in range(3)))

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

A = [0 for _ in range(N)]
B = [0 for _ in range(N)]
C = [0 for _ in range(N)]

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

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

print(max(dp[-1]))

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

A = [0 for _ in range(N)]
B = [0 for _ in range(N)]
C = [0 for _ in range(N)]

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

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

print(max(dp[-1]))

Solution (Python):
def run():
  N = int(input())
  abc_li = [[int(i) for i in input().split()] for n in range(N)]
  dp = [[0]*3 for n in range(N)]
  dp[0] = abc_li[0]
  for n in range(1, N):
    for next_abc in range(3):
      for pre_abc in range(3):
        if pre_abc == next_abc: continue
        dp[n][next_abc] = max(dp[n][next_abc], dp[n-1][pre_abc]+abc_li[n][next_abc])
  print(max(dp[N-1]))
  
if __name__ == '__main__':
  run()

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


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

for i in range(N-1):
    for j in range(3):
        actions = list(set([0, 1, 2]) - set([j]))
        dp[i+1][j] = max(list(map(lambda x: abc[i+1][j]+dp[i][x], actions)))

print(max(dp[-1]))

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

dp[0] = abc[0]
ls = [[1,2], [0,2], [0,1]]

if n == 1:
    ans = min(dp[0])
else:
    for i in range(1,n):
        for j in range(3):
            dp[i][j] = max([ dp[i-1][k] for k in ls[j] ]) + abc[i][j]

print(max(dp[-1]))

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


dp = [['' for i in range(3)] for j in range(n)]
for i in range(n):
    if(i == 0):
        dp[i] = A[i]
        continue
    for j in range(3):
        if(j ==0):
            dp[i][j] = max(dp[i-1][1], dp[i-1][2])+A[i][j]
        elif(j ==1):
            dp[i][j] = max(dp[i-1][0], dp[i-1][2])+A[i][j]
        elif(j ==2):
            dp[i][j] = max(dp[i-1][0], dp[i-1][1])+A[i][j]

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

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

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

for i in range(0, 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] + actions[i][k])

print(max(dp[n]))

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
data = []
for _ in range(N):
    a,b,c = [int(x) for x in stdin.readline().rstrip().split()]
    data.append((a,b,c))

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

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

Solution (Python):

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

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

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

Solution (Python):
def solve(n, a, b, c): 
    dp = [[0,0,0] for i in range(n)]
    v = [[a[i], b[i], c[i]] for i in range(n)]
    for i in range(3):
        dp[-1][i] = v[-1][i]
    for i in range(n-2, -1, -1):
        for j in range(3):
            for k in range(3):
                if j != k:
                    dp[i][j] = max(dp[i][j], dp[i+1][k] + v[i][j])
    return max(dp[0])

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())
print(solve(n, a, b, c))