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: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 6)

def f(cur_day=0, cur_sum=0, prev_activity=None):
    if cur_day == n-1:
        return cur_sum + max([data[n-1][k] if k!=prev_activity else -1 for k in range(3)])
    tmp = max([f(cur_day + 1, cur_sum=cur_sum + data[cur_day][k], prev_activity=k)
               if k!=prev_activity else -1 for k in range(3)])

    return tmp

if __name__ == "__main__":
    n = int(input())
    data = []
    for j in range(n):
        data.append(list(map(int, input().split(" "))))
    data = np.array(data)
    points = f()
    print(points)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

def f(cur_day=0, cur_sum=0, prev_activity=None):
    if cur_day == n-1:
        return cur_sum + max([data[n-1][k] if k!=prev_activity else -1 for k in range(3)])
    tmp = max([f(cur_day + 1, cur_sum=cur_sum + data[cur_day][k], prev_activity=k)
               if k!=prev_activity else -1 for k in range(3)])

    return tmp

if __name__ == "__main__":
    n = int(input())
    data = []
    for j in range(n):
        data.append(list(map(int, input().split(" "))))
    points = f()
    print(points)

Submission status: Time Limit Exceeded

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

if days == 1:
  print(max(util[0]))
else:
  dp = [2**util[0][0], 2**util[0][1], 2**util[0][2]]
  for i in range(1, days):
    temp = [1]*3
    temp[0] = (dp[1]<<util[i][0])|(dp[2]<<util[i][0])
    temp[1] = (dp[0]<<util[i][1])|(dp[2]<<util[i][1])
    temp[2] = (dp[0]<<util[i][2])|(dp[1]<<util[i][2])
    dp = temp

  print(max(list(map(lambda x:len(format(x, "b")), dp)))-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1114112)

n = int(input())
a,b,c = [],[],[]
for i in range(n):
    line = input()
    line = line.strip("\n").split(" ")
    a.append(int(line[0]))
    b.append(int(line[1]))
    c.append(int(line[2]))

def helper(i, prev=None, memo={}):
    if (i,prev) in memo: return memo[(i,prev)]

    if i >= n: return 0

    happ1 = 0 if prev == 'a' else a[i] + helper(i+1, 'a', memo)
    happ2 = 0 if prev == 'b' else b[i] + helper(i+1, 'b', memo)
    happ3 = 0 if prev == 'c' else c[i] + helper(i+1, 'c', memo)

    memo[(i,prev)] = max(happ1, happ2, happ3)
    return memo[(i, prev)]

print(helper(0))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
ans = 0
field = [list(map(int,input().split())) for _ in range(n)]
dp = np.zeros((n + 1,3),np.int64)
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] + field[i][k])
for d in dp[-1]:
  ans = max(ans,d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
ary = [list(map(int,input().split())) for _ in range(n)]
ary = np.array(ary,dtype=int)
dp = np.zeros((n,3),dtype=int)
dp[0] = ary[0]
for i in range(1,n):
    for j in range(3):
        for k in range(3):
            if j == k:continue
            if dp[i][j] < dp[i-1][k]+ary[i][j]:
                dp[i][j] = dp[i-1][k] + ary[i][j]
print(max(dp[n-1]))

Submission status: Time Limit Exceeded

Solution code:

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

@lru_cache(None)
def cal(i,action):
    if i>=len(arr):
        return 0

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

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

print(max(cal(0,0),cal(0,1),cal(0,2)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
ary = [list(map(int,input().split())) for _ in range(n)]
ary = np.array(ary)
dp = np.zeros((n,3))
dp[0] = ary[0]
for i in range(n-1):
    for j in range(3):
        for k in range(3):
            if k == j:continue
            dp[i+1][k] = max(dp[i+1][k],dp[i][j] + ary[i+1][k])
print(int(max(dp[n-1])))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
days = int(input())

activity_scores = []
for _ in range(days):
    activity_scores.append(tuple(map(int, input().split())))


dp = {}
def get_max_happiness(previous, scores):
    if len(scores) == 0:
        return 0
    options = []
    head = scores[0]
    tail = scores[1:]
    for i in range(3):
        if i == previous:
            continue
        combination = (i, tail)
        if combination not in dp:
            dp[combination] = get_max_happiness(i, tail)
        options.append(head[i] + dp[combination])
    return max(options)


print(get_max_happiness(-1, tuple(activity_scores)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
dp = np.zeros((N+1,3))
for i in range(N):
    happiness = list(map(int,input().split()))
    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] + happiness[k])
print(int(max(dp[N])))

Submission status: Time Limit Exceeded

Solution code:
import os, sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")
 
sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10**18
MOD = 10**9 + 7

def n(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))
def bulk_li(): return list(map(lambda s: list(map(int, s.split())), sys.stdin.readlines()))

N = n()
abc = bulk_li()  # [[a_i, b_i, c_i]...]

# print(abc)

T = [
    [1, 2],
    [0, 2],
    [0, 1]
]

def solve(abc):
    dp = np.zeros((N, 3), dtype='int32')  # [[Ai, Bi, Ci]...]

    for j in range(3):
        dp[0][j] = abc[0][j]
    if N == 1:
        return dp

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

    # print(dp)
    return dp

print(max(solve(abc)[N-1]))


"""
ちゃんと解いたVer
"""

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())

A = np.zeros([N, 3], dtype='int32')

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

dp = np.zeros([N+1, 3], dtype='int32')

for i in range(N):
    for j in range(3):     # i   日目の選択
        for k in range(3): # i+1 日目の選択
            if j == k:
                continue
            if dp[i+1][k] < dp[i][j] + A[i][k]:
                dp[i+1][k] = dp[i][j] + A[i][k]

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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(10**8)

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

# l = [[None for _ in range(3)] for _ in range(N+10)]
@lru_cache(maxsize=(N+10)*3)
def dp(i, use):
    if i == -1:
        return 0
    # if l[i][use] != None:
    #     return l[i][use]
    max_num = 0
    for k in range(3):
        if k == use:
            continue
        max_num = max(max_num, dp(i-1, k)+ABC[i][use])
    # l[i][use] = max_num 
    return max_num

print(max(dp(N-1, m) for m in range(3)))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(10**8)

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

# l = [[0 for _ in range(3)] for _ in range(N+10)]
@lru_cache(maxsize=None)
def dp(i, use):
    if i == -1:
        return 0
    max_num = 0
    for k in range(3):
        if k == use:
            continue
        max_num = max(max_num, dp(i-1, k)+ABC[i][use])
    return max_num

print(max(dp(N-1, m) for m in range(3)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())

data = np.zeros((n, 3), dtype=np.int64)

for i in range(n):

  data[i] = list(map(int, input().split()))

dp = np.zeros((n+1, 3), dtype=np.int64)

for i in range(n):
  for j in range(3):
    for k in range(3):
      if j != k:
        dp[i+1][j] = np.maximum(dp[i][k] + data[i][j], dp[i+1][j])

print(np.max(dp[n]))

Submission status: Time Limit Exceeded

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

import numpy as np

N = int(input())

dp = np.zeros((N+1, 3), dtype=int)
arr = np.zeros((N, 3), dtype=int)
for i in range(N):
  arr[i] = list(map(int, input().split()))

# dp roop
for i in range(N):
  for j in range(3):
    for k in range(3):
      if j==k:
        continue
      dp[i+1, k] = np.maximum(dp[i+1, k], dp[i, j] + arr[i, k])
print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def check_value(before_key, values):
    if before_key == 0:
        k, v = np.argmax(values[1:])+1, np.max(values[1:])
    elif before_key == 1:
        k, v = np.argmax(values[::2])*2, np.max(values[::2])
    else:
        k, v = np.argmax(values[:-1]), np.max(values[:-1])
    return k, v


if __name__ == '__main__':
    n = int(input())
    happy_list = []
    for _ in range(n):
        happy_list.append(list(map(int, input().split())))
    a_key, b_key, c_key = 0, 1, 2
    a_sum, b_sum, c_sum = happy_list[0][0], happy_list[0][1], happy_list[0][2]
    for happy in happy_list[1:]:
        key, value = check_value(a_key, happy)
        a_key = key
        a_sum += value
        key, value = check_value(b_key, happy)
        b_key = key
        b_sum += value
        key, value = check_value(c_key, happy)
        c_key = key
        c_sum += value
    print(max(a_sum, b_sum, c_sum))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
dp = np.array([ [0] * (N+1), [0] * (N+1), [0] * (N+1) ])

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

print(dp[:, N].max())

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10**8)


def dp_solve(i, k, dp):
    if k == 0:
        if i == 0:
            return max(bx[i], cx[i])
        dp[i] = max(dp_solve(i-1, 1, dp)+ax[i], dp_solve(i-1, 2, dp)+ax[i])
    if k == 1:
        if i == 0:
            return max(ax[i], cx[i])
        dp[i] = max(dp_solve(i-1, 0, dp)+bx[i], dp_solve(i-1, 2, dp)+bx[i])
    if k == 2:
        if i == 0:
            return max(ax[i], bx[i])
        dp[i] = max(dp_solve(i-1, 0, dp)+cx[i], dp_solve(i-1, 1, dp)+cx[i])
    return dp[i]


if __name__ == "__main__":
    n = int(input())
    ax = []
    bx = []
    cx = []
    for i in range(n):
        a, b, c = map(int, input().split())
        ax.append(a)
        bx.append(b)
        cx.append(c)

    dp = [0]*n
    dp1 = dp_solve(n-1, 0, dp)
    dp = [0]*n
    dp2 = dp_solve(n-1, 1, dp)
    dp = [0]*n
    dp3 = dp_solve(n-1, 2, dp)
    print(max(dp1, dp2, dp3))

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret

# 全探索だと
# 3^N通りになってTLEだこれ

# 制限がなければ、iごとにmaxを取っておわりO(N)

# iの時の最善の状態が[i,j](jは行動)のとき、i+1最善の状態は[i+1,k](k!=j)となる
# これはDPで実装できそう！


import numpy as np

N = read_a_int()
ABC = np.array(read_matrix(N))
# A, B, C = read_col(N, 3)

dp = np.full((N, 3), 0, dtype='int16')
# 0->a,1->b,2->c

dp[0, :] = ABC[0]

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

# print(dp)
print(dp[-1].max())

# TLEしたのでpypy3仕様にかきなおし

# ABC = read_matrix(N)

# # dp = np.full((N, 3), -float('inf'))
# dp = [[-float('inf') for _ in range(3)] for _ in range(N)]
# # 0->a,1->b,2->c

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

# for i in range(N - 1):

#     for j in range(3):
#         iterlist = [0, 1, 2]
#         iterlist.remove(j)
#         dp[i+1][j] = max([dp[i][k] + ABC[i+1][j] for k in iterlist])

# # print(dp)
# print(int(max(dp[-1])))

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret

# 全探索だと
# 3^N通りになってTLEだこれ

# 制限がなければ、iごとにmaxを取っておわりO(N)

# iの時の最善の状態が[i,j](jは行動)のとき、i+1最善の状態は[i+1,k](k!=j)となる
# これはDPで実装できそう！


import numpy as np

N = read_a_int()
ABC = np.array(read_matrix(N))
# A, B, C = read_col(N, 3)

dp = np.full((N, 3), 0, dtype='int32')
# 0->a,1->b,2->c

dp[0, :] = ABC[0]

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

    # dp[i + 1, 0] = dp[i, 1:].max()+ABC[i+1, 0]
    # dp[i + 1, 1] = dp[i, (0, 2)].max() + ABC[i+1, 1]
    # dp[i + 1, 2] = dp[i, :2].max()+ABC[i+1, 2]

# print(dp)
print(dp[-1].max())

# TLEしたのでpypy3仕様にかきなおし

# ABC = read_matrix(N)

# # dp = np.full((N, 3), -float('inf'))
# dp = [[-float('inf') for _ in range(3)] for _ in range(N)]
# # 0->a,1->b,2->c

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

# for i in range(N - 1):

#     for j in range(3):
#         iterlist = [0, 1, 2]
#         iterlist.remove(j)
#         dp[i+1][j] = max([dp[i][k] + ABC[i+1][j] for k in iterlist])

# # print(dp)
# print(int(max(dp[-1])))

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret

# 全探索だと
# 3^N通りになってTLEだこれ

# 制限がなければ、iごとにmaxを取っておわりO(N)

# iの時の最善の状態が[i,j](jは行動)のとき、i+1最善の状態は[i+1,k](k!=j)となる
# これはDPで実装できそう！


import numpy as np

N = read_a_int()
ABC = np.array(read_matrix(N))
# A, B, C = read_col(N, 3)

dp = np.full((N, 3), -float('inf'))
# 0->a,1->b,2->c

dp[0, :] = ABC[0]

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

# print(dp)
print(int(dp[N-1].max()))

Submission status: Time Limit Exceeded

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret

# 全探索だと
# 3^N通りになってTLEだこれ

# 制限がなければ、iごとにmaxを取っておわりO(N)

# iの時の最善の状態が[i,j](jは行動)のとき、i+1最善の状態は[i+1,k](k!=j)となる
# これはDPで実装できそう！


import numpy as np

N = read_a_int()
ABC = np.array(read_matrix(N))
# A, B, C = read_col(N, 3)

dp = np.full((N, 3), -float('inf'))
# 0->a,1->b,2->c

dp[0, :] = ABC[0]

for i in range(N - 1):  # 範囲は怪しい後で考える
    # 幸福度足してないじゃん！
    dp[i + 1, 0] = (dp[i, 1:]+ABC[i+1, 0]).max()
    dp[i + 1, 1] = (dp[i, (0, 2)] + ABC[i+1, 1]).max()
    dp[i + 1, 2] = (dp[i, :2]+ABC[i+1, 2]).max()

# print(dp)
print(int(dp[N-1].max()))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
action=np.array([list(map(int,input().split())) for _ in range(n)])
# happy[i][j] i日目にaction j を選んだ場合の幸福度の最大値
happy=np.zeros((n+1,3))
for i in range(1,n+1):
    for j in range(3):
        for k in range(3):
            if j!=k:
                happy[i][j]=max(happy[i][j],happy[i-1][k]+action[i-1][j])
        # happy[i][j]=max(np.concatenate((happy[i-1][0:j]+action[i-1][j],happy[i-1][j+1:3]+action[i-1][j]),axis=None))
# print(happy)
print(int(max(happy[n])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
action=np.array([list(map(int,input().split())) for _ in range(n)])
# happy[i][j] i日目にaction j を選んだ場合の幸福度の最大値
happy=np.zeros((n+1,3))
for i in range(1,n+1):
    for j in range(3):
        happy[i][j]=max(np.concatenate((happy[i-1][0:j]+action[i-1][j],happy[i-1][j+1:3]+action[i-1][j]),axis=None))
# print(happy)
print(int(max(happy[n])))

Submission status: Time Limit Exceeded

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

s = 0
def calc(rs,si,srs):
    l = rs[0]
    srs += l[si]
    if (len(rs)==1):
        return srs
    else:
        if si == 0:
            return max(calc(rs[1:],1,srs), calc(rs[1:],2,srs))
        elif si == 1:
            return max(calc(rs[1:],0,srs), calc(rs[1:],2,srs))
        elif si == 2:
            return max(calc(rs[1:],0,srs), calc(rs[1:],1,srs))

print(max(calc(al,0,0),calc(al,1,0),calc(al,2,0)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())

happiness = np.zeros(3)

for i in range(n):
    act = np.array(list(map(int, input().split())))
    happiness = np.maximum(act+np.roll(happiness, 1), act+np.roll(happiness, 2))

print(int(happiness.max()))

Submission status: Time Limit Exceeded

Solution code:
def fastio():
    import sys
    from io import StringIO 
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))

n, = I()
l = []
for i in range(n):
    l.append(I())
ans = [0]*(n+1)
ans[0] = max(l[0])
m = -MOD
index = l[0].index(max(l[0]))
mindex = 0
if n > 1:
    for i in range(3):
        if l[1][i] + ans[0] > m and i != index:
            m = l[1][i] + ans[0]
            mindex = i
ans[1] = m
index = mindex
for i in range(2, n):
    m = -MOD
    for j in range(3):
        if l[i][j] + ans[i-1] > m and j != index:
            m = l[i][j] + ans[i-1]
            mindex = j
    if l[i][index] + ans[i-2] > m:
        m = l[i][index] + ans[i-2]
        mindex = index
    ans[i] = m
    index = mindex
# print(ans)
print(ans[n-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

fil = [np.array([False, True, True]),
       np.array([True, False, True]),
       np.array([True, True, False])]

def vacation(v):
    dp = np.full_like(v, 0)
    dp[0, :] = v[0, :]
    for i in range(1, v.shape[0]):
        for a in range(3):
            dp[i, a] = max(dp[i-1, fil[a]]) + v[i, a]
    return dp[-1].max()

N = int(input())
v = np.array([list(map(int, input().split())) for _ in range(N)])
print(vacation(v))

Submission status: Memory Limit Exceeded

Solution code:
def maxreturn(t,n,a):
    ma=[0]*3
    b=[0]*n
    if t==n-1:
        for i in range(3):
           ma[i]=a[n-1][i]
    else:
      b=list(maxreturn(t+1,n,a))
      for i in range(3):
        for j in range(3):
            if i!=j:
                ma[i]=max(ma[i],a[t][i]+b[j])
                
    return ma
n=int(input())
a=[[0]*3]*n
for i in range(n):
    a[i]=list(map(int,input().split()))
ma=maxreturn(0,n,a)
print(max(ma))

Submission status: Accepted

Solution code:

n = int(input())

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

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

dp[0] = li[0]

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

  
print(max(dp[-1]))

Submission status: Accepted

Solution code:
N=int(input())

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

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


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
happy=[]
dp=[[0,0,0] for r in range(N)]
for i in range(N):
  happy.append(list(map(int,input().split())))
dp[0]=happy[0].copy()
for i in range(1,N):
  for j in range(3):
    for k in range(3):
      if j != k :
        dp[i][j]=max(dp[i-1][k]+happy[i][j],dp[i][j])
        

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

Submission status: Accepted

Solution code:
N = int(input())
a = []
b = []
c = []
for i in range(N):
    num = list(map(int, input().split(' ')))
    a.append(num[0])
    b.append(num[1])
    c.append(num[2])
dp = [[0,0,0] for i 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])
ans = max(dp[N -1][0], dp[N -1][1], dp[N -1][2])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ls = [[0 for i in range(3)] for i in range(N)]
for i in range(N):
    ls[i] = list(map(int,input().split()))
# dp[i][j] -> i-1日目にjの仕事をしたときの i 日目の幸福度の総和
dp = [ [0 for i in range(3)] for i in range(N)]
for i in range(3):
    dp[0][i] = ls[0][i]
for i in range(1,N):
    for j in range(3):
        w = [0,1,2]
        w.remove(j)
        x,y = w[0],w[1]
        dp[i][j] = max(dp[i-1][x],dp[i-1][y]) + ls[i][j]
            
print(max(dp[N-1]))

Submission status: Accepted

Solution code:
N = int(input())
abc = [list(map(int,input().split())) for c in range(N)]
dp = [[0,0,0] for c in range(N)]
dp[0] = [abc[0][0],abc[0][1],abc[0][2]]
for i in range(1,N):
    for j in range(3):
        # print([dp[i-1][c] + abc[i][j] for c in range(3) if c != j])
        dp[i][j] = max([dp[i-1][c] + abc[i][j] for c in range(3) if c != j])
        # print(dp[i][j])

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

Submission status: Accepted

Solution code:
n = int(input())

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

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

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

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 = [[abc[0][0], abc[0][1], abc[0][2]]] + [[0, 0, 0] for i in range(N - 1)]

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

Submission status: Accepted

Solution code:

n = int(input())
A = list(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] + A[i][k])

print(max(dp[n]))

Submission status: Accepted

Solution code:
n = int(input())

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

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

for i in range(n): # i represents i_th day
    for j in range(3): # j represents j_th activity chosen on the i_th day
        for k in range(3): # k represents k_th activity to be chosen on the day after
            if k != j:
                dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + abc[i][k])
print(max(dp[n]))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    acts = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        acts.append([a,b,c])
    dp = [[0] * 3 for _ in range(N + 5)]

    dp[0][0] = acts[0][0]
    dp[0][1] = acts[0][1]
    dp[0][2] = acts[0][2]
    for i in range(1,N):
        for j in range(3):
            if j == 0:
                score = max(dp[i-1][1], dp[i-1][2])
            if j == 1:
                score = max(dp[i-1][0], dp[i-1][2])
            if j == 2:
                score = max(dp[i-1][1], dp[i-1][0])
            dp[i][j] = acts[i][j] + score

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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
x, y, z = 0, 0, 0

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

Submission status: Accepted

Solution code:
import numpy as np


def main():
    n = int(input())
    d = [list(map(int, input().split())) for i in range(n)]

    dp = np.zeros((n, 3), dtype='int')
    dp[0] = d[0]

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
INF=float('inf')

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

#import
#import math
#import numpy as np
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(N-1):
    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] + abc[i+1][k])



print(max(dp[-1]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

#import
#import math
#import numpy as np
N = int(input())
abc = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(N):
    if i == 0:
        dp[i][0] = abc[i][0]
        dp[i][1] = abc[i][1]
        dp[i][2] = abc[i][2]
        continue

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



print(max(dp[-1]))

Submission status: Accepted

Solution code:
'''
in
-----
7
2
9
4
5
1
6
10
'''
'''
out
-----
8
'''
from collections import defaultdict
dp = defaultdict(lambda:int(0))

N = int(input())
L = [0] * (N +2)
for i in range(0, N):
    L[i] = list(map(int, input().split()))

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

print(max(dp.values()))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
abc = []
for i in range(N):
  abc.append([int(i) for i in input().split()])
abc.append([0,0,0])
dp = np.zeros([N+1,3])
#print(dp)

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

Submission status: Accepted

Solution code:
d={}
for i in range(int(input())):
    d[i]={}
    a,b,c=map(int,input().split())
    if i==0:
        d[i][0]=a
        d[i][1]=b
        d[i][2]=c
    else:
        d[i][0]=max(d[i-1][1],d[i-1][2])+a
        d[i][1]=max(d[i-1][0],d[i-1][2])+b
        d[i][2]=max(d[i-1][1],d[i-1][0])+c
print(max(d[i][0],d[i][1],d[i][2]))