Problem:


Score : 600 points

Problem Statement

The squirrel Chokudai has N acorns.
One day, he decides to do some trades in multiple precious metal exchanges to make more acorns.

His plan is as follows:

Get out of the nest with N acorns in his hands.

Go to Exchange A and do some trades.

Go to Exchange B and do some trades.

Go to Exchange A and do some trades.

Go back to the nest.

In Exchange X (X = A, B), he can perform the following operations any integer number of times (possibly zero) in any order:

Lose g_{X} acorns and gain 1 gram of gold.

Gain g_{X} acorns and lose 1 gram of gold.

Lose s_{X} acorns and gain 1 gram of silver.

Gain s_{X} acorns and lose 1 gram of silver.

Lose b_{X} acorns and gain 1 gram of bronze.

Gain b_{X} acorns and lose 1 gram of bronze.

Naturally, he cannot perform an operation that would leave him with a negative amount of acorns, gold, silver, or bronze.

What is the maximum number of acorns that he can bring to the nest?
Note that gold, silver, or bronze brought to the nest would be worthless because he is just a squirrel.

Constraints

1 \leq N \leq 5000

1 \leq g_{X} \leq 5000

1 \leq s_{X} \leq 5000

1 \leq b_{X} \leq 5000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
g_A s_A b_A
g_B s_B b_B

Output

Print the maximum number of acorns that Chokudai can bring to the nest.

Sample Input 1

23
1 1 1
2 1 1

Sample Output 1

46

He can bring 46 acorns to the nest, as follows:

In Exchange A, trade 23 acorns for 23 grams of gold. {acorns, gold, silver, bronze}={ 0,23,0,0 }

In Exchange B, trade 23 grams of gold for 46 acorns. {acorns, gold, silver, bronze}={ 46,0,0,0 }

In Exchange A, trade nothing. {acorns, gold, silver, bronze}={ 46,0,0,0 }

He cannot have 47 or more acorns, so the answer is 46.



Sample input:
23
1 1 1
2 1 1


Sample output:
46

Submission status: Runtime Error

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

def F(N,A,B):
    AB = list(zip(A,B))
    AB = [(a,b) for a,b in AB if a < b] # 有用なやつだけ
    AB.sort(key = lambda x: x[1]/x[0], reverse = True)
    if len(AB) == 0:
        return N
    if len(AB) == 1:
        a,b = AB[0]
        x = N//a
        return N + (b-a) * x
    if len(AB) == 2:
        (a,b),(c,d) = AB
        # 2種類目の硬価はa回未満しか使わない：ac個はa優先なので
        return max(N + (N - i * c) // a * (b-a) + i * (d-c) for i in range(M))
    # 効率の良いものから並んでいる
    dp = [0] * (N+1)
    for n in range(N+1):
        x = n
        for a,b in AB:
            if n >= a:
                y = dp[n-a] + b
                if x < y:
                    x = y
        dp[n] = x
    return dp[N]

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

answer = F(F(N,A,B),B,A)
print(answer)

Submission status: Runtime Error

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

def F(N,A,B):
    AB = list(zip(A,B))
    AB = [(a,b) for a,b in AB if a < b] # 有用なやつだけ
    AB.sort(key = lambda x: x[1]/x[0], reverse = True)
    if len(AB) == 0:
        return N
    if len(AB) == 1:
        a,b = AB[0]
        x = N//a
        return N + (b-a) * x
    if len(AB) == 2:
        (a,b),(c,d) = AB
        # 2種類目の硬価はa回未満しか使わない：ac個はa優先なので
        return max(N + (N - i * c) // a * (b-a) + i * (d-c) for i in range(M))
    # 効率の良いものから並んでいる
    dp = [0] * (N+1)
    for n in range(N+1):
        x = n
        for a,b in AB:
            if n >= a:
                y = dp[n-a] + b
                if x < y:
                    x = y
        dp[n] = x
    return dp[N]

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

answer = F(F(N,A,B),B,A)
print(answer)

Submission status: Runtime Error

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

def F(N,A,B):
    # n 個のどんぐりを持っている
    # a個がbの価値に変換できる
    AB = [(x,y) for x,y in zip(A,B) if x < y]
    dp = [0] * (N+1)
    for n in range(N+1):
        x = n
        for a,b in AB:
            if n >= a:
                y = dp[n-a] + b
                if x < y:
                    x = y
        dp[n] = x
    return dp[N]

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

answer = F(F(N,A,B),B,A)
print(answer)

Submission status: Runtime Error

Solution code:
# 新ステージでは、一度全部どんぐりに直してから換金を始めるとしてよい

def F(N, A, B):
  # N個のどんぐりを、Aで換金してからBに持っていく
  # Bでどんぐりに直す
  A,B = zip(*[(x,y) for x,y in zip(A,B) if x < y])
  dp = [0] * (N+1)
  for n in range(N+1):
    x = n
    for j in range(3):
      if n >= A[j]:
        y = dp[n-A[j]] + B[j]
        if x < y:
          x = y
    dp[n] = x
  return dp[N]

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

answer = F(F(N,A,B),B,A)
print(answer)

Submission status: Runtime Error

Solution code:
# 新ステージでは、一度全部どんぐりに直してから換金を始めるとしてよい

def F(N, A, B):
  # N個のどんぐりを、Aで換金してからBに持っていく
  # Bでどんぐりに直す
  A,B = zip(*((x,y) for x,y in zip(A,B) if x < y))
  dp = [0] * (N+1)
  for n in range(N+1):
    x = n
    for j in range(3):
      if n >= A[j]:
        y = dp[n-A[j]] + B[j]
        if x < y:
          x = y
    dp[n] = x
  return dp[N]

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

answer = F(F(N,A,B),B,A)
print(answer)

Submission status: Runtime Error

Solution code:
# 新ステージでは、一度全部どんぐりに直してから換金を始めるとしてよい

def F(N, A, B):
  # N個のどんぐりを、Aで換金してからBに持っていく
  # Bでどんぐりに直す
  A,B = zip(*(x,y for x,y in zip(A,B) if x < y))
  dp = [0] * (N+1)
  for n in range(N+1):
    x = n
    for j in range(3):
      if n >= A[j]:
        y = dp[n-A[j]] + B[j]
        if x < y:
          x = y
    dp[n] = x
  return dp[N]

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

answer = F(F(N,A,B),B,A)
print(answer)

Submission status: Runtime Error

Solution code:
n = int(input())
a,b,c = map(int,input().split())
d,e,f = map(int,input().split())
s = {0:a-d,1:b-e,2:c-f}
t = [[a,d],[b,e],[c,f]]
s = sorted(s.items(),key=lambda x:-x[1])
g=n
for i in range(3):
    if s[-1-i][1]<0:
        g+=-s[-1-i][1]*(n//t[s[-1-i][0]][0])
        n%=t[s[-1-i][0]][0]
        mrk=0
    if mrk==1:
        n=g
    mrk=1
    if s[-1-i][1]>0:
        g+=s[-1-i][1]*(n//t[s[-1-i][0]][1])
        n%=t[s[-1-i][0]][1]
        mrk=0
print(g)

Submission status: Runtime Error

Solution code:
n = int(input())
a,b,c = map(int,input().split())
d,e,f = map(int,input().split())
s = {0:a-d,1:b-e,2:c-f}
t = [[a,d],[b,e],[c,f]]
s = sorted(s.items(),key=lambda x:-x[1])
g=n
print(s)
for i in range(3):
    if s[-1-i][1]<0:
        g+=-s[-1-i][1]*(n//t[s[-1-i][0]][0])
        print(g)
        n%=t[s[-1-i][0]][0]
        mrk=0
    if mrk==1:
        n=g
    mrk=1
    if s[-1-i][1]>0:
        g+=s[-1-i][1]*(n//t[s[-1-i][0]][1])
        print(g)
        n%=t[s[-1-i][0]][1]
        mrk=0
print(g)

Submission status: Runtime Error

Solution code:

SIZE=3
def knapsack(i,j):
    if i==SIZE:
        return 0
    if dp[i][j] != -1:
        return dp[i][j]
    tmp=-1
    if j<weigh[i]:
        tmp=knapsack(i+1,j)
    else:
        tmp=max( knapsack(i+1,j), knapsack(i,j-weigh[i])+value[i] )
    dp[i][j]=tmp
    return tmp

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
bHIKUa=[[a[i],b[i],b[i]-a[i]] for i in range(SIZE)]
bHIKUa.sort(key=lambda x:-x[1])
weigh=[bHIKUa[i][0] for i in range(SIZE)]
value=[bHIKUa[i][2] for i in range(SIZE)]
# print(weigh,value)
dp=[[-1 for j in range(n+5)] for i in range(SIZE+5)]
newN=n+knapsack(0,n)
# print(newN)

weigh=[bHIKUa[SIZE-i-1][1] for i in range(SIZE)]
value=[-bHIKUa[SIZE-i-1][2] for i in range(SIZE)]
# print(weigh,value)
dp=[[-1 for j in range(newN+5)] for i in range(SIZE+5)]
ans=newN+knapsack(0,newN)
print(ans)

Submission status: Runtime Error

Solution code:
(lambda __g, __y, __print: [[(__print(solve(solve(N, A, B), B, A)), None)[1] for (__g['N'], __g['A'], __g['B']) in [((int(input()), list(map(int, input().split())), list(map(int, input().split()))))]][0] for __g['solve'], solve.__name__ in [(lambda n, a, b: (lambda __l: [[(lambda __items, __after, __sentinel: __y(lambda __this: lambda: (lambda __i: [[__this() for __l['dp'][__l['w']] in [(max(__l['w'], ((__l['dp'][(__l['w'] - __l['a'][0])] + __l['b'][0]) if ((__l['w'] - __l['a'][0]) >= 0) else __l['w']), ((__l['dp'][(__l['w'] - __l['a'][1])] + __l['b'][1]) if ((__l['w'] - __l['a'][1]) >= 0) else __l['w']), ((__l['dp'][(__l['w'] - __l['a'][2])] + __l['b'][2]) if ((__l['w'] - __l['a'][2]) >= 0) else __l['w'])))]][0] for __l['w'] in [(__i)]][0] if __i is not __sentinel else __after())(next(__items, __sentinel)))())(iter(range((__l['n'] + 1))), lambda: __l['dp'][-1], []) for __l['dp'] in [(([0] * (__l['n'] + 1)))]][0] for __l['n'], __l['a'], __l['b'] in [(n, a, b)]][0])({}), 'solve')]][0])(globals(), (lambda f: (lambda x: x(x))(lambda y: f(lambda: y(y)()))), __import__('builtins', level=0).__dict__['print'])

Submission status: Runtime Error

Solution code:
import sys

def trade(n, a, b):
    a0, a1, a2 = a
    b0, b1, b2 = b
    dp = [0] * (n+1)
    for i i range(1, n+1):
        gold, silver, copper = 0, 0, 0
        if i >= a0:
            gold = dp[i-a0] + b0
        if i >= a1:
            silver = dp[i-a1] + b1
        if i >= a2:
            copper = dp[i-a2] + b2
        dp[i] = max(i, gold, silver, copper)

    return dp[n]


def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    # Trade A -> B
    M = trade(N, A, B)
    # Trade B -> A
    return trade(M, B, A)


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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

def don(dk, rate, amin):
    if not rate:
        return dk
    if dk < amin:
        return dk
    if dp[dk] != -1:
        return dp[dk]
    mx = 0
    for a, b in rate:
        if a > dk: continue
        tmp = don(dk - a, rate, amin) + b
        if tmp > mx:
            mx = tmp
    dp[dk] = mx
    return mx

n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
atob = []
btoa = []
amin = 10 ** 7
bmin = 10 ** 7
for a, b in zip(aa, bb):
    if a < b:
        atob.append([a, b])
        if a < amin:
            amin = a
    elif a > b:
        btoa.append([b, a])
        if b < bmin:
            bmin = b
print(atob, amin)
print(btoa, bmin)
dp = [-1] * (n + 1)
n = don(n, atob, amin)
print(n)
dp = [-1] * (n + 1)
print(don(n, btoa, bmin))

Submission status: Runtime Error

Solution code:
def don(dk, rate, amin):
    if not rate:
        return dk
    if dk < amin:
        return dk
    if dp[dk] != -1:
        return dp[dk]
    re = []
    for a, b in rate:
        re += [don(dk - a, rate, amin) + b]
    dp[dk] = re0 = max(re)
    return re0

n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))
atob = []
btoa = []
amin = 10 ** 7
bmin = 10 ** 7
for a, b in zip(aa, bb):
    if a < b:
        atob.append([a, b])
        if a < amin:
            amin = a
    elif a > b:
        btoa.append([b, a])
        if b < bmin:
            bmin = b
dp=[-1]*(n+1)
n = don(n, atob, amin)
dp=[-1]*(n+1)
print(don(n, btoa, bmin))

Submission status: Runtime Error

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
max=a[-1]
min=a[0]
if n==2:
    print(max-min)
    print(max,min)
    exit()
ans=0
if a[-1]<0:
    ans+=-sum(a)+max*2
elif a[0]>0:
    ans+=sum(a)-min*2
else:
    for x in a:
        ans+=abs(x)
print(ans)
X=max
Y=min
for i in range(1,n-1):
    if a[i]>=0:
        x=Y
        y=a[i]
        print(x,y)
        Y=x-y    
    else:
        x=X
        y=a[i]
        print(x,y)
        X=x-y
print(X,Y)

Submission status: Runtime Error

Solution code:
N = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))

# A -> Bで増えるドングリの最大値
def solve(n, ga, sa, ba, gb, sb, bb):
    gd, sd, bd = gb - ga, sb - sa, bb - ba

    if bd <= 0 and sd <= 0 and gd <= 0:
        return n

    elif bd <= 0 and sd <= 0 and gd > 0:
        return n + gd * (n // ga)

    elif bd <= 0 and sd > 0 and bd<= 0:
        return n + sd * (n // sa)

    elif bd <= 0 and sd > 0 and bd > 0:
        val = 0
        for k in range(n//ga + 1):
            l = (n - k * ga) // sa
            val = max(val, n + k * gd + l * sd)
        return val
    
    elif bd > 0 and sd <= 0 and bd <= 0:
        return n + bd * (n // ba)
    
    elif bd > 0 and sd <= 0 and gd > 0:
        val = 0
        for k in range(n//ga + 1):
            l = (n - k * ga) // ba
            val = max(val, n + k * gd + l * bd)
        return val

    elif bd > 0 and sd > 0 and gd <= 0:
        val = 0
        for k in range(n//sa + 1):
            l = (n - k * sa) // ba
            val = max(val, n + k * sd + l * bd)
        return val
    
    elif bd > 0 and sd > 0 and gd > 0:
        val = 0
        for k in range(n//ga + 1):
            for l in range((n - k * ga) // sa + 1):
                m = (n - k * ga - l * sa) // ba
                val = max(val, n + k * gd + l * sd + m * bd)
        return val


n1 = solve(N, ga, sa, ba, gb, sb, bb)
n2 = solve(n1, gb, sb, bb, ga, sa, ba)
print(n2)

Submission status: Runtime Error

Solution code:

SIZE=3
def knapsack(i,j):
    if i==SIZE:
        return 0
    if dp[i][j] != -1:
        return dp[i][j]
    res=-1
    if j<weigh[i]:
        res=knapsack(i+1,j)
    else:
        res=max( knapsack(i+1,j), knapsack(i,j-weigh[i])+value[i] )
    dp[i][j]=res
    return res

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
bHIKUa=[[a[i],b[i],b[i]-a[i]] for i in range(SIZE)]
bHIKUa.sort(key=lambda x:-x[1])
weigh=[bHIKUa[i][0] for i in range(SIZE)]
value=[bHIKUa[i][2] for i in range(SIZE)]
# print(weigh,value)
dp=[[-1 for j in range(n+1)] for i in range(SIZE+1)]
newN=n+knapsack(0,n)
# print(newN)

weigh=[bHIKUa[SIZE-i-1][1] for i in range(SIZE)]
value=[-bHIKUa[SIZE-i-1][2] for i in range(SIZE)]
# print(weigh,value)
dp=[[-1 for j in range(newN+1)] for i in range(SIZE+1)]
ans=newN+knapsack(0,newN)
print(ans)

Submission status: Runtime Error

Solution code:
 from collections import deque


def transaction(N, r):
    x = r[0]
    n = int(N / x[1])
    if N % x[1] == 0:
        return n * x[2]
    if len(r) == 1:
        return n * x[2] + N - n * x[1]
    r.popleft()
    s = N
    for i in range(n + 1):
        tmp = i * x[2] + transaction(N - i * x[1], r)
        if tmp > s:
            s = tmp
    return s

N = int(input())
A = [int(e) for e in input().split()]
B = [int(e) for e in input().split()]

r = []
for i in range(3):
    (a, b) = (A[i], B[i])
    if b > a:
        r.append((b / a, a, b))

if len(r) > 0:
    r.sort(reverse=True)
    dr = deque(maxlen=3)
    for x in r:
        dr.append(x)
    N = transaction(N, dr)

r = []
for i in range(3):
    (a, b) = (A[i], B[i])
    if a > b:
        r.append((a / b, b, a))

if len(r) > 0:
    r.sort(reverse=True)
    dr = deque(maxlen=3)
    for x in r:
        dr.append(x)
    N = transaction(N, dr)

print(N)

Submission status: Runtime Error

Solution code:
from collections import deque


def transaction(N, r):
    x = r[0]
    n = int(N / x[1])
    if N % x[1] == 0:
        return n * x[2]
    if len(r) == 1:
        return n * x[2] + N - n * x[1]
    r.popleft()
    s = N
    for i in range(n + 1):
        tmp = i * x[2] + transaction(N - i * x[1], r)
        if tmp > s:
            s = tmp
    return s

N = int(input())
A = [int(e) for e in input().split()]
B = [int(e) for e in input().split()]

r = []
for i in range(3):
    (a, b) = (A[i], B[i])
    if b > a:
        r.append((b / a, a, b))

if len(r) > 0:
    r.sort(reverse=True)
    dr = deque(maxlen=3)
    for x in r:
        dr.append(x)
    N = transaction(N, dr)

r = []
for i in range(3):
    (a, b) = (A[i], B[i])
    if a > b:
        r.append((a / b, b, a))

if len(r) > 0:
    r.sort(reverse=True)
    dr.clear()
    for x in r:
        dr.append(x)
    N = transaction(N, dr)

print(N)

Submission status: Runtime Error

Solution code:
from collections import deque


def transaction(N, r):
    if len(r) == 0:
        return N
    x = r[0]
    n = int(N / x[1])
    if N % x[1] == 0 or len(r) == 1:
        return n * x[2]
    r.popleft()
    s = N
    for i in range(n + 1):
        tmp = i * x[2] + transaction(N - i * x[1], r)
        if tmp > s:
            s = tmp
    return s

N = int(input())
A = [int(e) for e in input().split()]
B = [int(e) for e in input().split()]

r = []
for i in range(3):
    (a, b) = (A[i], B[i])
    if b > a:
        r.append((b / a, a, b))

r.sort(reverse=True)
dr = deque(maxlen=3)
for x in r:
    dr.append(x)
N = transaction(N, dr)

r = []
for i in range(3):
    (a, b) = (A[i], B[i])
    if a > b:
        r.append((a / b, b, a))

r.sort(reverse=True)
dr.clear()
for x in r:
    dr.append(x)

print(transaction(N, r))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)

n = int(input())
aa = list(map(int, input().split()))
bb = list(map(int, input().split()))

rates_1 = []
rates_2 = []
for i in range(3):
	if aa[i] > bb[i]:
		rates_2.append([bb[i], aa[i]])
	else:
		rates_1.append([aa[i], bb[i]])

def dp(rest, obtained, memo, rates):
	#print(rest, obtained)
	if rest < 0:
		return -10000

	if memo[rest] != -1:
		return memo[rest]

	memo[rest] = max([dp(rest - x[0],  obtained + x[1], memo, rates) for x in rates_1] + [rest + obtained])
	return memo[rest]


if len(rates_1) > 0:
	memo_1 = [-1 for _ in range(n + 1)]
	m = dp(n, 0, memo_1, rates_1)
else:
	m = n

if len(rates_2) > 0:
	memo_2 = [-1 for _ in range(n + 1)]
	ans = dp(m, 0, memo_2, rates_2)
else:
	ans = m

print(ans)

Submission status: Runtime Error

Solution code:
SIZE=3
# 深さ優先探索(再帰関数)をメモ化
# i番目以降の荷物を重みj以下で詰めたときの価値の和の最大値を返す
def knapsack(i,j,w,v):
    if i==SIZE:
        return 0
    if dp[i][j] != -1:
        return dp[i][j]
    res=-1
    if j<w[i]:
        res=knapsack(i+1,j,w,v)
    else:
        res=max( knapsack(i+1,j,w,v), knapsack(i,j-w[i],w,v)+v[i] )
    dp[i][j]=res
    return res

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
bHIKUa=[[a[i],b[i],b[i]-a[i]] for i in range(SIZE)]
bHIKUa.sort(key=lambda x:-x[1])
weigh=[bHIKUa[i][0] for i in range(SIZE)]
value=[bHIKUa[i][2] for i in range(SIZE)]
# print(weigh,value)
dp=[[-1 for j in range(n+1)] for i in range(SIZE)]
newN=n+knapsack(0,n,weigh,value)
# print(newN)

weigh=[bHIKUa[SIZE-i-1][1] for i in range(SIZE)]
value=[-bHIKUa[SIZE-i-1][2] for i in range(SIZE)]
# print(weigh,value)
dp=[[-1 for j in range(newN+1)] for i in range(SIZE)]
ans=newN+knapsack(0,newN,weigh,value)
print(ans)

Submission status: Runtime Error

Solution code:
SIZE=3
# i番目以降の荷物を重みj以下で詰めたときの価値の和の最大値を返す
def knapsack(i,j,w,v):
    if i==SIZE:
        return 0
    elif j<w[i]:
        return knapsack(i+1,j,w,v)
    else:
        return max(knapsack(i+1,j,w,v), knapsack(i,j-w[i],w,v)+v[i])
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
bHIKUa=[[a[i],b[i]-a[i]] for i in range(SIZE)]
bHIKUa.sort(key=lambda x:-x[1])
weigh=[bHIKUa[i][0] for i in range(SIZE)]
value=[bHIKUa[i][1] for i in range(SIZE)]
# print(bHIKUa,weigh,value)
newN=n+knapsack(0,n,weigh,value)
# print(newN)

aHIKUb=[[b[i],a[i]-b[i]] for i in range(3)]
aHIKUb.sort(key=lambda x:-x[1])
weigh=[aHIKUb[i][0] for i in range(SIZE)]
value=[aHIKUb[i][1] for i in range(SIZE)]
# print(aHIKUb,weigh,value)
ans=newN+knapsack(0,newN,weigh,value)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

def f(a,b,N):
    def cur(n):
        if n<0: return -2
        elif memo[n]!=-1: return memo[n]
        tmp=[]
        for i in range(3):
            if cur(n-a[i])!=-2: tmp.append(cur(n-a[i])+b[i])
        if max(tmp)>=0: memo[n]=max(tmp)
        else: memo[n]=-2
        return memo[n]
    
    memo=[0]+[-1]*(N)
    return cur(N)

import sys
N=int(input())

A=list(map(int,input().split()))
B=list(map(int,input().split()))

N=f(A,B,N)
N=f(B,A,N)
print(N)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

def f(a,b,N):
    
    def cur(n):
        if n<0: return -1
        if memo[n]!=-1: return memo[n]
        tmp=[]
        for i in range(3):
            if n-a[i]>=0: tmp.append(cur(n-a[i])+b[i])
        memo[n]=max(tmp)
        return memo[n]
    
    memo=[0]+[-1]*(N)
    return cur(N)

import sys
N=int(input())

A=list(map(int,input().split()))
B=list(map(int,input().split()))

N=f(A,B,N)
N=f(B,A,N)
print(N)

Submission status: Runtime Error

Solution code:
def gcd(a,b):
    if b>a:
        a,b=b,a
    while b:
        a,b=b, a%b
    return a

def f(a,b,N):
    
    def cur(n):
        if n<0: return -1
        if memo[n]!=-1: return memo[n]
        tmp=[]
        memo[n]=max(cur(n-a[i])+b[i] for i in range(3))
        return memo[n]
    
    memo=[0]+[-1]*(N)
    return cur(N)

import sys
N=int(input())

A=list(map(int,input().split()))
B=list(map(int,input().split()))

N=f(A,B,N)
N=f(B,A,N)
print(N)

Submission status: Runtime Error

Solution code:
N, K  = map(int, input().split())
A_list  = list( map(int, input().split()))

import sys
sys.setrecursionlimit(20000000)

ruisekiwa =[0]
for i, a in enumerate(A_list):
    ruisekiwa.append(ruisekiwa[i] + a)
#print(ruisekiwa)


def ruiseki_count(n,result):
    if n == 0:
        return result
    #print(len(A_list) + 1 - n,'len')
    kekka = False
    for i in range(len(A_list) + 1 - n):
        if ruisekiwa[n + i] - ruisekiwa[i] >= K:
            #print(ruisekiwa[n + i] - ruisekiwa[i],'ruiseki')
            result +=1
            kekka = True
    if not kekka:
        return result

    return ruiseki_count(n-1,result)

result = ruiseki_count(len(A_list),0)
print(result)

'''
2 4 1 
'''
#print(A_list)

Submission status: Runtime Error

Solution code:
import numpy as np
import math

def main():
    n = int(input())
    gsb_a = list(map(int, input().split(' ')))
    gsb_b = list(map(int, input().split(' ')))

    ## gsbをi番目まで利用して，j個のどんぐりを消費するときの価値の最大値 dpa[i,j]
    dpa = np.zeros([len(gsb_a)+1,n+1], dtype=int)
    dpa[0,:] = np.array(range(len(dpa[0])))
    for i in range(len(gsb_a)):
        for j in range(n+1):
            dpa[i+1,j] = dpa[i,j]
            if j >= gsb_a[i]:
                dpa[i+1,j] = max(dpa[i+1,j-gsb_a[i]]+gsb_b[i], dpa[i+1,j])

    m = max(n, dpa[len(gsb_a),n])

    dpb = np.zeros([len(gsb_b)+1,m+1], dtype=int)
    dpb[0,:] = np.array(range(len(dpb[0])))
    for i in range(len(gsb_b)):
        for j in range(m+1):
            dpb[i+1,j] = dpb[i,j]
            if j >= gsb_b[i]:
                dpb[i+1,j] = max(dpb[i+1,j-gsb_b[i]]+gsb_a[i], dpb[i+1,j])

    ## print(dpa, dpb)
    print(max(n, m, dpb[len(gsb_b),m]))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n = I()
    a = LI()
    b = LI()
    if sum(a) > sum(b):
        a,b = b,a
    c = sorted([(ai,bi) for ai,bi in zip(a,b)], key=lambda x: x[0]-x[1])

    if c[2][0] < c[2][1]:
        m = n
        for i in range(0,n+1,a[0]):
            k = n - i
            u = i // a[0] * b[0]
            for j in range(0,k+1,a[1]):
                l = k - j
                t = u + j // a[1] * b[1] + l % a[2] + l // a[2] * b[2]
                if m < t:
                    m = t
        return m

    m = n
    if c[1][0] < c[1][1]:
        for i in range(0,n+1,c[0][0]):
            k = n - i
            t = i // c[0][0] * c[0][1]
            t += k % c[1][0]
            t += k // c[1][0] * c[1][1]
            if m < t:
                m = t
    else:
        t = n % c[0][0]
        t += n // c[0][0] * c[0][1]
        if m < t:
            m = t

    r = m
    if c[1][0] > c[1][1]:
        for i in range(0,m+1,c[1][1]):
            k = m - i
            t = i // c[1][1] * c[1][0]
            t += k % c[2][1]
            t += k // c[2][1] * c[2][0]
            if r < t:
                r = t
    else:
        t = 1 // 0
        t = m % c[2][1]
        t += m // c[2][1] * c[2][0]
        if r < t:
            r = t

    return r


print(main())

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n = I()
    a = LI()
    b = LI()
    if sum(a) > sum(b):
        a,b = b,a
    c = sorted([(ai,bi) for ai,bi in zip(a,b)], key=lambda x: x[0]-x[1])

    if c[2][0] < c[2][1]:
        m = n
        for i in range(0,n+1,a[0]):
            k = n - i
            u = i // a[0] * b[0]
            for j in range(0,k+1,a[1]):
                l = k - j
                t = u + j // a[1] * b[1] + l % a[2] + l // a[2] * b[2]
                if m < t:
                    m = t
        return m

    m = n
    if c[1][0] < c[1][1]:
        for i in range(0,n+1,c[0][0]):
            k = n - i
            t = i // c[0][0] * c[0][1]
            t += k % c[1][0]
            t += k // c[1][0] * c[1][1]
            if m < t:
                m = t
    else:
        t = 1 // 0
        t = n % c[0][0]
        t += n // c[0][0] * c[0][1]
        if m < t:
            m = t

    r = m
    if c[1][0] > c[1][1]:
        for i in range(0,m+1,c[1][1]):
            k = m - i
            t = i // c[1][1] * c[1][0]
            t += k % c[2][1]
            t += k // c[2][1] * c[2][0]
            if r < t:
                r = t
    else:
        t = m % c[2][1]
        t += m // c[2][1] * c[2][0]
        if r < t:
            r = t

    return r


print(main())

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n = I()
    a = LI()
    b = LI()
    if sum(a) > sum(b):
        a,b = b,a
    c = sorted([(ai,bi) for ai,bi in zip(a,b)], key=lambda x: x[0]-x[1])

    if c[2][0] < c[2][1]:
        return n // 0
        m = n
        for i in range(0,n+1,a[0]):
            k = n - i
            u = i // a[0] * b[0]
            for j in range(0,k+1,a[1]):
                l = k - j
                t = u + j // a[1] * b[1] + l % a[2] + l // a[2] * b[2]
                if m < t:
                    m = t
        return m

    m = n
    if c[1][0] < c[1][1]:
        for i in range(0,n+1,c[0][0]):
            k = n - i
            t = i // c[0][0] * c[0][1]
            t += k % c[1][0]
            t += k // c[1][0] * c[1][1]
            if m < t:
                m = t
    else:
        t = n % c[0][0]
        t += n // c[0][0] * c[0][1]
        if m < t:
            m = t

    r = m
    if c[1][0] > c[1][1]:
        for i in range(0,m+1,c[1][1]):
            k = m - i
            t = i // c[1][1] * c[1][0]
            t += k % c[2][1]
            t += k // c[2][1] * c[2][0]
            if r < t:
                r = t
    else:
        t = m % c[2][1]
        t += m // c[2][1] * c[2][0]
        if r < t:
            r = t

    return r


print(main())

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n = I()
    a = LI()
    b = LI()
    if sum(a) > sum(b):
        a,b = b,a
    c = sorted([(ai,bi) for ai,bi in zip(a,b)], key=lambda x: x[0]-x[1])

    if c[2][0] < c[2][1]:
        m = n
        for i in range(0,n+1,a[0]):
            k = n - i
            tm = 0
            u = i // a[0] * b[0]
            for j in range(0,k+1,a[1]):
                l = k - j
                t = u + j // a[1] * b[1] + l % a[2] + l // a[2] * b[2]
                if m < t:
                    m = t
        return m

    m = n
    if c[1][0] < c[1][1]:
        for i in range(0,n+1,c[0][0]):
            k = n - i
            t += i // c[0][0] * c[0][1]
            t += k % c[1][0]
            t += k // c[1][0] * c[1][1]
            if m < t:
                m = t
    else:
        m = n % c[0][0]
        m += n // c[0][0] * c[0][1]

    r = m
    if c[1][0] > c[1][1]:
        for i in range(0,m+1,c[1][1]):
            k = m - i
            t += i // c[1][1] * c[1][0]
            t += k % c[2][1]
            t += k // c[2][1] * c[2][0]
            if r < t:
                r = t
    else:
        r = m % c[2][1]
        r += m // c[2][1] * c[2][0]

    return r


print(main())