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:
n = int(input())
hap = []
for i in range(n):
    hap += [[int(i) for i in input().split()]]
dp =[[0,0,0] for i in range(n+1)]
for i in range(1,n+1):
    if i == 1:
        dp[1] = hap[0] 
    else:
        for j in range(3):
            dp[i][j] = max(dp[i-1][(j+1)%3]+hap[i-1][j],dp[i-1][(j+2)%3]+hap[i-1][j])
print(max(dp[n]))

Submission status: Accepted

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

DP = [0, 0, 0]

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

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

print(max(DP))

Submission status: Accepted

Solution code:
import sys
import heapq

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

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

Submission status: Accepted

Solution code:
n = int(input())
v = tuple(tuple(map(int, input().split())) for _ in range(n))
e = tuple(zip(*v))
# e[j][i(0-indexed)]:=i日目に活動jして得る幸福度
# print(e)

dp = tuple([0] * 3 for _ in range(n + 1))
# dp[i(1-indexed)][j]:=i日目に活動jした最大幸福度

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

for _ in range(N):
	a, b, c = list(map(int, input().split()))
	happy[0].append(a)
	happy[1].append(b)
	happy[2].append(c)
	
dp = [[0 for _ in range(3)] for _ in range(N + 1)]

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

Submission status: Accepted

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

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

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

print(max(dp[n]))

Submission status: Accepted

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

dp = [[0]*3 for _ in range(n)]#[0]*nではない
dp[0] = [a[0],b[0],c[0]] 
for i in range(1,n):
    dp[i][0] = max([dp[i-1][1],dp[i-1][2]])+a[i]
    dp[i][1] = max([dp[i-1][0],dp[i-1][2]])+b[i]
    dp[i][2] = max([dp[i-1][0],dp[i-1][1]])+c[i]
print(max(dp[n-1]))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
#C - Vacation

n=int(input())
a=[]
b=[]
c=[]
for i in range(n):
    ak,bk,ck=map(int,input().split())
    a.append(ak)
    b.append(bk)
    c.append(ck)
hy=[]
for i in range(n):
    hy.append([0,0,0])
#hy[n-1]まで埋める
#0日目を埋めておく
hy[0][0]=a[0]
hy[0][1]=b[0]
hy[0][2]=c[0]

    
for i in range(1,n):
#    hy.append([])
    hy[i][0] = max(hy[i-1][1]+a[i],hy[i-1][2]+a[i])#hy[i][a]を求める
    hy[i][1] = max(hy[i-1][0]+b[i],hy[i-1][2]+b[i])#hy[i][a]を求める
    hy[i][2] = max(hy[i-1][0]+c[i],hy[i-1][1]+c[i])#hy[i][a]を求める

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

Submission status: Accepted

Solution code:
N = int(input())

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

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

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

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

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

print(max(dp[-1]))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

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

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

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)
dpa,dpb,dpc = A[0],B[0],C[0]
for i in range(1,N):
    a,b,c = dpa,dpb,dpc
    dpa = max(c,b)+A[i]
    dpb = max(c,a)+B[i]
    dpc = max(a,b)+C[i]
print(max(dpa,dpb,dpc))

Submission status: Accepted

Solution code:


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

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

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

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

Submission status: Accepted

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

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

print(max(dp))

Submission status: Accepted

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

dp = [[0 for _ in range(3)] for _ in range(N+1)] # i日目までの活動で最終i日目に活動jを行った時の幸福度の最大値をdp[i][j]にしまう

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

# dp[i][k] := day-i, last is k
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]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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)]
# print(dp)
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(dp)  
print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]  # N日間の夏休み

dp = [[0]*3 for _ in range(N)]  # i日目の状態, (幸福度の合計, 前日の遊んだ内容3種類のテーブル)

# print(S)
# print(dp)

# 初期値
dp[0][0] = (S[0][0], 'a')
dp[0][1] = (S[0][1], 'b')
dp[0][2] = (S[0][2], 'c')

# print(dp)
for i in range(1, N):  # N日間の遷移
    # aの予定を実行する場合
    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')

    # bの予定を実行する場合
    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')

    # cの予定を実行する場合
    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(dp)
print(max(dp[N-1])[0])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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(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
#import unittest
#import collections

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():
	#Read the input N
	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()

Submission status: Accepted

Solution code:
import sys
#import unittest
#import collections

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():
	#Read the input N
	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()

Submission status: Accepted

Solution code:
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:  # i-1番目,i番目で連続して同じ活動は選択できない
                continue
            dp[i+1][k] = max(dp[i+1][k], (dp[i][j] + actives[i][k]))

print(max(dp[N]))

Submission status: Accepted

Solution code:
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])
    # print(dp)
    return max(dp[N])

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

def chmin(a,i,b):
  if a[i] > b:
    a[i] = b
    #print(a)
    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])

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]
# print(happy)
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(happy)
print(max(happy[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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:
                    #print(i,j,int(index))
                    dp[i][index]=max(dp[i-1][j]+l[index],dp[i][index])

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:


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

N = int(input())

# 「翌日の値をセット」しているので、最終日+1日まで入る関係で+1
dp = [ [0 for _ in range(3)] for _ in range(N+1) ]
#print(dp)

ABC = [[]] * N

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

#print(ABC)

# i日目
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])
    '''
    # i日目の選択肢
    for j in range(3):
        # i+1日目の選択肢
        for k in range(3):
            # 翌日が今日と同じならパス
            if j == k:
                continue

            ### 配るdp
            # 翌日の活動kと、今日の幸福度+選択した活動を比較
            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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

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

#dp[iまでの幸福度のmax][最終状態]
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)

Submission status: Accepted

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