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:
## necessary imports
import sys
input = sys.stdin.readline
# from math import *

# swap_array function
def swaparr(arr, a,b):
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp

## gcd function
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a, a)

## nCr function efficient using Binomial Cofficient
def nCr(n, k): 
    if(k > n - k): 
        k = n - k 
    res = 1
    for i in range(k): 
        res = res * (n - i) 
        res = res / (i + 1) 
    return res 

## upper bound function code -- such that e in a[:i] e < x;
def upper_bound(a, x, lo=0):
    hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x:
            lo = mid+1
        else:
            hi = mid
    return lo

## prime factorization
def primefs(n):
    ## if n == 1    ## calculating primes
    primes = {}
    while(n%2 == 0):
        primes[2] = primes.get(2, 0) + 1
        n = n//2
    for i in range(3, int(n**0.5)+2, 2):
        while(n%i == 0):
            primes[i] = primes.get(i, 0) + 1
            n = n//i
    if n > 2:
        primes[n] = primes.get(n, 0) + 1
    ## prime factoriazation of n is stored in dictionary
    ## primes and can be accesed. O(sqrt n)
    return primes

## MODULAR EXPONENTIATION FUNCTION
def power(x, y, p): 
    res = 1
    x = x % p  
    if (x == 0) : 
        return 0
    while (y > 0) : 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
        y = y >> 1      
        x = (x * x) % p 
    return res 

## DISJOINT SET UNINON FUNCTIONS
def swap(a,b):
    temp = a
    a = b
    b = temp
    return a,b

# find function with path compression included (recursive)
# def find(x, link):
#     if link[x] == x:
#         return x
#     link[x] = find(link[x], link);
#     return link[x];

# find function with path compression (ITERATIVE)
def find(x, link):
    p = x;
    while( p != link[p]):
        p = link[p];
    
    while( x != p):
        nex = link[x];
        link[x] = p;
        x = nex;
    return p;


# the union function which makes union(x,y)
# of two nodes x and y
def union(x, y, link, size):
    x = find(x, link)
    y = find(y, link)
    if size[x] < size[y]:
        x,y = swap(x,y)
    if x != y:
        size[x] += size[y]
        link[y] = x

## returns an array of boolean if primes or not USING SIEVE OF ERATOSTHANES
def sieve(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    return prime

#### PRIME FACTORIZATION IN O(log n) using Sieve ####
MAXN = int(1e6 + 5)
def spf_sieve():
    spf[1] = 1;
    for i in range(2, MAXN):
        spf[i] = i;
    for i in range(4, MAXN, 2):
        spf[i] = 2;
    for i in range(3, ceil(MAXN ** 0.5), 2):
        if spf[i] == i:
            for j in range(i*i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i;
    ## function for storing smallest prime factors (spf) in the array

################## un-comment below 2 lines when using factorization #################
# spf = [0 for i in range(MAXN)]
# spf_sieve() 
def factoriazation(x):
    ret = {};
    while x != 1:
        ret[spf[x]] = ret.get(spf[x], 0) + 1;
        x = x//spf[x]
    return ret
    ## this function is useful for multiple queries only, o/w use
    ## primefs function above. complexity O(log n)

## taking integer array input
def int_array():
    return list(map(int, input().strip().split()))
## taking string array input
def str_array():
    return input().strip().split();

#defining a couple constants
MOD = int(1e9)+7;
CMOD = 998244353;
INF = float('inf'); NINF = -float('inf');

################### ---------------- TEMPLATE ENDS HERE ---------------- ###################


## recusive code intended to give TLE;
sys.setrecursionlimit(int(1e8));

n = int(input()); array = [];
for _ in range(n):
    array.append(int_array());

def function(prev, x):
    if x == n-1:
        a = array[x][0] + function(0, x-1);
        b = array[x][1] + function(1, x-1);
        c = array[x][2] + function(2, x-1);
        return max(a, b, c);
    if x == -1:
        return 0;

    if prev == 0:
        a = array[x][1] + function(1, x-1);
        b = array[x][2] + function(2, x-1);
        return max(a, b);
    elif prev == 1:
        a = array[x][0] + function(0, x-1);
        b = array[x][2] + function(2, x-1);
        return max(a, b);
    else:
        a = array[x][0] + function(0, x-1);
        b = array[x][1] + function(1, x-1);
        return max(a, b);

ans = function(-1, n-1);
print(ans);

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import numpy as np


def main():
    n = int(input())
    abc = [list(map(int, input().split() )) for _ in range(n)]
    abc = np.array(abc, dtype='int')

    dp = np.empty((n, 3), dtype='int')
    dp[0, :] = abc[0, :]

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
abc = [list(map(int,input().split())) for _ in range(N)]
dp = np.array([[0]*3]*N)
dp[0][0],dp[0][1],dp[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[i][k] = max(dp[i][k], dp[i-1][j] + abc[i][k])

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
abc = [list(map(int,input().split())) for _ in range(N)]
dp = np.array([[0]*3]*N)
dp[0][0],dp[0][1],dp[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[i][k] = max(dp[i][k], dp[i-1][j] + abc[i][k])

ans = 0

for l in range(N):
  ans = max(ans, max(dp[l]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N = I()
	a = np.zeros((N,))
	b = np.zeros((N,))
	c = np.zeros((N,))
	for i in range(N):
		a[i], b[i], c[i] = LI()
	
	dp = np.zeros((N, 3), dtype=int)
	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, :]))

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N = I()
	a = np.zeros((N,))
	b = np.zeros((N,))
	c = np.zeros((N,))
	for i in range(N):
		a[i], b[i], c[i] = LI()
	
	dp = np.zeros((N, 3), dtype=int)
	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(np.max(dp[-1, :]))

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N = I()
	a = np.zeros((N,))
	b = np.zeros((N,))
	c = np.zeros((N,))
	for i in range(N):
		a[i], b[i], c[i] = LI()
	
	dp = np.zeros((N, 3), dtype=int)
	for i in range(N):
		if i == 0:
			dp[i, 0] = a[i]
			dp[i, 1] = b[i]
			dp[i, 2] = c[i]
		else:
			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(np.max(dp[-1, :]))

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
#最初に置いておくもの
import sys
sys.setrecursionlimit(500000) 
input=sys.stdin.readline

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

inf=float('inf')
dp=[[0]*3 for j in range(N+1)]

def chmax(a,b):
    return max(a,b)

def rec(n,m):
    if n==0:
        return 0
    if dp[n][m]>0:
        return dp[n][m]

    for i in range(3):
            if (i == m):
                continue
            dp[n][m]=chmax(dp[n][m], rec(n-1,i) + A[n-1][m])
    
    return dp[n][m]

re=max(rec(N,0),rec(N,1),rec(N,2))
print(re)

Submission status: Time Limit Exceeded

Solution code:
#最初に置いておくもの
import sys
sys.setrecursionlimit(500000) 
input=sys.stdin.readline

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

inf=float('inf')
dp=[[-inf]*3 for j in range(N+1)]
dp[0][0]=0
dp[0][1]=0
dp[0][2]=0

def chmax(a,b):
    return max(a,b)

def rec(n,m):
    if n==0:
        return 0
    for i in range(3):
        if (m == i):
            continue
        dp[n][m]=chmax(dp[n][m], rec(n-1,i) + A[n-1][m])
    
    return dp[n][m]

re=max(rec(N,0),rec(N,1),rec(N,2))
print(re)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(200000)

n = int(input())
 
def dp(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
	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: Time Limit Exceeded

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

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

dp = [[0] * N 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: Time Limit Exceeded

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

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

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

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

print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    N = int(input())
    A, B, C = np.full((3,N),0)

    for i in range(N):
        A[i], B[i], C[i] = [int(x) for x in input().split()]

    DP = np.full((N,3),0,dtype=int)

    act = [A,B,C]

    for i, X in enumerate(act):
        DP[0][i] = X[0]
    
    for i in range(N-1):
        for x, X in enumerate(act):
            for y, Y in enumerate(act):
                if x != y:
                    DP[i+1][y] = max(DP[i+1][y],DP[i][x]+Y[i+1])

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

if __name__ == "__main__":
    main()
    pass

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())  #nは入力回数
num_list = [list(map(int, input().split())) for _ in range(n)]
dp_ini=0
dp=np.zeros((n+1,3))
for i in range(0,n):
  for j in range(3):
    for k in range(3):
      if(j==k):
        continue
      else:
        dp[i+1][k]=max(dp[i+1][k],dp[i][j]+num_list[i][k])
print(int(max(dp[n][0],dp[n][1],dp[n][2])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
dp = np.zeros((n + 1, 3), dtype=int)
for i in range(n):
    abc = list(map(int, input().split()))
    for j in range(3):
        for k in range(1, 3):
            k = (j + k) % 3
            dp[i + 1, j] = max(dp[i + 1, j], dp[i, k] + abc[k])
print(dp[-1].max())

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
N = int(input())
import numpy as np
koufuku = np.array( [list(map(int, input().split())) for i in range(N)] ,dtype=int)
dp_ko = [0]*(N+1) 

dp_ko[0] = max( koufuku[0,:] ) , np.argmax(koufuku[0,:]) 

#
for i in range(N-1):
    
    tomorr_i = np.argmax(koufuku[i+1,:]) # 翌日の最大値のindex
    tomorr_ko = np.max(koufuku[i+1,:] ) # 翌日の最大値
    if tomorr_i != dp_ko[i][1]: # 翌日最大値のindex not 当日の保存していたindex(当日の最大値とは限らない)
        dp_ko[i+1] = dp_ko[i][0] + tomorr_ko , tomorr_i # 累積＋翌日の最大値 , 翌日のindex
    else:
        tomorr_no2 = np.sort( koufuku[i+1,:] )[-2] # 翌日2番目に大きい値
        tomorr_no2_i = koufuku[i+1,:].argsort()[-2] # 翌日2番目に大きい値のindex
        dp_ko[i+1] = dp_ko[i][0] + tomorr_no2 , tomorr_no2_i 

print(dp_ko[N-1][0])

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
N = int(input())
import numpy as np
koufuku = np.array( [list(map(int, input().split())) for i in range(N)] ,dtype=int)
dp_ko_np = np.zeros((N,2),dtype=int) 
dp_ko_np[0,0] = max( koufuku[0,:] )
dp_ko_np[0,1] = np.argmax(koufuku[0,:]) 

#
for i in range(N-1):
    # 翌日最大値のindex not 当日の保存していたindex(前日があるので、当日の最大値とは限らない)
    tomorr_i = np.argmax(koufuku[i+1,:]) # 翌日の最大値のindex
    if tomorr_i != dp_ko_np[i,1]: 
        dp_ko_np[i+1,0] = dp_ko_np[i][0] + np.max(koufuku[i+1,:] ) # 累積＋翌日の最大値
        dp_ko_np[i+1,1] = np.argmax(koufuku[i+1,:]) # 翌日のindex
    else:
        dp_ko_np[i+1,0] = dp_ko_np[i][0] + np.sort( koufuku[i+1,:] )[-2] # 累積＋2番目に大きい値
        dp_ko_np[i+1,1] = koufuku[i+1,:].argsort()[-2] # 2番目に大きい値のindex

print(dp_ko_np[N-1,0])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
 
N = int(input())
H = list(list(map(int,input().split())) for _ in range(N))
#sub problem: max cost from 0 to ith day
memo = {}
def rec(i, choice):
  if (i, choice) in memo:
    return memo[(i, choice)]
  if i == len(H):
    return 0
  m = max(H[i][j] + rec(i+1,j) for j in range(3) if j != choice)
  memo[(i, choice)] = m
  return m
print(max(rec(0, j) for j in range(3)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
 
N = int(input())
H = list(list(map(int,input().split())) for _ in range(N))
#sub problem: max cost from 0 to ith day
def rec(i, choice):
  if i == len(H):
    return 0
  return max(H[i][j] + rec(i+1,j) for j in range(3) if j != choice)
print(max(rec(0, j) for j in range(3)))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
l1=[[] for i in range(N)]
for i in range(N):
    l=list(map(int,input().split()))
    for j in range(len(l)):
        l1[i].append(l[j])
pos=-1
f=-1
suma=0
for i in range(N):
    f=i
    if l1[i][0]>=l1[i][1] and l1[i][0]>=l1[i][2]:
        s=l1[i][0]
       # print(s)
        pos=0
    elif l1[i][1]>=l1[i][0] and l1[i][1]>=l1[i][2]:
        s=l1[i][1]
       # print(s)
        pos=1
    else:
        s=l1[i][2]
       # print(s)
        pos=2
    m=pos
    for j in range(i-1,-1,-1):
        if m==0:
            if l1[j][1]>=l1[j][2]:
                s=s+l1[j][1]
                #print(l1[j][1])
                m=1
            else:
                s=s+l1[j][2]
                #print(l1[j][2])
                m=2
        elif m==1:
            if l1[j][0]>=l1[j][2]:
                s=s+l1[j][0]
                #print(l1[j][0])
                m=0
            else:
                s=s+l1[j][2]
                #print(l1[j][2])
                m=2
        else:
            if l1[j][0]>=l1[j][1]:
                s=s+l1[j][0]
                #print(l1[j][0])
                m=0
            else:
                s=s+l1[j][1]
                #print(l1[j][1])
                m=1
    if suma<s:
        suma=s
    for j in range(i+1,N):
        if pos==0:
            if l1[j][1]>=l1[j][2]:
                s=s+l1[j][1]
                #print(l1[j][1])
                pos=1
            else:
                s=s+l1[j][2]
                #print(l1[j][2])
                pos=2
        elif pos==1:
            if l1[j][0]>=l1[j][2]:
                s=s+l1[j][0]
                #print(l1[j][0])
                pos=0
            else:
                s=s+l1[j][2]
                #print(l1[j][2])
                pos=2
        else:
            if l1[j][0]>=l1[j][1]:
                s=s+l1[j][0]
                #print(l1[j][0])
                pos=0
            else:
                s=s+l1[j][1]
                #print(l1[j][1])
                pos=1
    #print(s)
    if suma<s:
        suma=s
print(suma)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inp_list(): return list(map(int, sys.stdin.readline().split()))


def lcm(x, y): return (x * y) // gcd(x, y)


N = inp()
a = np.zeros((N, 3), dtype=int)

for i in range(N):
    a[i] = inp_list()

# dp[i + 1][j]: i日目までの活動で、i日目に活動 j (0: A, 1: B, 2:C) を選んだときの i + 1 日目の幸福の最大値
dp = np.zeros((N + 1, 3), dtype=int)
for i in range(N):
    for j in range(3): # i 日目の活動
        for k in range(3): # i + 1 日目の活動
            if j == k: continue
            dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + a[i][k])

ans = 0
for i in range(3):
    ans = max(ans, dp[N][i]) # N 日目を終了したときの幸福度 => dp[N][] (N + 1 番目)

# print(a)
# print(dp)
print(ans)

Submission status: Time Limit Exceeded

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

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


def recur(i, last_index, v):
    if i == n:
        return v
    res = -1
    for j in range(3):
        if j == last_index:
            continue
        res = max(res, recur(i + 1, j, v + abc[i][j]))
    return res


print(recur(0, -1, 0))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
#dp[i]...i日間で得られる幸福度の最大値
INF = 10**18
dp =[]
for _ in range(N):
    dp.append([INF] * (N+1))
dp[0] = list(map(int,input().split()))
#print(dp)
for i in range(1, N):
    #変えたいのはdp[1][0〜2]
    day = list(map(int,input().split()))
    d_temp = [dp[i-1][k]+day[j] for j in range(3) for k in range(3) if k!=j]
    #print(d_temp)
    dp[i]=[max(d_temp[2*x:2*x+2]) for x in range(3)]
print(max(dp[N-1]))

Submission status: Time Limit Exceeded

Solution code:
import copy

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

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

for i, l in enumerate(abc):
    if i == 0:
        dp[i] = copy.deepcopy(l)
    else:
        mx = 0
        ex = [0, 1, 2]
        ext = copy.deepcopy(ex)
        for j, m in enumerate(l):
            ext.remove(j)
            mx1 = max(mx, abc[i][ext[0]] + dp[i - 1][j])
            mx2 = max(mx, abc[i][ext[1]] + dp[i - 1][j])
            mx = max(mx1, mx2)
            ext = copy.deepcopy(ex)
            dp[i][j] = mx

print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
ABC=[]
for i in range(N):
  l=list(map(int,input().split()))
  ABC=ABC+[l]
dp=[[0,0,0] for i in range(N)]#dp[i][j]はi+1日目にアクティビティjを選んだ時の活動終了時の幸福量
for i in range(3):
  dp[0][i]=ABC[0][i]
for i in range(1,N):
  dp[i][1]=max(dp[i-1][2]+ABC[i][1],dp[i-1][0]+ABC[i][1])
  dp[i][0]=max(dp[i-1][1]+ABC[i][0],dp[i-1][2]+ABC[i][0])
  dp[i][2]=max(dp[i-1][1]+ABC[i][2],dp[i-1][0]+ABC[i][2])
ans=max(dp[N-1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 6)

N = int(input())

plans = []

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

  
@lru_cache(maxsize=None)
def max_utility_at(day, i):
  candidates = [
    (1, 2),
    (0, 2),
    (0, 1)
  ]
  if day == 0:
    return plans[0][i]
  else:    
    return max(max_utility_at(day - 1, x) + plans[day][i] for x in candidates[i])

  
print(max(max_utility_at(N - 1, x) for x in (0, 1, 2)))

Submission status: Time Limit Exceeded

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

ex = np.array([[1,2], [0,2], [0,1]])
dp = np.array([abc[0]] + [[0]*3 for _ in range(n-1)])

for i in range(n-1):
    for j in range(3):
        dp[i+1][j] = abc[i+1][j] + np.max(np.take(dp[i], ex[j]))

print(max(dp[-1]))

Submission status: Time Limit Exceeded

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

ex = [[1,2], [0,2], [0,1]]
dp = np.array([abc[0]] + [[0]*3 for _ in range(n-1)])

for i in range(n-1):
    for j in range(3):
        dp[i+1][j] = abc[i+1][j] + np.max(np.take(dp[i], ex[j]))

print(max(dp[-1]))

Submission status: Time Limit Exceeded

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

ex = [[1,2], [0,2], [0,1]]
dp = np.array([abc[0]] + [[0]*3 for _ in range(n-1)])

for i in range(n-1):
    for j in range(3):
        dp[i+1][j] = abc[i+1][j] + max(np.take(dp[i], ex[j]))

print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
abc_list = [[int(i) for i in input().split()] for j in range(n)]
abc_list = np.array(abc_list)

dp = np.zeros((n, 3))
dp[0,:] = abc_list[0,:]

temp_indexes = np.array([0, 1, 2])
for i in range(1, n):
    for j in range(3):
        indexes = temp_indexes[temp_indexes!=j]
        bigger = max(dp[i-1][indexes[0]], dp[i-1][indexes[1]])
        dp[i][j] = bigger + abc_list[i][j]
        
print(int(np.max(dp[-1,:])))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

def main():
    N = int(input())
    act = np.array([[int(item) for item in input().split()] for _ in range(N)])

    dp = np.zeros((2, 3), dtype='int64')
    selector = np.array([[0,1,1], [1,0,1], [1,1,0]])

    for i in range(0,N):
        for k in range(3):
            act_array = act[i][k]
            dp[i%2^1][k] = np.max(dp[i%2]*selector[k]) + act_array

        # print(dp)

    print(max(dp[N%2]))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

def main():
    N = int(input())
    act = np.array([[int(item) for item in input().split()] for _ in range(N)])

    dp = np.zeros((2, 3), dtype='int64')

    for i in range(0,N):
        for j in range(3):
            prev_dp_array = [dp[i%2][k] if k != j else 0 for k in range(3)]
            dp[i%2 ^ 1][j] = np.max(prev_dp_array + act[i][j])
        # print(dp)
    print(np.max(dp))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

N = int(input())
act = np.array([[int(item) for item in input().split()] for _ in range(N)])

dp = np.zeros((2, 3), dtype='int64')

for i in range(0,N):
    for j in range(3):
        prev_dp_array = [dp[i%2][k] if k != j else 0 for k in range(3)]
        dp[i%2 ^ 1][j] = max(prev_dp_array + act[i][j])
    # print(dp)
print(np.max(dp))

Submission status: Time Limit Exceeded

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

import numpy as np
dp=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:

                dp[i][j] = max(dp[i-1][k] + S[i-1][j],dp[i][j])
                #happy =  dp[i-1][k] + S[i-1][j]
                #if dp[i][j] < happy:
                #    dp[i][j] = happy

print(int(max(dp[N])))

Submission status: Time Limit Exceeded

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

import numpy as np
dp=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 =  dp[i-1][k] + S[i-1][j]
                if dp[i][j] < happy:
                    dp[i][j] = happy

print(int(max(dp[N])))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys 
sys.setrecursionlimit(2147483647)

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

#@lru_cache(None)
def dfs(d,pre):
    if (d,pre) in dic: return dic[(d,pre)]
    if d < 0:
        dic[(d,pre)] = 0 
        return 0
    ma = 0 
    for idx,a in enumerate(A[d]):
        if idx != pre:
            res = dfs(d - 1,idx) + a 
            ma = max(res,ma)
    dic[(d,pre)] = ma
    return dic[(d,pre)]
dic = {}
res = dfs(N-1,-1)
print(res)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys 
sys.setrecursionlimit(2147483647)

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


@lru_cache(None)
def dfs(d,pre):
    if d>=N-1: return 0
    ma = 0 
    for idx,a in enumerate(A[d]):
        if idx != pre:
            res = dfs(d + 1,idx) + a 
            ma = max(res,ma)
    return ma
res = dfs(-1,-1)
print(res)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys 
sys.setrecursionlimit(2147483647)

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

@lru_cache(None)
def dfs(d,pre):
    if d>=N-1: return 0
    ans = 0
    for idx,a in enumerate(A[d]):
        if idx != pre:
            res = dfs(d + 1,idx) + a 
            ans = max(res,ans)
    return ans

print(dfs(-1,-1))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys 
sys.setrecursionlimit(2147483647)

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

@lru_cache(None)
def dfs(d,pre):
    if d>=N-1: return 0
    tmp = [0] 
    for idx,a in enumerate(A[d]):
        if idx != pre:
            res = dfs(d + 1,idx) + a 
            tmp.append(res)
    return max(tmp)

print(dfs(-1,-1))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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


@lru_cache(None)
def dfs(d,h,pre):
    if d == N - 1:
        return h
    tmp = [0] 
    for idx,a in enumerate(A[d]):
        if idx != pre:
            res = dfs(d + 1,h + a,idx)
            tmp.append(res)
    return max(tmp)

import sys
sys.setrecursionlimit(2147483647)

print(dfs(-1,0,-1))

Submission status: Time Limit Exceeded

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

def max_happiness(n, data, a, b, c):
  if n == 0:
    if a and b:
      return max(data[n][0], data[n][1])
    elif b and c:
      return max(data[n][1], data[n][2])
    elif c and a:
      return max(data[n][2], data[n][0])
  
  max_a = -1
  max_b = -1
  max_c = -1
  
  if a:
    max_a = data[n][0] + max_happiness(n-1, data, a=False, b=True, c=True)
  if b:
    max_b = data[n][1] + max_happiness(n-1, data, a=True, b=False, c=True)
  if c:
    max_c = data[n][2] + max_happiness(n-1, data, a=True, b=True, c=False)
    
  return max(max_a, max_b, max_c)

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

print(max_happiness(N-1, data, a=True, b=True, c=True))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
n = int(input())

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

dp[0][0], dp[0][1], dp[0][2] = map(int, input().split())
if n == 1:
    print(int(np.max(dp[0])))
    sys.exit()
    
for _ in range(n-1):
    h = list(map(int, input().split()))
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[1][k] = max(dp[0][j] + h[k], dp[1][k])
    dp[0] = dp[1]
print(int(np.max(dp[1])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
dp = np.zeros((N+1, 3), dtype=int)
for i in range(1, N+1):
    lst = np.array(list(map(int, input().split(' '))))
    dp[i][0] = np.max(dp[i-1][[1,2]] + lst[[1,2]])
    dp[i][1] = np.max(dp[i-1][[0,2]] + lst[[0,2]])
    dp[i][2] = np.max(dp[i-1][[0,1]] + lst[[0,1]])
print(np.max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
dp = np.zeros((N+1, 3), dtype=int)
for i in range(1, N+1):
    lst = np.array(list(map(int, input().split(' '))))
    dp[i][0] = max(dp[i-1][[1,2]] + lst[[1,2]])
    dp[i][1] = max(dp[i-1][[0,2]] + lst[[0,2]])
    dp[i][2] = max(dp[i-1][[0,1]] + lst[[0,1]])

print(max(dp[-1]))

Submission status: Time Limit Exceeded

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

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

dp = [[-1] * 4 for i in range(N + 1)]


def happy(n, p):
    if n < 0:
        return 0
    if dp[n][p] >= 0:
        return dp[n][p]

    a = 0 if p == 0 else happy(n - 1, 0) + abc[n][0]
    b = 0 if p == 1 else happy(n - 1, 1) + abc[n][1]
    c = 0 if p == 2 else happy(n - 1, 2) + abc[n][2]
    dp[n][p] = max([a, b, c])

    return dp[n][p]


print(happy(N - 1, 3))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
import time

def main():
    N = int(input())
    dp = np.array([[0]*3] * N)
    
    for i in range(N):
        w_all = list(map(int, input().split()))
        for j,  w in enumerate(w_all):
            if(i == 0):
                dp[i][j] = w
            else:
                tmp = dp[i-1]
                ind = np.ones(len(w_all), dtype=bool)
                ind[j] = False
                tmp = tmp[ind]
                dp[i][j] = max(tmp) + w
    print(int(max(dp[N-1])))

if __name__ == "__main__":
    main()