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

ans = max(dp[N])
print(ans)

Solution (Python):
n=int(input())
a,b,c = map(int,input().split())
d={'a':a,'b':b,'c':c}
for i in range(n-1):
    a,b,c = map(int,input().split())
    da,db,dc=d['a'],d['b'],d['c']
    d['a'] = a +max(db,dc)
    d['b'] = b +max(da,dc)
    d['c'] = c +max(da,db)
print(max(d.values()))

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

print(max(dp[n]))

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


dp = [[0,0,0],]

for a,b,c in mX:
    nA = max(dp[-1][1], dp[-1][2]) + a
    nB = max(dp[-1][0], dp[-1][2]) + b
    nC = max(dp[-1][0], dp[-1][1]) + c
    dp.append([nA, nB, nC])

print(max(dp[-1]))

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

vacation = []

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

    vacation.append([a,b,c])

dp = []*N

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

dp[0][0]=vacation[0][0]
dp[0][1]=vacation[0][1]
dp[0][2]=vacation[0][2]

for i in range(0, N-1, 1):

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

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

Solution (Python):

n = int(input())

a = []

for i in range(n):
  a.append([int(x) for x in input().split()])

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

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

print(max(dp[-1]))

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

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


def chmax(i, j):
    diff = max([dp[i-1][x] for x in {0, 1, 2}-{j}])
    if dp[i][j] < ABC[i][j] + diff:
        dp[i][j] = ABC[i][j] + diff
        return True
    return False


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

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

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

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

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

Solution (Python):

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

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

print(max(dp[-1]))

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

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





dp[0][0] = (S[0][0], 'a')
dp[0][1] = (S[0][1], 'b')
dp[0][2] = (S[0][2], 'c')


for i in range(1, N):  
    
    if dp[i-1][1][0]+S[i][0] > dp[i-1][2][0]+S[i][0]:
        dp[i][0] = (dp[i-1][1][0]+S[i][0], 'a')
    else:
        dp[i][0] = (dp[i-1][2][0]+S[i][0], 'a')

    
    if dp[i-1][0][0]+S[i][1] > dp[i-1][2][0]+S[i][1]:
        dp[i][1] = (dp[i-1][0][0]+S[i][1], 'b')
    else:
        dp[i][1] = (dp[i-1][2][0]+S[i][1], 'b')

    
    if dp[i-1][0][0]+S[i][2] > dp[i-1][1][0]+S[i][2]:
        dp[i][2] = (dp[i-1][0][0]+S[i][2], 'c')
    else:
        dp[i][2] = (dp[i-1][1][0]+S[i][2], 'c')


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

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

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

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

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

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

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

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

N = int(input())
ABC = []
for _ in range(N):
    ABC.append([int(v) for v in sys.stdin.readline().strip().split(' ')])


def memoize(f):
    cache = {}
    def helper(x, y):
        if (x, y) not in cache:
            cache[(x, y)] = f(x, y)
        return cache[(x, y)]
    return helper

@memoize
def find(d, p):
    if d == -1:
        return 0
    else:
        if p == 0:
            return max(ABC[d][0] + find(d - 1, 1), ABC[d][0] + find(d - 1, 2))
        elif p == 1:
            return max(ABC[d][1] + find(d - 1, 0), ABC[d][1] + find(d - 1, 2))
        else:
            return max(ABC[d][2] + find(d - 1, 0), ABC[d][2] + find(d - 1, 1))

print(max(find(N - 1, 0), find(N - 1, 1), find(N - 1, 2)))

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

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


for i in range(N):
    if i == 0:
        continue
    
    for j in range(3):
        a = abc[i-1][(j + 1)%3] 
        b = abc[i-1][(j + 2)%3] 
        abc[i][j] += a if a>b else b


print(max(abc[-1]))

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



def plan_vacation(activity, n):
	dp = [0] * 3 
	for i in xrange(3):
		dp[i] = activity[0][i]
	
	for i in xrange(1, n):
		new_dp = [0] * 3
		for j in xrange(3):
			for k in xrange(3):
				if j != k:
					new_dp[j] = max(new_dp[j], dp[k] + activity[i][j])
		dp = new_dp
	return max(dp)
	
	
def read_input():
	
	n = int(sys.stdin.readline())
	activity = [[0]* 3 for i in xrange(n)]
	for i in xrange(n):
		a = sys.stdin.readline().split()
		for j in xrange(3):
			activity[i][j] = int(a[j])
	
	result = plan_vacation(activity, n)
	print result
		
if __name__ == '__main__':
	 read_input()

Solution (Python):
import sys



def plan_vacation(activity, n):
	dp = [[0] * 3 for i in xrange(n)]
	for i in xrange(3):
		dp[0][i] = activity[0][i]
	
	for i in xrange(1, n):
		for j in xrange(3):
			for k in xrange(3):
				if j != k:
					dp[i][j] = max(dp[i][j], dp[i-1][k] + activity[i][j])
	return max(dp[n-1])
	
	
def read_input():
	
	n = int(sys.stdin.readline())
	activity = [[0]* 3 for i in xrange(n)]
	for i in xrange(n):
		a = sys.stdin.readline().split()
		for j in xrange(3):
			activity[i][j] = int(a[j])
	
	result = plan_vacation(activity, n)
	print result
		
if __name__ == '__main__':
	 read_input()

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

dp = [[0 for _ in range(3)] for __ in range(N+100)]
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] + actives[i][k]))

print(max(dp[N]))

Solution (Python):
def main():

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

if __name__ == '__main__':
    print(main())

Solution (Python):
from sys import stdin
from collections import defaultdict
n = int(stdin.readline())

dp = defaultdict(int)
for i in range(0, n):
    cur = [int(i) for i in stdin.readline().split(' ')]
    dp[(i, "a")] = cur[0]+max(dp[(i-1, "b")], dp[(i-1, "c")])
    dp[(i, "b")] = cur[1]+max(dp[(i-1, "a")], dp[(i-1, "c")])
    dp[(i, "c")] = cur[2]+max(dp[(i-1, "a")], dp[(i-1, "b")])

print(max(dp[(n-1, "a")], dp[(n-1, "b")], dp[(n-1, "c")]))

Solution (Python):
n = int(input())
abc = [[0 for i in range(3)] for j in range(n)]
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() ) 
  abc[i][0] = a
  abc[i][1] = b
  abc[i][2] = c

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

  
  


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

Solution (Python):
import sys

def chmin(a,i,b):
  if a[i] > b:
    a[i] = b
    
    return True
  else:
    return False

n = int(input())
abc = [[0 for i in range(3)] for j in range(n)]
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() ) 
  abc[i][0] = a
  abc[i][1] = b
  abc[i][2] = c

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

  
  


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

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

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

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

Solution (Python):
N=int(input())
arr = [int(a) for a in input().split()]
dp = [[arr[0],arr[1],arr[2]],[0,0,0]]
l=1
p=0
for i in range(1, N):
    arr = list(map(int, input().split()))
    for j in range(3):
        for k in range(3):
            if j == k: continue
            dp[l][k] = max(dp[l][k], dp[p][j] + arr[k])
    l=l^1
    p=p^1
            
print(max([dp[p][j] for j in range(3)]))

Solution (Python):
def LIST():
    return list(map(int, input().split()))
N = int(input())
arr = [LIST() for _ in range(N)]
dp = [[arr[0][0],arr[0][1],arr[0][2]],[0,0,0]]
l=1
p=0
for i in range(1, N):
    for j in range(3):
        for k in range(3):
            if j == k: continue
            a1=dp[p][j]
            a2=arr[i][k]
            a3=a1+a2
            dp[l][k] = max(dp[l][k], dp[p][j] + arr[i][k])
    l=l^1
    p=p^1
            
print(max([dp[p][j] for j in range(3)]))

Solution (Python):
n = int(input())
h = []
for _ in range(n):
    a, b, c = [int(x) for x in input().split()]
    h.append((a, b, c))

vals = {}
a, b, c = h[0]
vals[(0, 'A')] = a
vals[(0, 'B')] = b
vals[(0, 'C')] = c

for i in range(1, n):
    a, b, c = h[i]
    vals[(i, 'A')] = max(vals[(i-1, 'B')], vals[(i-1, 'C')]) + a
    vals[(i, 'B')] = max(vals[(i-1, 'A')], vals[(i-1, 'C')]) + b
    vals[(i, 'C')] = max(vals[(i-1, 'B')], vals[(i-1, 'A')]) + c

print(max(vals[(n-1, 'A')], vals[(n-1, 'B')], vals[(n-1, 'C')]))

Solution (Python):
from sys import stdin

numberOfDays = input()
a = []
b = []
c = []

for days in stdin:
    values = days.split(' ')
    a.append(int(values[0]))
    b.append(int(values[1]))
    c.append(int(values[2]))

maxHapNA = [0]
maxHapNB = [0]
maxHapNC = [0]
for day in range(0, len(a)):
    maxHapNA.append(max((maxHapNB[day] + b[day]), (maxHapNC[day] + c[day])))
    maxHapNB.append(max((maxHapNA[day] + a[day]), (maxHapNC[day] + c[day])))
    maxHapNC.append(max((maxHapNA[day] + a[day]), (maxHapNB[day] + b[day])))

print(max(maxHapNA[-1], maxHapNB[-1], maxHapNC[-1]))

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

Solution (Python):
import sys


def LIST():
    return list(map(int, input().split()))


input = sys.stdin.readline

N = int(input())

arr = [LIST() for _ in range(N)]

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

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

print(max([dp[N][j] for j in range(3)]))

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

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
abc=[list(map(int,input().split())) for i in range(n)]
happy=[[0,0,0] for i in range(n)]
happy[0]=abc[0]

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

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


for i in range(n):
    c = list(map(int, input().split()))
    new_dp = [0]*3
    for j in range(3):
        for k in range(3):
            if j != k:
                new_dp[k] = max(new_dp[k], dp[j] + c[k])
    dp = new_dp[:]
print(max(dp))

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

Solution (Python):


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

if N==1:
    print(max(list(map(int,input().split()))))
else:
    for i in range(0,N):
        l=list(map(int,input().split()))
        if i==0:
            dp[0]=l
        else:
            for j in range(3):
                index_l=[0,1,2]
                index_l.pop(j)
                for index in index_l:
                    
                    dp[i][index]=max(dp[i-1][j]+l[index],dp[i][index])

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

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

pa, pb, pc = 0, 0, 0
for _ in range(N) :
    a, b, c = map(int, input().split())
    na = max(pb + a, pc + a)
    nb = max(pa + b, pc + b)
    nc = max(pa + c, pb + c)
    pa, pb, pc = na, nb, nc
print(max([na, nb, nc]))

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

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

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


N = int(input())


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


ABC = [[]] * N

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




for i in range(N):
    '''
             j                     k
    dp[ i ][ 0 ] から dp[ i + 1 ][ 0 ] はcontinue(以下略）
    dp[ i ][ 0 ] から dp[ i + 1 ][ 1 ] への遷移(ABC[i][1])
    dp[ i ][ 0 ] から dp[ i + 1 ][ 2 ] への遷移(ABC[i][2])
    dp[ i ][ 1 ] から dp[ i + 1 ][ 0 ] への遷移(ABC[i][0])
    dp[ i ][ 1 ] から dp[ i + 1 ][ 2 ] への遷移(ABC[i][2])
    dp[ i ][ 2 ] から dp[ i + 1 ][ 0 ] への遷移(ABC[i][0])
    dp[ i ][ 2 ] から dp[ i + 1 ][ 1 ] への遷移(ABC[i][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]+ABC[i][k])

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

print(ans)

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

a = []
b = []
c = []

for _ in range(n):
    ai, bi, ci = [int(i) for i in raw_input().split()]
    a.append(ai)
    b.append(bi)
    c.append(ci)


def vacation_planning(a,b,c):
    n = len(a)
    fa = [0] * n 
    fb = [0] * n
    fc = [0] * n

    fa[0] = a[0]
    fb[0] = b[0]
    fc[0] = c[0]

    for i in range(1, n):
        fa[i] = a[i] + max(fb[i-1], fc[i-1])
        fb[i] = b[i] + max(fa[i-1], fc[i-1])
        fc[i] = c[i] + max(fa[i-1], fb[i-1])

    return max(fa[-1], fb[-1], fc[-1])

print(vacation_planning(a,b,c))

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

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


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

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

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

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

dp = [0 for i in range(nums+1)]
for i in range(len(dp)):
    dp[i] = [0,0,0]

for i in range(nums):
    for x in range(3):
        for y in range(3):
            if x == y: continue
            check = dp[i][x] + ary[i][y]
            if check >= dp[i+1][y]:
                dp[i+1][y] = check

result= 0
for i in range(3):
    if result < dp[nums][i]:
        result = dp[nums][i]
print(result)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N = II()
    happiness = [[] for _ in range(N)]
    for i in range(N):
        happiness[i] = LI()

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

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

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

from collections import defaultdict
dp = defaultdict(int)
for i in range(N):
    dp[i] = [0]*3

for i,v in enumerate(A[0]):
    dp[0][i]=v
    

for i in range(1,N):
    for after in range(3):
        max_value = max([A[i][after] + dp[i-1][before] for before in range(3) if after!=before])
        dp[i][after] = max_value

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

Solution (Python):
import numpy as np
import sys

stdin = sys.stdin
 
sn = lambda : stdin.readline().rstrip()
an = lambda : map(int, stdin.readline().split())
ni = lambda : int(sn())

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

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

for i in range(N):
    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][k])

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

print(ans)

Solution (Python):
def p_c():
    N = int(input())
    before = [0] * 3

    for _ in range(N):
        abc = list(map(int, input().split()))
        for i in range(3):
            abc[i] += max(before[(i + 1) % 3], before[(i + 2) % 3])

        before = abc

    print(max(abc))


if __name__ == '__main__':
    p_c()

Solution (Python):
def p_c():
    N = int(input())
    before = [0] * 3

    for _ in range(N):
        abc = list(map(int, input().split()))
        idx, mv = max(enumerate(before), key=lambda x: x[1])
        before.pop(idx)
        for i in range(len(abc)):
            if i == idx:
                abc[i] += max(before)
            else:
                abc[i] += mv

        before = abc

    print(max(abc))


if __name__ == '__main__':
    p_c()

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

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

for i in range(N):
    for pre_play in range(3):
        now_hpns = three_hpnses[pre_play][i]
        for j in range(1,3):
            next_play = (pre_play+j)%3
            next_hpns = now_hpns + abc_list[next_play][i]
            three_hpnses[next_play][i+1] = max(three_hpnses[next_play][i+1], next_hpns)

print(max([hpnses[-1] for hpnses in three_hpnses]))

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

Solution (Python):
N = int(input())
dp=[[0,0,0] for i in range(N)]
satisfy=[[int(x) for x in input().split()] for i in range(N)]
dp[0]=satisfy[0]
for i in range(N-1):
    dp[i+1][0] = dp[i][1] + satisfy[i+1][0] if dp[i][1]>dp[i][2] else dp[i][2] + satisfy[i+1][0]
    dp[i+1][1] = dp[i][0] + satisfy[i+1][1] if dp[i][0]>dp[i][2] else dp[i][2] + satisfy[i+1][1]
    dp[i+1][2] = dp[i][0] + satisfy[i+1][2] if dp[i][0]>dp[i][1] else dp[i][1] + satisfy[i+1][2]
print(max(dp[-1]))

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
from copy import *

N = int(input())
dp1, dp2 = [0] * 3, [0] * 3
for i in range(1, N+1):
    p = list(map(int, input().split()))
    for j in range(3):
        for k in range(3):
            if j != k:
                dp2[j] = max(dp2[j], dp1[k]+p[j])
    dp1 = deepcopy(dp2)
print(max(dp1))

Solution (Python):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N = int(input())
    actions = []


    for _ in range(N):
        a, b, c = map(int, input().split())
        actions.append((a, b, c))

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

    for day, (a, b, c) in enumerate(actions):
        dp[day + 1][0] = max(dp[day][1], dp[day][2]) + a
        dp[day + 1][1] = max(dp[day][2], dp[day][0]) + b
        dp[day + 1][2] = max(dp[day][0], dp[day][1]) + c

    ans = max(dp[N])
    print(ans)


sol()

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

def main():
    N = int(input())
    X = [list(map(int,input().split())) for _ in range(N)]
    dp = [[0,0,0] for _ in range(N)]
    dp[0][0] = X[0][0]
    dp[0][1] = X[0][1]
    dp[0][2] = X[0][2]
    for i in range(N-1):
        for j in range(3):
            for k in range(3):
                if j == k:
                    continue
                else:
                    dp[i+1][k] = max(dp[i+1][k],dp[i][j]+X[i+1][k])

    print(max(dp[-1]))
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

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

inf = 10**9+7
dp = [[0] * 3 for _ in range(N+10)]
dp[0] = [ABC[0][0],ABC[0][1],ABC[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][j] = max(dp[i+1][j],dp[i][k]+ABC[i+1][j])
        
    

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

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

l = []
for i in range(n):
    s = [int(j) for j in input().split()]
    l.append(s)
dp0 = [0 for i in range(n)]
dp1 = [0 for i in range(n)]
dp2 = [0 for i in range(n)]
dp0[0]=l[0][0]
dp1[0]=l[0][1]
dp2[0]=l[0][2]

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

Solution (Python):

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

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

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

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

for i in range(N):
    for j in range(3):
        beforeMax = max([n for index, n in enumerate(dp[i]) if index != j])
        dp[i + 1][j] = numList[i][j] + beforeMax

print(max(dp[N]))

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

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

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

for i in range(n):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue

            dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + score[i][k])

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

Solution (Python):
def max_points(arr):
	dp = [[0] * (len(arr[0])) for _ in range(len(arr) + 1)]

	for i in range(len(arr)):  
		for j in range(len(arr[0])):  
			max_before = 0
			for k in range(len(arr[0])):
				if k == j:
					continue
				max_before = max(max_before, dp[i][k])
			dp[i+1][j] = arr[i][j] + max_before
	return max(dp[-1])

  
arr = [[int(x) for x in input().strip().split()]for _ in range(int(input().strip()))]
print(max_points(arr))

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

for i in range(N):
    if i == 0:
        yesterday = list(map(int, input().split()))
    else:
        tmp = [0, 0, 0]
        today = list(map(int, input().split()))

        tmp[0] = max([
            yesterday[1] + today[0],
            yesterday[2] + today[0]
        ])

        tmp[1] = max([
            yesterday[0] + today[1],
            yesterday[2] + today[1]
        ])

        tmp[2] = max([
            yesterday[0] + today[2],
            yesterday[1] + today[2]
        ])

        yesterday = tmp

print(max(yesterday))

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

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

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

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

Solution (Python):

def f(A, B, C):
    n = len(A)
    a, b, c = 0, 0, 0 
    for i in range(n):
        a_ = max(b + A[i], c + A[i])
        b_ = max(a + B[i], c + B[i])
        c_ = max(a + C[i], b + C[i])
        a, b, c = a_, b_, c_
    return max(a, b, c)

assert f([10, 20, 30], [40, 50, 60], [70, 80, 90]) == 210

n = int(input())
A, B, C = [], [], []
for _ in range(n):
    a, b, c = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
ans = f(A, B, C)
print(ans)