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())
abc = [list(map(int, input().split())) for _ in range(n)]
ans = [[0]*3 for _ in range(n)]

ans[0][0] = abc[0][0]
ans[0][1] = abc[0][1]
ans[0][2] = abc[0][2]

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

print(max(ans[-1]))

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


N = int(input())
abc_list = []
for _ in range(N):
    abc_list.append([int(x) for x in input().split()])

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

print(max(dp[-1]))

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

for _ in range(n):
  li.append(list(map(int, input().split())))

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

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

print(max(dp[n]))

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

Solution (Python):
from __future__ import division, print_function

def main():
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    dp = [[0 for _ in range(3)] for _ in range(n)]
    for i in range(n):
        if i == 0:
            dp[i][0] = a[i][0]
            dp[i][1] = a[i][1]
            dp[i][2] = a[i][2]
            continue
            
        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][0], dp[i - 1][1])

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



py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

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

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

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')


import math
import collections

from collections import Counter
from math import fabs

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
activities = []
plans = ['A', 'B', 'C']
for _ in range(N):
    activities.append(tuple(map(int, input().split())))
dp = {i: {p: 0 for p in plans} for i in range(1, N+1)}
for i, p in enumerate(plans):
    dp[1][p] = activities[0][i]
for i in range(2, N+1):
    a, b, c = activities[i-1]
    dp[i]['A'] = max([dp[i-1][p] + a for p in plans if p != 'A'])
    dp[i]['B'] = max([dp[i-1][p] + b for p in plans if p != 'B'])
    dp[i]['C'] = max([dp[i-1][p] + c for p in plans if p != 'C'])
print(max([dp[N][p] for p in plans]))

Solution (Python):
n=int(input())
dp=[0,0,0]
for i in range(n):
    a=list(map(int,input().split()))
    dpn=[0,0,0]
    for j in range(3):
        
        for k in range(3):
            if(j!=k):
                dpn[k]=max(dpn[k],dp[j]+a[k])
        
    dp=dpn.copy()
    
print(max(dp))

Solution (Python):

import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


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

    for i, (ca, cb, cc) in enumerate(zip(a, b, c)):
        dp[i + 1][0] = max(dp[i][1], dp[i][2]) + ca
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + cb
        dp[i + 1][2] = max(dp[i][0], dp[i][1]) + cc
    return max(dp[-1])


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))
    result = solve(N, a, b, c)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

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

n = int(input())
dp = [[-float("inf"),-float("inf"),-float("inf")] for i in range(n+1)]

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

dp[0] = [0]*3
dp[1] = a[0]

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

Solution (Python):
import numpy as np
N = int(input())
dp = np.zeros((N,3))
a,b,c = map(int,input().split())
dp[0][0] = a
dp[0][1] = b
dp[0][2] = c
for i in range(1,N):
  a,b,c = map(int,input().split())
  dp[i][0] = max(dp[i-1][1]+a,dp[i-1][2]+a)
  dp[i][1] = max(dp[i-1][0]+b,dp[i-1][2]+b)
  dp[i][2] = max(dp[i-1][1]+c,dp[i-1][0]+c)
print(int(np.max(dp)))

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

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

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

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

today_a,today_b,today_c=0,0,0
for i in range(n) : 
    a,b,c=map(int,input().split()) 
    tomorrow_a=a+max(today_b,today_c)
    tomorrow_b=b+max(today_a,today_c)
    tomorrow_c=c+max(today_a,today_b)

    today_a=tomorrow_a
    today_b=tomorrow_b
    today_c=tomorrow_c

print(max(tomorrow_a,tomorrow_b,tomorrow_c))

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

h1, h2, h3 = [0] * N, [0] * N, [0] * N

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

Solution (Python):
N=int(input())
A=[]
for i in range(N):
    a=list(map(int,input().split()))
    A.append(a)
INF=10**9
dp=[[0]*3 for i in range(N+1)]

dp[0][0]=dp[0][1]=dp[0][2]=0
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][0],dp[N][1],dp[N][2]))

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

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

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

print(max(dp[-1]))

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

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

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

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
ABC = [list(map(int,input().split())) for i in range(N)]

dp = [0]*(N+1)
dp[0] = [0,0,0]

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

print(max(dp[N]))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
ABC = [list(map(int,input().split())) for i in range(N)]

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

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

print(max(dp[N]))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
ABC = [list(map(int,input().split())) for i in range(N)]

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

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-1][k]+ABC[i-1][j],dp[i][j])

print(max(dp[N]))

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

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

Solution (Python):

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

print(max(dp[-1]))

Solution (Python):
import sys

N = int(input())
dpa, dpb, dpc = 0, 0, 0
for _ in range(N):
    a, b, c = map(int, sys.stdin.readline().split())
    dpa1 = a + max(dpb, dpc)
    dpb1 = b + max(dpc, dpa)
    dpc1 = c + max(dpa, dpb)
    dpa, dpb, dpc = dpa1, dpb1, dpc1 
print(max(dpa, dpb, dpc))

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

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

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

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

ans = max(dp[N-1])

print(ans)

Solution (Python):

import sys


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    INF = 0
    dp = [[INF] * (N+1) for i in range(3)]

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

    print(max(dp[0][N], dp[1][N], dp[2][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):
from __future__ import division, print_function

def main():
    n = int(input())
    dp = [0, 0, 0]
    for _ in range(n):
        curr_dp = [0, 0, 0]
        c = [int(_) for _ in input().split()]
        for i in range(3):
            for j in range(3):
                if i != j:
                    curr_dp[j] = max(curr_dp[j], dp[i] + c[j])

        dp = curr_dp

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



py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

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

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

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')


import math
import collections

from collections import Counter
from math import fabs

if __name__ == "__main__":
    main()

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

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

Solution (Python):
n = int(input())
dp = [[0, 0, 0] for i in range(n+1)]
for i in range(n):
  a, b, c = map(int, input().split())
  dp[i+1][0] = max(dp[i][1]+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 problem():
    N = int(input())
    activityList = []
    for i in range(N):
      row = list(map(int, input().split()))
      activityList.append(row)

    print(algorithm(N,activityList))

def algorithm(N, activityList):
  dp = [[0, 0, 0] for i in range(N+ 1)]

  for index in range(1, N + 1):
    for j in range(3):
      for k in range(3):
        if j == k:
          continue
        if dp[index][j] < dp[index - 1][k] + activityList[index-1][j]:
          dp[index][j] = dp[index - 1][k] + activityList[index-1][j]
      
  return max(dp[N])

problem()

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

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

for i in range(N):
    row = input().split()
    abc = [int(n) for n in row]
    abcs.append(abc)
    if i == 0:
        dp[0][0] = abc[0]
        dp[0][1] = abc[1]
        dp[0][2] = abc[2]
    else:
        dp[i][0] = max([abc[0] + dp[i-1][1], abc[0] + dp[i-1][2]])
        dp[i][1] = max([abc[1] + dp[i-1][0], abc[1] + dp[i-1][2]])
        dp[i][2] = max([abc[2] + dp[i-1][0], abc[2] + dp[i-1][1]])

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

Solution (Python):
N = int(input())
sel = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * 3 for _ in range(N+1)]

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

print(max(dp[N]))

Solution (Python):
N = int(input())
sel = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * 3 for _ in range(N+1)]

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

print(max(dp[N]))

Solution (Python):
import sys
import numpy as np

input = sys.stdin.readline

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 = np.zeros((N, 3))
DP[0, 0] = A[0]
DP[0, 1] = B[0]
DP[0, 2] = C[0]

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

print(int(max(DP[-1, 0], DP[-1, 1], DP[-1, 2])))

Solution (Python):
import fileinput


def chose_action_prev(current_action, last_best_rewards):
    return max((v, idx) for idx, v in enumerate(last_best_rewards) if idx != current_action)[1]


def vacation(action_values):
    last_best_rewards = [0, 0, 0]
    current_best_rewards = [0, 0, 0]

    for vals_for_day in action_values:
        for action, rev in enumerate(vals_for_day):
            prev_action = chose_action_prev(action, last_best_rewards)
            current_best_rewards[action] = last_best_rewards[prev_action] + rev

        last_best_rewards = current_best_rewards
        current_best_rewards = [0, 0, 0]

    return max(last_best_rewards)


inp = fileinput.input()
line_count = int(inp.readline())

action_vals = []
for _ in range(line_count):
    action_vals.append([int(v) for v in inp.readline().split(" ")])

print(vacation(action_vals))

Solution (Python):



def get_inputs():
    n = int(input())
    hap = []
    for _ in range(n):
        hap.append([int(x) for x in input().split()])
    
    return n, hap


if __name__ == "__main__":
    n, hap = get_inputs()
    
    dp = [[0, 0, 0] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        
        dp[i][0] = hap[i - 1][0] + max(dp[i - 1][1], dp[i - 1][2])
        
        dp[i][1] = hap[i - 1][1] + max(dp[i - 1][0], dp[i - 1][2])
        
        dp[i][2] = hap[i - 1][2] + max(dp[i - 1][0], dp[i - 1][1])
    
    print(max(dp[n]))

Solution (Python):

"""
C - Vacation
https://atcoder.jp/contests/dp/tasks/dp_c

"""
import sys


def solve(N, acivities):
    pre_A, pre_B, pre_C = 0, 0, 0
    for a, b, c in acivities:
        aa = a + max(pre_B, pre_C)
        bb = b + max(pre_A, pre_C)
        cc = c + max(pre_A, pre_B)
        pre_A, pre_B, pre_C = aa, bb, cc
    return max(pre_A, pre_B, pre_C)


def main(args):
    N = int(input())
    acivities = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(N, acivities)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
n=int(input())
d=[]
for i in range(n):
    ai,bi,ci=map(int,input().split())
    d.append([ai,bi,ci])

if n==1:
    print(max(d[0][0],d[0][1],d[0][2]))
    exit()
    

ap=d[0][0]
bp=d[0][1]
cp=d[0][2]

for i in range(1,n):
    a=max(bp+d[i][0],cp+d[i][0])
    b=max(ap+d[i][1],cp+d[i][1])
    c=max(ap+d[i][2],bp+d[i][2])

    ap=a
    bp=b
    cp=c
    

print(max(a,b,c))

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

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

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

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

dp = [[0]*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]+L[i][k])

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

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

    a += max(B, C)
    b += max(A, C)
    c += max(A, B)

    A, B, C = a, b, c

print(max(A, B, C))

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

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

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

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

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

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

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


if __name__ == '__main__':
    ans = c()
    print(ans)

Solution (Python):
def larger(x, y):
	if x > y: return x
	return y

N = int(input())
dpa = [0]
dpb = [0]
dpc = [0]
for i in range(0, N):
	a, b, c = map(int, input().split())
	if i == 0:
		dpa.append(a)
		dpb.append(b)
		dpc.append(c)
	else:
		newa = larger(dpb[-1], dpc[-1])+a
		newb = larger(dpa[-1], dpc[-1])+b
		newc = larger(dpa[-1], dpb[-1])+c
		dpa.append(newa)
		dpb.append(newb)
		dpc.append(newc)
print(larger(larger(dpa[-1], dpb[-1]), dpc[-1]))

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

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

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

prea, preb, prec = a[0], b[0], c[0]

for i in range(1, n):
    prea, preb, prec = max(preb, prec) + a[i], max(prea, prec) + b[i], max(preb, prea) + c[i]

print(max(prea, preb, prec))

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

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

happy = [[0] * 3 for _ in range(N)]
for i in range(3):
	happy[0][i] = abc[0][i]

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

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

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

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

happy = [[0] * 3 for _ in range(N)]
for i in range(3):
	happy[0][i] = abc[0][i]

for i in range(1, N):
	for j in range(3):
		for k in range(3):
			if j != k and happy[i][j] < happy[i - 1][k]:
				happy[i][j] = happy[i - 1][k]
		happy[i][j] += abc[i][j]

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

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

happy = [abc[0]]

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

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

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

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

dp = [{} for _ in range(N+1)]
dp[0]["a"] = a_s[0]
dp[0]["b"] = b_s[0]
dp[0]["c"] = c_s[0]

for i in range(1, N):
    dp[i]["a"] = max(dp[i-1]["b"]+a_s[i],
                     dp[i-1]["c"]+a_s[i])
    dp[i]["b"] = max(dp[i-1]["a"]+b_s[i],
                     dp[i-1]["c"]+b_s[i])
    dp[i]["c"] = max(dp[i-1]["a"]+c_s[i],
                     dp[i-1]["b"]+c_s[i])
    
print(max(dp[N-1]["a"], dp[N-1]["b"], dp[N-1]["c"]))

Solution (Python):
def sub():
    N = int(input())
    buf_abc = [[int(e) for e in input().split()] for _ in range(N)]
    
    class ZeroDict(dict):
        def __missing__(self, key):
            self[key] = 0 
            return 0

    dp_table = ZeroDict()
    
    dp_table[(1, 0)] = buf_abc[0][0]
    dp_table[(1, 1)] = buf_abc[0][1]
    dp_table[(1, 2)] = buf_abc[0][2]
    for i in range(1, N):
        for j, (k,l) in enumerate([[1,2], [0,2], [0,1]]):
            candi = max(dp_table[(i, k)]+buf_abc[i][j], dp_table[(i, l)]+buf_abc[i][j])
            dp_table[(i+1,j)] = max(candi, dp_table[(i+1,j)])

    vv = [dp_table[(N, i)] for i in range(3)]
    print(max(vv))
    
    
    

sub()

Solution (Python):
N = input()
act = []
new = []

for i in range(0,N):
	act.append(raw_input().split(' '))

for i in act:
	tli = []
	for j in i:
		tli.append(int(j))
	new.append(tli)

ans = []

for i in range(0,N):
	emp = [0]*3
	ans.append(emp)


for i in range(0,N):
	for j in range(0,3):
		if(i == 0):
			ans[i][j] = new[i][j]

		else:
			m = -99999	
			for x in range(0,3):
				if(x != j):
					if(m < ans[i-1][x]):
						m = ans[i-1][x]

			ans[i][j] = new[i][j] + m

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

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

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

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

print(max(dp[-1]))

Solution (Python):

import sys


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    dp = [[0 for i in range(3)] for j in range(N)]
    
    ml = list(zip(a,b,c))

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

    for i,m in enumerate(ml[1:]):
        i += 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]+m[j])

    print(max(dp[-1]))
    




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):
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def mi(): return map(int, input().split())


def li(): return list(mi())


def li_(): return [int(x) - 1 for x in input().split()]


def lin(n: int): return [input() for _ in range(n)]


def llin(n: int): return [li() for _ in range(n)]


def llin_(n: int): return [li_() for _ in range(n)]


def lli(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def f(): return float(input())


def s(): return input().replace('\n', '')


def main():
    N = I()
    ABC = llin(N)
    dp = [[0] * 3 for _ in range(N)]
    dp[0] = ABC[0]
    for i in range(1, N):
        for j in range(3):
            dp[i][j] = max((ABC[i][j]+dp[i - 1][k]
                            for k in range(3) if k != j))
    print(max(dp[N-1]))


if __name__ == '__main__':
    main()

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

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

dp[0][0] = arr[0][0]
dp[0][1] = arr[0][1]
dp[0][2] = arr[0][2]

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

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

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

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