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.



Sample input:
3
10 40 70
20 50 80
30 60 90


Sample output:
210

Submission status: Accepted

Solution code:
def c():
    n = int(input())
    arr = []
    for _ in range(n):
        line = list(map(int, input().split() ))
        arr.append(line)
    
    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] = arr[i][j]
            else:
                dp[i][j] = arr[i][j] + max([x for ii, x in enumerate(dp[i-1]) if ii != j])

    return max(dp[-1])


print(c())

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
#Atcoder dp educational contest

n = int(input())
l = []

for i in range(n):
    l.append(list(map(int, input().split())))


dp = []
for i in range(n + 1):
    dp.append([-1, -1, -1])

dp[1][0] = l[0][0]
dp[1][1] = l[0][1]
dp[1][2] = l[0][2]

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

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

Submission status: Accepted

Solution code:
n = int(input())
u = [[0,0,0]]
for i in range(n):
    u.append(list(map(int,input().split())))

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
n=int(input())
happy=[[] for i in range(n)]
for i in range(n):
  happy[i]=list(map(int,input().split()))
dp=[[0,0,0] for i in range(n)]
dp[0]=[happy[0][0],happy[0][1],happy[0][2]]
for i in range(1,n):
  #print('i is ',i)
  for j in range(3):#i日目に幸福jを選んだ場合の幸福最大をdp[i][j]とする。
    x=[]
    for k in range(3):
      if k!=j:
        x.append(dp[i-1][k])
    dp[i][j]=max(x)+happy[i][j]
    #print(j,x)
print(max(dp[n-1]))

Submission status: Accepted

Solution code:
N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
dp = [[0] * 3 for i in range(N)]
#dp[i][j]=i日目にjを行った時幸福度
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]))

Submission status: Accepted

Solution code:
n = int(input())

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

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):
    abc = [int(x) for x in input().split()]
    
    for j in range(len(abc)):
        dp[i][j] = max(dp[i - 1][(j + 1) % 3] + abc[j], dp[i - 1][(j + 2) % 3] + abc[j])

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [[-float("inf") for x in range(3)] for x in range(n)]
dp[0] = list(map(int,input().split()))
for i in range(1,n):
    a = list(map(int,input().split()))
    for x in range(3):
        for y in range(3):
            if(x == y):
                continue
            if(dp[i-1][x]+a[y]>dp[i][y]):
                dp[i][y] = dp[i-1][x]+a[y]
print(max(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())
abc = [list(map(int, input().split())) for _ in range(n)] 
happy = [[0, 0, 0] for _ in range(n+1)]
for i in range(n):
    for j in range(3):
        happy[i + 1][j % 3] = abc[i][j % 3] + max(happy[i][(j + 1) % 3], happy[i][(j + 2) % 3])
print(max(happy[-1][i] for i in range(3)))

Submission status: Accepted

Solution code:
N = int(input())
plans = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (3) for _ 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
            else:
                dp[i+1][k] = chmax(dp[i+1][k], dp[i][j] + plans[i][k])
                
res = 0
for j in range(3):
    res = chmax(res, dp[-1][j])
print(res)

Submission status: Accepted

Solution code:
N = int(input())

last_a = 0
last_b = 0
last_c = 0

for _ in range(N):
    a, b, c = map(int, input().split())
    last_a, last_b, last_c = a + max(last_b, last_c), b + max(last_c, last_a), c + max(last_a, last_b)

print(max(last_a, last_b, last_c))

Submission status: Accepted

Solution code:
def resolve():
	n = int(input())
	dp = [[0]*3 for _ in range(n+1)]
	for i in range(1, n+1):
		nums = list(map(int, input().split()))
		for j in range(3):
			for k in range(3):
				if j == k:
					continue
				dp[i][j] = max(dp[i][j], nums[j] + dp[i-1][k])
	print(max(dp[-1]))
resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

n = inp()
dp = [[0] * 3 for i in range(n+1)]
for i in range(n):
    work = inpl()
    for j in range(3):
        option = [dp[i][k] + work[k] for k in range(3) if j != k]
        dp[i + 1][j] = max(option)
print(max(dp[n]))

Submission status: Accepted

Solution code:
n = int(input())
lst = [list(map(int, input().split())) for i in range(n)]
ans = [[0]*3 for i in range(n)]
ans[0] = lst[0]
for i in range(1, n):
  ans[i][0] = lst[i][0] + max(ans[i-1][1], ans[i-1][2])
  ans[i][1] = lst[i][1] + max(ans[i-1][0], ans[i-1][2])
  ans[i][2] = lst[i][2] + max(ans[i-1][0], ans[i-1][1])

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

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
n=int(input())
satis=[]

for i in range(n):
	satis.extend(map(int,input().split()))

tempA=satis[0]
tempB=satis[1]
tempC=satis[2]
if n > 1:
  for i in range(n-1):
    tempA2=satis[3*i+3]+max([tempB,tempC])
    tempB2=satis[3*i+4]+max([tempA,tempC])
    tempC2=satis[3*i+5]+max([tempA,tempB])
    tempA=tempA2
    tempB=tempB2
    tempC=tempC2
  print(max([tempA,tempB,tempC]))
else:
  print(max([tempA,tempB,tempC]))

Submission status: Accepted

Solution code:
n=int(input())
satis=[]

for i in range(n):
  A=list(map(int,input().split()))
  satis.extend(A)

tempA=satis[0]
tempB=satis[1]
tempC=satis[2]
if n > 1:
  for i in range(n-1):
    tempA2=satis[3*i+3]+max([tempB,tempC])
    tempB2=satis[3*i+4]+max([tempA,tempC])
    tempC2=satis[3*i+5]+max([tempA,tempB])
    tempA=tempA2
    tempB=tempB2
    tempC=tempC2
  print(max([tempA,tempB,tempC]))
else:
  print(max([tempA,tempB,tempC]))

Submission status: Accepted

Solution code:
# inputを高速化する。
import sys
input = sys.stdin.readline

n = int(input())

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

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

    if i == 0:
        count[i][0] = a
        count[i][1] = b
        count[i][2] = c

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

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

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-04-29 10:32
# @url:https://atcoder.jp/contests/dp/tasks/dp_c
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

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

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

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

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


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


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    n=int(input())
    nums=[list(map(int,input().split())) for i in range(n)]
    dp=[[0]*3 for i in range(n)]
    dp[0]=nums[0]
    for i in range(1,n):
        for j in range(3):
            if j==0:
                dp[i][j]=max(dp[i-1][j+1],dp[i-1][j+2])+nums[i][j]
            elif j==1:
                dp[i][j]=nums[i][j]+max(dp[i-1][j-1],dp[i-1][j+1])
            elif j==2:
                dp[i][j]=max(dp[i-1][j-1],dp[i-1][j-2])+nums[i][j]
    print (max(dp[n-1]))
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)

n = int(input())
 
m ={}
def dp(i, a, b, c):
	if (i,a,b,c) in m:
		return m[(i,a,b,c)]
	if i == -1: return 0
	a_v = dp(i-1, a=False, b=True, c=True) + al[i] if a else -1
	b_v = dp(i-1, a=True, b=False, c=True) + bl[i] if b else -1
	c_v = dp(i-1, a=True, b=True, c=False) + cl[i] if c else -1
	m[(i,a,b,c)] = max([a_v, b_v, c_v])
	return max([a_v, b_v, c_v])
 
al = []
bl = []
cl = []
for i in range(n):
	a, b, c = list(map(int, input().split(" ")))
	al.append(a)
	bl.append(b)
	cl.append(c)
    
print(dp(n-1, a=True, b=True, c=True))

Submission status: Accepted

Solution code:
N = int(input())
x, y, z = 0, 0, 0
for _ in range(N):
    a, b, c = map(int, input().split())
    x, y, z = max(y, z) + a, max(z, x) + b, max(x, y) + c
print(max(x, y, z))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

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

dp = [[0,0,0] for i in range(N)]
dp[0] = [a[0],b[0],c[0]]

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

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

Submission status: Accepted

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

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

print(max(dp[-1]))

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
abc = []
ia, ib, ic = map(int, input().split())
for _ in range(n-1):
    a, b, c = map(int, input().split())
    abc.append((a, b, c))

dp = [ia, ib, ic]

for a, b, c in abc:
    newdp = [None]*3
    newdp[0] = max(dp[1], dp[2]) + a
    newdp[1] = max(dp[2], dp[0]) + b
    newdp[2] = max(dp[0], dp[1]) + c
    dp = newdp

print(max(dp))

Submission status: Accepted

Solution code:
N=int(input())
ABC=[[0,0,0]]
for i in range(N):
	ABC+=[[int(i) for i in input().split()]]
DP=[[0,0,0] for i in range(N+1)]
for i in range(N):
	for j in range(3):
		DP[i+1][j]=ABC[i+1][j]+max(DP[i][(j+1)%3],DP[i][(j+2)%3])
print(max(DP[N]))

Submission status: Accepted

Solution code:
N=int(input())
ABC=[]
for i in range(N):
	ABC+=[[int(i) for i in input().split()]]
DP=[[0,0,0] for i in range(N+1)]
for i in range(N):
	for j in range(3):
		DP[i][j]=ABC[i][j]+max(DP[i-1][(j+1)%3],DP[i-1][(j+2)%3])
print(max(DP[N-1]))

Submission status: Accepted

Solution code:
n = int(input())
abc = []
for i in range(n):
    abc.append([int(i) for i in input().split()])

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

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

Submission status: Accepted

Solution code:
N=int(input())
ABC=[]
for i in range(N):
	ABC+=[[int(i) for i in input().split()]]
DP=[[0,0,0] for i in range(N)]
for i in range(N):
	DP[i]=[ABC[i][0]+max(DP[i-1][1],DP[i-1][2]),ABC[i][1]+max(DP[i-1][0],DP[i-1][2]),ABC[i][2]+max(DP[i-1][1],DP[i-1][0])]
print(max(DP[N-1]))

Submission status: Accepted

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

ans = [a[0]]

for i in range(1, n):
    t = [0,0,0]
    for j in range(3):
        t[j] = max([ans[i-1][k] + a[i][j] if k != j else 0 for k in range(3)])
    ans.append(t)
    #print(ans)
print(max(ans[n-1]))

Submission status: Accepted

Solution code:
def knapsack(points):
    days = len(points)

    # dp[i][j] is the max points we can get at day i and choosing activity j
    dp = [[0] * 3 for _ in range(days)]
    dp[0] = points[0]
    for i in range(1, days):
        for j in range(3):
            dp[i][j] = points[i][j] + max([dp[i-1][k] for k in range(3) if k != j])
    return max(dp[-1])


if __name__ == "__main__":
    N = int(input())
    points = []
    for _ in range(N):
        points.append([int(x) for x in input().split()])

    print(knapsack(points))

Submission status: Accepted

Solution code:
n = int(input())
a = [[0]*3 for i in range(n+1)]

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

# dp[i][j] = i日目にjの活動を行なった場合の幸福度の最大値
dp = [[0]*3 for i in range(n+1)]
dp[1] = a[1]

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
def knapsack(points):
    days = len(points)

    # dp[i][j] is the max points we can get at day i and choosing activity j
    dp = [[0]*3] * days
    dp[0] = points[0]
    for i in range(1, days):
        newdp = [0] * 3
        for j in range(3):
            newdp[j] = points[i][j] + max([dp[i-1][k] for k in range(3) if k != j])
            #dp[i][j] = points[i][j] + max([dp[i-1][k] for k in range(3) if k != j])
        dp[i] = newdp

    return max(dp[-1])


if __name__ == "__main__":
    N = int(input())
    points = []
    for _ in range(N):
        points.append([int(x) for x in input().split()])

    print(knapsack(points))

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
X = np.array([input().split() for _ in range(n)], np.int64)
dp = np.zeros((n + 1, 3), np.int64)
dp[0, 0] = dp[0, 1] = dp[0, 2] = 0
for i in range(n):
    for j in range(3):
        dp[i + 1, j] = X[i, j] + max(dp[i, k] for k in range(3) if j != k)
print(max(dp[n]))

Submission status: Accepted

Solution code:
# coding: utf-8
import numpy as np

n = int(input())
dp = np.zeros((n+10, 3))

def cmax(a,b):
    if a>b:
        return a
    else: 
        return b
        
for i in range(1, n+1):
    a, b, c = map(int, input().split())
    # a
    dp[i][0] = cmax(dp[i-1][1]+a, dp[i-1][2]+a)
    # b
    dp[i][1] = cmax(dp[i-1][0]+b, dp[i-1][2]+b)
    # c
    dp[i][2] = cmax(dp[i-1][0]+c, dp[i-1][1]+c)

print(int(max(dp[i,:])))

Submission status: Accepted

Solution code:
n=input()
a=[map(int,raw_input().split()) for _ in xrange(n)]
z=[[0]*3 for _ in xrange(n)]
z[0]=a[0]
for i in xrange(1,n):
    for j in xrange(3):
        for k in xrange(3):
            if j!=k:
                z[i][j]=max(z[i][j],z[i-1][k]+a[i][j])
print max(z[-1])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
options = [None] * N
for i in range(N):
    options[i] = tuple(int(x) for x in readline().split())


def solve():
    da, db, dc = 0, 0, 0
    for i in range(N):
        xa, xb, xc = options[i]
        xa += da
        xb += db
        xc += dc
        da, db, dc = max(xb, xc), max(xa, xc), max(xa, xb)
    print(max(da, db, dc))


if __name__ == "__main__":
    solve()

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=[]
b=[]
c=[]
for i in range(n):
    A,B,C=map(int,input().split())
    a.append(A)
    b.append(B)
    c.append(C)

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

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

Submission status: Accepted

Solution code:
N = int(input())
abc = [tuple(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):
    dp[i+1][j] = max(dp[i][j-1], dp[i][j-2]) + abc[i][j]
    
print(max(dp[-1]))

Submission status: Accepted

Solution code:
t=int(input())
a=[[0 for i in range(3)] for j in range(t)]
res=0
for i in range (t):
  a[i][0],a[i][1],a[i][2]=list(map(int, input().split()))
 
   
dp = [[0] * 3 for _ in range(t + 1)]
#for i in range(3):
#  dp[0][i]=a[0][i]
 # res=max(res,dp[0][i])
for i in range (0,t):
  for curr in range(3):
    for last in range(3):
      if last!=curr:
        dp[i+1][curr]=max(dp[i+1][curr],dp[i][last]+a[i][curr])
    
    if i==t-1:
      res=max(res,dp[i+1][curr])
      
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
ABC = [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:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][k] + ABC[i][j])

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys

# import os
# path = os.getcwd()
# path = os.path.join(path,"input.txt")
# sys.stdin = open(path)

input = sys.stdin.readline
import numpy as np
N = int(input())
abc = np.zeros((N,3))
for i in range(N):
    abc[i] = list(map(int,input().split()))

dp = np.zeros((N,3))
for i in range(N):
    if i == 0:
        dp[i] = abc[i]
        continue
    dp_a,dp_b,dp_c = dp[i-1]
    dp[i] = abc[i] + [max(dp_b,dp_c),max(dp_a,dp_c),max(dp_a,dp_b)]
print(int(max(dp[N-1])))

Submission status: Accepted

Solution code:
def solve(h):
    dp = [h[0]]
    for i in range(1, len(h)):
        a = h[i][0] + max(dp[i-1][1], dp[i-1][2])
        b = h[i][1] + max(dp[i-1][0], dp[i-1][2])
        c = h[i][2] + max(dp[i-1][0], dp[i-1][1])
        dp.append([a, b, c])
    return max(dp[-1])


if __name__ == "__main__":
    h = [[int(x) for x in input().split()] for y in range(int(input()))]
    print(solve(h))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
from sys import stdin,stdout
n=int(stdin.readline())
p,q,r=map(int,stdin.readline().split())
for i in range(1,n):
    a,b,c=map(int,stdin.readline().split())
    p1=max(a+q,a+r)
    q1=max(b+p,b+r)
    r1=max(c+p,c+q)
    p,q,r=p1,q1,r1
stdout.write(str(max(p,q,r))+'\n')

Submission status: Accepted

Solution code:
import numpy as np
import math

def solve():
    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 i in range(n+5)]
    for i in range(1,n+1):
        dp[i][0] = max(dp[i-1][1]+a[i-1],dp[i-1][2]+a[i-1])
        dp[i][1] = max(dp[i-1][0]+b[i-1],dp[i-1][2]+b[i-1])
        dp[i][2] = max(dp[i-1][0]+c[i-1],dp[i-1][1]+c[i-1])
    print(max(dp[n]))
    return 0
 
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
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] = ABC[0]
if N>1:
    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[-1]))

Submission status: Accepted

Solution code:
n = int(input())
l = []
for _ in range(n):
    a, b, c = map(int, input().split())
    l.append([a, b, c])

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

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
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(1,n+1):
    dp[i][0]=max(dp[i-1][1]+abc[i-1][0],dp[i-1][2]+abc[i-1][0])
    dp[i][1]=max(dp[i-1][0]+abc[i-1][1],dp[i-1][2]+abc[i-1][1])
    dp[i][2]=max(dp[i-1][0]+abc[i-1][2],dp[i-1][1]+abc[i-1][2])
print(max(dp[n]))

Submission status: Accepted

Solution code:
import numpy as np

# 1つ前で何をしていたかのみに依存する
def main():
	N = int(input())

	dp = np.zeros((N, 3), dtype=int)

	h = list(map(int, input().split(" ")))
	dp[0,0], dp[0,1], dp[0,2] = h

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

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

if __name__ == '__main__':
	main()

Submission status: Accepted

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

#dp[i+1][j]:i日目までの活動履歴のうち、最終日である i 日目には活動 j (0: A, 1: B, 2: C) を選んだ場合の、得られる幸福度の最大値

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

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
N = int(input())

# kth entry: [max up to ak, bk, ck]
max_happiness = [[None] * 3 for _ in range(N)]

for k in range(N):
    if k == 0:
        max_happiness[k] = [int(n) for n in input().split()]
    else:
        ak, bk, ck = [int(n) for n in input().split()]

        a_opt, b_opt, c_opt = max_happiness[k-1]
        max_happiness[k][0] = ak + max(b_opt, c_opt)
        max_happiness[k][1] = bk + max(a_opt, c_opt)
        max_happiness[k][2] = ck + max(a_opt, b_opt)

print(max(max_happiness[-1]))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    matrix = []
    tb = [[0] * 4 for _ in range(n + 1)]
    for _ in range(n):
        matrix.append([int(e) for e in input().split()])
    
    for i in range(1, n + 1):
        for j in range(1, 4):
            for l in range(1, 4):
                if j == l: continue
                tb[i][j] = max(tb[i][j], tb[i - 1][l] + matrix[i - 1][j - 1])
    
    print(max(tb[n]))
    return 0

if __name__ == "__main__":
    main()

Submission status: Accepted

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

print(max(dp[-1]))

Submission status: Accepted

Solution code:
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):
  dp[i+1][0] = max(dp[i][1],dp[i][2])+l[i][0]
  dp[i+1][1] = max(dp[i][0],dp[i][2])+l[i][1]
  dp[i+1][2] = max(dp[i][0],dp[i][1])+l[i][2]
print(max(dp[n]))

Submission status: Accepted

Solution code:
N=int(input())
dp=[ [0,0,0] for i in range(N) ]

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

Submission status: Accepted

Solution code:
import sys
import numpy as np 

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

x, y, z = 0, 0, 0
for a, b, c in h:
    x, y, z = max(y, z) + a, max(x, z) + b, max(x, y) + c

print(max(x, y, z))