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

Solution code:
def solve(n, ga, sa, ba, gb, sb, bb):
    ans = n
    for g in range(1 if ga >= gb else n // ga + 1):
        n2 = n - g * ga
        tmp1 = g * gb
        if ba >= bb:
            s = n2 // sa
            ans = max(ans, n2 + tmp1, n2 - s * sa + tmp1 + s * sb)
        elif sa >= sb:
            b = n2 // ba
            ans = max(ans, n2 + tmp1, n2 - b * ba + tmp1 + b * bb)
        else:
            for s in range(n2 // sa + 1):
                b = (n2 - s * sa) // ba
                ans = max(ans, n2 - s * sa - b * ba + tmp1 + s * sb + b * bb)
    return ans


n = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))
n2 = solve(n, ga, sa, ba, gb, sb, bb)
n3 = solve(n2, gb, sb, bb, ga, sa, ba)
print(n3)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

# case
# すべて a > b
# すべて b < a
# 2個  a > b
# 1個  a > b

# weight:ga price:gb どんぐり weight:1 price:1


vmax = 0
for g in range(0,N + 1, ga):
    for s in range(0,N + 1 - g, sa):
        v = (g // ga) * gb + (s // sa) * sb
        amari = N - g - s
        if amari < 0:
            break
        if ba < bb:
            v += amari // ba * bb
            amari %= ba
        v += amari

        vmax = max(vmax, v)

D = vmax
vmax = D

if ba < bb:
    tmp = sa,sb
    sa,sb = ba,bb
    ba,bb = tmp

for g in range(0,D + 1, gb):
    if ga < gb and g > 0:
        break
    for s in range(0, D + 1 - g, sb):
        if sa < sb and s > 0:
            break
        v = (g // gb) * ga + (s // sb) * sa
        amari = D - g - s
        if amari < 0:
            break
        if ba > bb:
            v += amari // bb * ba
            amari %= bb
        v += amari

        vmax = max(vmax, v)

print(vmax)

Submission status: Time Limit Exceeded

Solution code:

# 個数制限なしナップサック問題を2回やる？

"""前半の交換：
重さはga, sa, ba 合計がN以下
価値がgb, sb, bb これを最大化
"""
n = int(input())
a_rate =list(map(int, input().split() ))
b_rate =list(map(int, input().split() ))
a_rate.append(1)
b_rate.append(1)

dp1 = [[0 for j in range(n+1)] for i in range(5)]

for i in range(4):
	for j in range(n+1):
		if j < a_rate[i]:
			dp1[i + 1][j] = dp1[i][j]
		else:
			dp1[i + 1][j] = max(dp1[i][j], dp1[i + 1][j - a_rate[i]] + b_rate[i])

mid_donguri = dp1[4][n]

dp2 = [[mid_donguri for j in range(mid_donguri+1)] for i in range(4)]

"""前半の交換：
重さはgb, sb, bb 合計がN以下
価値がga, sa, ba これを最大化
"""
num_valid_trade = 0
for i in range(3):
	if a_rate[i] > b_rate[i]:
		num_valid_trade += 1 

if num_valid_trade == 0:
	print(mid_donguri)
	exit()
if num_valid_trade == 1:
	for i in range(3):
		if a_rate[i] > b_rate[i]:
			a = a_rate[i]
			b = b_rate[i]
	ans = mid_donguri % b + (mid_donguri // b * a)
	print(ans)
	exit()

# num_valid_trade == 2 or 3

for i in range(3):
	for j in range(mid_donguri+1):
		if j < b_rate[i]:
			dp2[i + 1][j] = dp2[i][j]
		else:
			dp2[i + 1][j] = max(dp2[i][j], dp2[i + 1][j - b_rate[i]] + a_rate[i] - b_rate[i])

print(dp2[3][mid_donguri])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 II(): return int(sys.stdin.readline())
def SI(): return input()

def get(n, rates):
    rates.sort()
    r0, a0, b0 = rates[0]
    r1, a1, b1 = rates[1]
    r2, a2, b2 = rates[2]
    if r0 >= 1:
        return n
    if r1 >= 1 or a0 == a1 == a2 or r0 == r1 == r2:
        return (n % a0) + (n // a0) * b0
    if r2 >= 1 or r1 == r2 or a1 == a2 or r0 == r1 or a0 == a1 or a0 == a2:
        if r0 == r1 or a0 == a1:
            r1, a1, b1 = r2, a2, b2
        ret = n
        for m0 in range(n // a0 + 1):
            rem = n - m0 * a0
            d = rem % a1
            tmp = d + m0 * b0 + (rem // a1) * b1
            ret = max(ret, tmp)
        return ret
    ret = n
    for m0 in range(n // a0 + 1):
        d0 = m0 * b0
        rem = n - m0 * a0
        for m1 in range(rem // a1 + 1):
            n2 = rem - m1 * a1
            d = n2 % a2
            tmp = d + d0 + m1 * b1 + (n2 // a2) * b2
            ret = max(ret, tmp)
    return ret

def main():
    N = II()
    ga, sa, ba = LI()
    gb, sb, bb = LI()
    rates = [[ga / gb, ga, gb], [sa / sb, sa, sb], [ba / bb, ba, bb]]
    rates2 = [[gb / ga, gb, ga], [sb / sa, sb, sa], [bb / ba, bb, ba]]
    ans = N
    ans = get(ans, rates)
    ans = get(ans, rates2)
    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
def knapsack_123(values,weights,capacity):
    work = [0 for i in range(capacity+1)]
    for c in range(1, capacity+1):
        candidates = [val + work[c-weight]
                      for val,weight in zip(values,weights) if weight <= c]
        work[c] = max(candidates) if candidates != [] else 0
    usedcap=min([c for c,w in enumerate(work) if w==work[-1]])
    return work[-1],usedcap
def sol(inp=input):
    n=int(inp())
    prices_a=list(map(int,inp().split()))
    prices_b=list(map(int,inp().split()))
    
    valA,usedcapA=knapsack_123(values=[xb for xa,xb in zip(prices_a,prices_b) if xa<xb],
                               weights=[xa for xa,xb in zip(prices_a,prices_b) if xa<xb],
                               capacity=n)
    capB=valA+n-usedcapA
    valB,usedcapB=knapsack_123(values=[xa for xa,xb in zip(prices_a,prices_b) if xa>xb],
                               weights=[xb for xa,xb in zip(prices_a,prices_b) if xa>xb],
                               capacity=capB)
    return '{}'.format(valB+capB-usedcapB)
  
print(sol())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

ans2 = n

for c in range(3):
    ans1 = 0
    for i in range(n + 1):
        for j in range(n + 1 - i):
            d = n
            d += (B[0] - A[0]) * (i // A[0])
            d += (B[1] - A[1]) * (j // A[1])
            k = n - i - j if c == 1 else 0
            # assert k >= 0
            d += (B[2] - A[2]) * (k // A[2])
        
            ans1 = max(ans1, d)

    for i in range(ans1 + 1):
        for j in range(ans1 + 1 - i):
            d = ans1
            d += (A[0] - B[0]) * (i // B[0])
            d += (A[1] - B[1]) * (j // B[1])
            k = ans1 - i - j if c == 2 else 0
            # assert k >= 0
            d += (A[2] - B[2]) * (k // B[2])
        
            ans2 = max(ans2, d)

print(ans2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_rate = list(map(int, input().split()))
B_rate = list(map(int, input().split()))


def trade(d, buy_rate, sell_rate):
    stuff = []
    for i in range(3):
        stuff.extend([[buy_rate[i], sell_rate[i]] for _ in range((d // buy_rate[i]))])
    stuff.extend([[1, 1] for _ in range(d)])
    dp = [[0 for j in range(d+1)] for i in range((len(stuff) + 1))]
    for i in range(1, len(stuff) + 1):
        for j in range(d+1):
            if j-stuff[i-1][0] >= 0:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-stuff[i-1][0]] + stuff[i-1][1])
            else:
                dp[i][j] = dp[i-1][j]
    return max(dp[-1])


print(trade(trade(N, A_rate, B_rate), B_rate, A_rate))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
change = [0,0,0]

for i in range(3):
    if a[i] > b[i]:
        change[i] = 1
    elif a[i] < b[i]:
        change[i] = 2

mdngr = 0
for i in range(n//a[0]+1):
    for j in range((n-a[0]*i)//a[1]+1):
        for k in range((n-a[0]*i-a[1]*j)//a[2]+1):
            dngr = n+i*(b[0]-a[0])+j*(b[1]-a[1])+k*(b[2]-a[2])
            if dngr > mdngr:
                mdngr = dngr

n = mdngr
for i in range(n//b[0]+1):
    for j in range((n-b[0]*i)//b[1]+1):
        for k in range((n-b[0]*i-b[1]*j)//b[2]+1):
            dngr = n+i*(a[0]-b[0])+j*(a[1]-b[1])+k*(a[2]-b[2])
            if dngr > mdngr:
                mdngr = dngr
print(mdngr)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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


# case
# すべて a > b
# すべて b < a
# 2個  a > b
# 1個  a > b

# weight:ga price:gb どんぐり weight:1 price:1


vmax = 0
for g in range(N+1):
    for s in range(N+1-g):
        v = (g//ga)*gb + (s//sa)*sb
        amari = N - g -s
        if amari < 0:
            break
        if ba < bb:
            v += amari//ba * bb
            amari %= ba
        v += amari

        vmax = max(vmax,v)

D = vmax
vmax = D
for g in range(D + 1):
    if ga < gb and g  > 0:
        break
    for s in range(D + 1 - g):
        if sa < sb and s > 0:
            break
        v = (g//gb)*ga + (s//sb)*sa
        amari = D - g - s
        if amari < 0:
            break
        if ba > bb:
            v += amari // bb * ba
            amari %= bb
        v += amari

        vmax = max(vmax, v)

print(vmax)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

ans2 = n

for a in range(3):
    for b in range(3):
        for c in range(3):
            ans1 = 0
            for i in range(n + 1 if a == 1 else 1):
                for j in range(n + 1 - i if b == 1 else 1):
                    d = n
                    d += (B[0] - A[0]) * (i // A[0])
                    d += (B[1] - A[1]) * (j // A[1])
                    k = n - i - j if c == 1 else 0
                    # assert k >= 0
                    d += (B[2] - A[2]) * (k // A[2])
                
                    ans1 = max(ans1, d)

            for i in range(ans1 + 1 if a == 2 else 1):
                for j in range(ans1 + 1 - i if b == 2 else 1):
                    d = ans1
                    d += (A[0] - B[0]) * (i // B[0])
                    d += (A[1] - B[1]) * (j // B[1])
                    k = ans1 - i - j if c == 2 else 0
                    # assert k >= 0
                    d += (A[2] - B[2]) * (k // B[2])
                
                    ans2 = max(ans2, d)

print(ans2)

Submission status: Time Limit Exceeded

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

wa_orig = [1, ga, sa, ba]
wb_orig = [1, gb, sb, bb]

wa = []
wb = []
for i in range(len(wa_orig)):
  if wa_orig[i] <= wb_orig[i]:
    wa.append(wa_orig[i])
    wb.append(wb_orig[i])

dp = [0] * (n+1)
for i in range(1, n+1):
  d = []
  for ai in range(len(wa)):
    w1 = wa[ai]
    w2 = wb[ai]
    if i-w1 <0:
      continue
    d.append(dp[i-w1] + w2)
  dp[i] = max(d)


wa = []
wb = []
for i in range(len(wa_orig)):
  if wa_orig[i] >= wb_orig[i]:
    wa.append(wa_orig[i])
    wb.append(wb_orig[i])


nn = dp[-1]

if len(wa) == 2:
  # greedy
  w1 = wb[1]
  w2 = wa[1]
  value = (nn // w1) * w2 + (nn % w1)
  print(value)
  exit(0)


dp = [0] * (nn+1)
for i in range(1, nn+1):
  d = []
  for ai in range(len(wb)):
    w1 = wb[ai]
    w2 = wa[ai]
    if i-w1 <0:
      continue
    d.append(dp[i-w1] + w2)
  dp[i] = max(d)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

N = int(input())
ag,a_s,ab = [int(i) for i in input().split()]
bg,bs,bb = [int(i) for i in input().split()]

dp = [0 for i in range(N+1)]
g_v = bg - ag
s_v = bs - a_s
b_v = bb - ab
if g_v > 0:
    for i in range(ag,N+1):
        dp[i] = max(dp[i],dp[i-ag] + g_v)
if s_v > 0:
    for i in range(a_s,N+1):
        dp[i] = max(dp[i],dp[i-a_s] + s_v)
if b_v > 0:
    for i in range(ab,N+1):
        dp[i] = max(dp[i],dp[i-ab] + b_v)

N += max(dp)
dp = [0 for i in range(N+1)]
g_v = -bg + ag
s_v = -bs + a_s
b_v = -bb + ab
if g_v > 0:
    for i in range(bg,N+1):
        dp[i] = max(dp[i],dp[i-bg] + g_v)
if s_v > 0:
    for i in range(bs,N+1):
        dp[i] = max(dp[i],dp[i-bs] + s_v)
if b_v > 0:
    for i in range(bb,N+1):
        dp[i] = max(dp[i],dp[i-bb] + b_v)

N += max(dp)
print(N)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

#0gold，1silver，2blonze
R = [A[0]/B[0],A[1]/B[1],A[2]/B[2]]
AtoB,BtoA = [],[]
for i in range(len(R)):
    if R[i]>1: BtoA.append(i)
    elif R[i]<1: AtoB.append(i)
        
#AtoB Phase
if len(AtoB)==1:
    N = ((N//A[AtoB[0]])*B[AtoB[0]])+(N%A[AtoB[0]])
elif len(AtoB)>=2: #ここでdp
    dp = [N for i in range(N+1)]
    for i in range(1,N+1):
        O = [dp[i-1]]
        for j in range(len(AtoB)):
            if i>=A[AtoB[j]]: O.append(dp[i-A[AtoB[j]]]-A[AtoB[j]]+B[AtoB[j]])
        dp[i] = max(O)
    N = dp[N]
    
#BtoA Phase
if len(BtoA)==1:
    N = ((N//B[BtoA[0]])*A[BtoA[0]])+(N%B[BtoA[0]])
elif len(BtoA)>=2: #ここでdp
    dp = [N for i in range(N+1)]
    for i in range(1,N+1):
        O = [dp[i-1]]
        for j in range(len(BtoA)):
            if i>=B[BtoA[j]]: O.append(dp[i-B[BtoA[j]]]-B[BtoA[j]]+A[BtoA[j]])
        dp[i] = max(O)
    N = dp[N]
    
print(N)

Submission status: Time Limit Exceeded

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

wa_orig = [1, ga, sa, ba]
wb_orig = [1, gb, sb, bb]

wa = []
wb = []
for i in range(len(wa_orig)):
  if wa_orig[i] <= wb_orig[i]:
    wa.append(wa_orig[i])
    wb.append(wb_orig[i])

dp = [0] * (n+1)
for i in range(1, n+1):
  d = []
  for ai in range(len(wa)):
    w1 = wa[ai]
    w2 = wb[ai]
    if i-w1 <0:
      continue
    d.append(dp[i-w1] + w2)
  dp[i] = max(d)


wa = []
wb = []
for i in range(len(wa_orig)):
  if wa_orig[i] >= wb_orig[i]:
    wa.append(wa_orig[i])
    wb.append(wb_orig[i])


nn = dp[-1]
dp = [0] * (nn+1)
for i in range(1, nn+1):
  d = []
  for ai in range(len(wb)):
    w1 = wb[ai]
    w2 = wa[ai]
    if i-w1 <0:
      continue
    d.append(dp[i-w1] + w2)
  dp[i] = max(d)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000


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

ag,a_s,ab = A
bg,bs,bb = B
dp = [0 for i in range(N+1)]
g_v = bg - ag
s_v = bs - a_s
b_v = bb - ab
if g_v > 0:
    for i in range(ag,N+1):
        dp[i] = max(dp[i],dp[i-ag] + g_v)
if s_v > 0:
    for i in range(a_s,N+1):
        dp[i] = max(dp[i],dp[i-a_s] + s_v)
if b_v > 0:
    for i in range(ab,N+1):
        dp[i] = max(dp[i],dp[i-ab] + b_v)

N += max(dp)
dp = [0 for i in range(N+1)]
g_v = -bg + ag
s_v = -bs + a_s
b_v = -bb + ab
if g_v > 0:
    for i in range(bg,N+1):
        dp[i] = max(dp[i],dp[i-bg] + g_v)
if s_v > 0:
    for i in range(bs,N+1):
        dp[i] = max(dp[i],dp[i-bs] + s_v)
if b_v > 0:
    for i in range(bb,N+1):
        dp[i] = max(dp[i],dp[i-bb] + b_v)

N += max(dp)
print(N)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
bf,bs = 0,0
fir = []
sec = []
fi1 = 1
se1 = 1
ans = n
ansf = n
for i in range(3):
  if a[i]>b[i]:
    if b[i] == 1:
      bs = 1
      if se1 < a[i]:
        se1 = a[i]
    else:     
      sec.append((a[i],b[i]))
  else:
    if a[i] == 1:
      bf = 1
      if fi1 < b[i]:
        fi1 = b[i]
    else:
      fir.append((b[i],a[i]))
sec += [(n,n),(n,n),(n,n)]
fir += [(n,n),(n,n),(n,n)]
for p in range(n//fir[0][1]+1):
  for q in range((n-p*fir[0][1])//fir[1][1]+1):
    rg = n - p*fir[0][1] - q*fir[1][1]
    if rg < 0:
      continue
    if bf:
      res = rg
      r = 0
    else:
      res = rg%fir[2][1]
      r = rg//fir[2][1]
    en = p*fir[0][0] + q*fir[1][0] + r*fir[2][0] + res*fi1
    if ansf < en:
      ansf = en
for p in range(ansf//sec[0][1]+1):
  for q in range((ansf-p*sec[0][1])//sec[1][1]+1):
    rg = ansf - p*sec[0][1] - q*sec[1][1]
    if rg < 0:
      continue
    if bs:
      res =  rg
      r = 0
    else:
      res = rg%sec[2][1]
      r = rg//sec[2][1]
    en = p*sec[0][0] + q*sec[1][0] + r*sec[2][0] + res*se1
    if ans < en:
      ans = en
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def knapsack_123(values,weights,capacity):
    work = [0 for i in range(capacity+1)]
    for c in range(1, capacity+1):
        candidates = [val + work[c-weight]
                      for val,weight in zip(values,weights) if weight <= c]
        work[c] = max(candidates) if candidates != [] else 0
    return work[-1]
def sol(inp=input):
    n=int(inp())
    prices_a=list(map(int,inp().split()))+[1]
    prices_b=list(map(int,inp().split()))+[1]
    valA=knapsack_123(values=prices_b,weights=prices_a,capacity=n)
    valB=knapsack_123(values=prices_a,weights=prices_b,capacity=valA)
    return '{}'.format(valB)

print(sol())

Submission status: Time Limit Exceeded

Solution code:

# 個数制限なしナップサック問題を2回やる？

"""前半の交換：
重さはga, sa, ba 合計がN以下
価値がgb, sb, bb これを最大化
"""
n = int(input())
a_rate =list(map(int, input().split() ))
b_rate =list(map(int, input().split() ))
a_rate.append(1)
b_rate.append(1)

dp1 = [[0 for j in range(n+1)] for i in range(5)]

for i in range(4):
	for j in range(n+1):
		if j < a_rate[i]:
			dp1[i + 1][j] = dp1[i][j]
		else:
			dp1[i + 1][j] = max(dp1[i][j], dp1[i + 1][j - a_rate[i]] + b_rate[i])

mid_donguri = dp1[4][n]

dp2 = [[0 for j in range(mid_donguri+1)] for i in range(5)]

"""前半の交換：
重さはgb, sb, bb 合計がN以下
価値がga, sa, ba これを最大化
"""

for i in range(4):
	for j in range(mid_donguri+1):
		if j < b_rate[i]:
			dp2[i + 1][j] = dp2[i][j]
		else:
			dp2[i + 1][j] = max(dp2[i][j], dp2[i + 1][j - b_rate[i]] + a_rate[i])

print(dp2[4][mid_donguri])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
gA, sA, bA = map(int, input().split())
gB, sB, bB = map(int, input().split())

dp = [[0] * (N+1) for _ in range(4)]
#[重さ,価値]を要素とする配列
lstAB = [[gA, gB-gA], [sA, sB-sA], [bA, bB-bA]]
lstBA = [[gB, gA-gB], [sB, sA-sB], [bB, bA-bB]]
for i in range(3):
    for j in range(N+1):
        if j < lstAB[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-lstAB[i][0]]+lstAB[i][1])

N += dp[3][N]
# print (N)

dp2 = [[0] * (N+1) for _ in range(4)]
for i in range(3):
    for j in range(N+1):
        if j < lstBA[i][0]:
            dp2[i+1][j] = dp2[i][j]
        else:
            dp2[i+1][j] = max(dp2[i][j], dp2[i+1][j-lstBA[i][0]]+lstBA[i][1])
print (N + dp2[3][N])

Submission status: Time Limit Exceeded

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

wa = [1, ga, sa, ba]
wb = [1, gb, sb, bb]

dp = [0] * (n+1)
for i in range(1, n+1):
  d = []
  for ai in range(4):
    w1 = wa[ai]
    w2 = wb[ai]
    if i-w1 <0:
      continue
    d.append(dp[i-w1] + w2)
  dp[i] = max(d)


nn = dp[-1]
dp = [0] * (nn+1)
for i in range(1, nn+1):
  d = []
  for ai in range(4):
    w1 = wb[ai]
    w2 = wa[ai]
    if i-w1 <0:
      continue
    d.append(dp[i-w1] + w2)
  dp[i] = max(d)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
gA, sA, bA = map(int, input().split())
gB, sB, bB = map(int, input().split())

dp = [[0] * (2 * N+ 2) for _ in range(2 * N + 2)]
#[重さ,価値]を要素とする配列
lstAB = [[gA, gB-gA], [sA, sB-sA], [bA, bB-bA]]
lstBA = [[gB, gA-gB], [sB, sA-sB], [bB, bA-bB]]
for i in range(3):
    for j in range(N+1):
        if j < lstAB[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-lstAB[i][0]]+lstAB[i][1])

N += dp[3][N]
# print (N)

dp2 = [[0] * (2 * N+ 2) for _ in range(2 * N + 2)]
for i in range(3):
    for j in range(N+1):
        if j < lstBA[i][0]:
            dp2[i+1][j] = dp2[i][j]
        else:
            dp2[i+1][j] = max(dp2[i][j], dp2[i+1][j-lstBA[i][0]]+lstBA[i][1])
print (N + dp2[3][N])

Submission status: Time Limit Exceeded

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

def trade(n, rate):
    dp = [0]
    for i in range(n):
        v = dp[i] + 1
        for ra, rb in rate:
            if i + 1 >= ra:
                v = max(v, dp[i + 1 - ra] + rb)
        dp.append(v)
    return dp[-1]

n = trade(n, [(ga, gb), (sa, sb), (ba, bb)])
n = trade(n, [(gb, ga), (sb, sa), (bb, ba)])
print(n)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))

    num = 0
    ab = []
    ba = []
    for i in range(3):
        if a[i]-b[i] < 0:
            ab.append([a[i],b[i]])  
        elif a[i]-b[i] > 0:
            ba.append([a[i],b[i]])

    dp = [i for i in range(n+1)]
    if len(ab) > 0:
        for i in range(n+1):
            for x,y in ab:
                if i >= x:
                    dp[i] = max(dp[i],dp[i-x]+y)
    p = max(n,dp[n])

    dp2 = [i for i in range(p+1)]
    if len(ba) > 0:
        for i in range(p+1):
            for y,x in ba:
                if i >= x:
                    dp2[i] = max(dp2[i],dp2[i-x]+y)
    print(dp2[-1])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def inverse(a):
    return pow(a, mod - 2, mod)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    n = maxi(n, a, b)
    n = maxi(n, b, a)
    print(n)


def maxi(n, a, b):
    ans = 0
    for g in range(n//a[0]+1):
        d = n - g * a[0]
        if d < 0:
            continue
        for s in range(d//a[1]+1):
            d = n - g * a[0] - s * a[1]
            if d < 0:
                continue
            for br in [0, d//a[2]]:
                ans = max([ans, n - g * a[0] - s * a[1] - br * a[2] + g * b[0] + s * b[1] + br * b[2]])
    return ans


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def lsearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] < x:
            lft = mid
        else:
            rgt = mid
    return lft


main()

Submission status: Time Limit Exceeded

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

w_ab = []
v_ab = []

if ga < gb:
    w_ab.append(ga)
    v_ab.append(gb)
if sa < sb:
    w_ab.append(sa)
    v_ab.append(sb)
if ba < bb:
    w_ab.append(ba)
    v_ab.append(bb)

dp = [[0]*(n+1) for i in range(len(w_ab)+1)]
for i in range(len(w_ab)):
    for j in range(n+1):
        if j < w_ab[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j - w_ab[i]] + v_ab[i])
ans = 0
for i in range(n+1):
    ans = max(ans, dp[len(w_ab)][i] + n-i)
n = ans

w_ab = []
v_ab = []

if ga > gb:
    w_ab.append(gb)
    v_ab.append(ga)
if sa > sb:
    w_ab.append(sb)
    v_ab.append(sa)
if ba > bb:
    w_ab.append(bb)
    v_ab.append(ba)

dp = [[0]*(n+1) for i in range(len(w_ab)+1)]
for i in range(len(w_ab)):
    for j in range(n+1):
        if j < w_ab[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j - w_ab[i]] + v_ab[i])
ans = 0
for i in range(n+1):
    ans = max(ans, dp[len(w_ab)][i] + n-i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
fir = []
sec = []
ans = n
ansf = n
for i in range(3):
  if a[i]>b[i]:
    sec.append((a[i],b[i]))
    fir.append((n,n))
  else:
    sec.append((n,n))
    fir.append((b[i],a[i]))
for p in range(n//fir[0][1]+1):
  for q in range((n-p*fir[0][1])//fir[1][1]+1):
    rg = n - p*fir[0][1] - q*fir[1][1]
    if rg < 0:
      continue
    res = rg%fir[2][1]
    r = rg//fir[2][1]
    en = p*fir[0][0] + q*fir[1][0] + r*fir[2][0] + res
    if ansf < en:
      ansf = en
for p in range(ansf//sec[0][1]+1):
  for q in range((ansf-p*sec[0][1])//sec[1][1]+1):
    rg = ansf - p*sec[0][1] - q*sec[1][1]
    if rg < 0:
      continue
    res = rg%sec[2][1]
    r = rg//sec[2][1]
    en = p*sec[0][0] + q*sec[1][0] + r*sec[2][0] + res
    if ans < en:
      ans = en
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_array = map(int, input().split())
B_array = map(int, input().split())

AB_use = []
BA_use = []
for a, b in zip(A_array, B_array):

    if a > b:
        BA_use.append((b, a))

    elif b > a:
        AB_use.append((a, b))

ans = N

if len(AB_use):
    ans_array = [0] * (ans + 1)
    for i in range(1, ans + 1):
        ans_max = ans_array[i - 1] + 1
        for j in AB_use:
            w, v = j
            if w <= i:
                ans_max = max(ans_max, ans_array[i - w] + v)
        ans_array[i] = ans_max
    # print(ans_array)
    ans = ans_array[ans]


if len(BA_use):
    ans_array = [0] * (ans + 1)
    for i in range(1, ans + 1):
        ans_max = ans_array[i - 1] + 1
        for j in BA_use:
            w, v = j
            if w <= i:
                ans_max = max(ans_max, ans_array[i - w] + v)
        ans_array[i] = ans_max
    ans = ans_array[ans]
    # print(ans_array)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations as pp
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
fir = []
sec = []
ans = n
ansf = n
for i in range(3):
  if a[i]>b[i]:
    sec.append((a[i],b[i]))
    fir.append((n,n))
  else:
    sec.append((n,n))
    fir.append((b[i],a[i]))
for p in range(n//fir[0][1]+1):
  for q in range((n-p*fir[0][1])//fir[1][1]+1):
    rg = n - p*fir[0][1] - q*fir[1][1]
    if rg < 0:
      continue
    res = rg%fir[2][1]
    r = rg//fir[2][1]
    en = p*fir[0][0] + q*fir[1][0] + r*fir[2][0] + res
    if ansf < en:
      ansf = en
for p in range(ansf//sec[0][1]+1):
  for q in range((ansf-p*sec[0][1])//sec[1][1]+1):
    rg = ansf - p*sec[0][1] - q*sec[1][1]
    if rg < 0:
      continue
    res = rg%sec[2][1]
    r = rg//sec[2][1]
    en = p*sec[0][0] + q*sec[1][0] + r*sec[2][0] + res
    if ans < en:
      ans = en
print(ans)

Submission status: Time Limit Exceeded

Solution code:
rr = raw_input
rrm = lambda: map(int, rr().split())

def knap(N, A, B):
    dp = [0]
    for x in xrange(1, N+1):
        dp.append(x)
        for i in xrange(3):
            if x >= A[i]:
                dp[x] = max(dp[x], dp[x-A[i]] + B[i])
    return dp[-1]

def solve(N, A, B):
    N2 = knap(N, A, B)
    N3 = knap(N2, B, A)
    return N3
                
N = int(rr())
A = rrm()
B = rrm()
print solve(N, A, B)

Submission status: Time Limit Exceeded

Solution code:
def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    n = int(input())
    [ga, sa, ba] = li()
    [gb, sb, bb] = li()

    dp = [0] * (n + 1)
    # A->Bでのトレード成果
    for i in range(1, n + 1):
        g_trade = dp[i - ga] + gb if i - ga >= 0 else dp[i - 1]
        s_trade = dp[i - sa] + sb if i - sa >= 0 else dp[i - 1]
        b_trade = dp[i - ba] + bb if i - ba >= 0 else dp[i - 1]
        dp[i] = max(dp[i - 1] + 1, g_trade, s_trade, b_trade)
    a_result = dp[-1]

    # B->Aでのトレード成果
    dp = [0] * (a_result + 1)
    # A->Bでのトレード成果
    for i in range(1, a_result + 1):
        g_trade = dp[i - gb] + ga if i - gb >= 0 else dp[i - 1]
        s_trade = dp[i - sb] + sa if i - sb >= 0 else dp[i - 1]
        b_trade = dp[i - bb] + ba if i - bb >= 0 else dp[i - 1]
        dp[i] = max(dp[i - 1] + 1, g_trade, s_trade, b_trade)
    print(dp[-1])

# n+1個のドングリを取引にかけたときに得られるドングリポテンシャルは
# n個までの最適+1, n-gA個までの最適+gB, n-sA個までの最適+sB, n-bA個までの最適+bBで一番大きくなる値

# AでBより安く金属を手に入れる
# Bでドングリに戻して、Aより安く金属を手に入れる
# Aでドングリに戻して帰る

Submission status: Time Limit Exceeded

Solution code:
rr = raw_input
rrm = lambda: map(int, rr().split())

def solve2(N, A, B):
    dp = [0]
    for x in xrange(1, N+1):
        dp.append(x)
        for i in xrange(3):
            if x >= A[i]:
                dp[x] = max(dp[x], dp[x-A[i]] + B[i])
    return dp[-1]

def solve(N, A, B):
    if cmp(A[0], B[0]) != cmp(A[1], B[1]):
        A[1],A[2] = A[2],A[1]
        B[1],B[2] = B[2],B[1]

    if A[0]>=B[0] and A[1]>=B[1] and A[2]>=B[2]:
        return solve2(N, B, A)
    if A[0]<=B[0] and A[1]<=B[1] and A[2]<=B[2]:
        return solve2(N, A, B)
    
    def exch1(N, A, B):
        # Have N, at A, going to B
        # what is most acorns can get at B?
        ans = N
        for g in xrange(N+1 if B[0]>=A[0] else 1):
            if g * A[0] > N: break
            for s in xrange(N+1 if B[1]>=A[1] else 1):
                cost = g*A[0] + s*A[1]
                if cost > N: break
                bns = N + g*(B[0] - A[0]) + s*(B[1] - A[1])
                if bns > ans: ans = bns
                b = (N-cost) / A[2]
                bns = N + g*(B[0] - A[0]) + s*(B[1] - A[1]) + b*(B[2] - A[2])
                if bns > ans: ans = bns
        return ans
    N2 = exch1(N, A, B)
    N3 = exch1(N2, B, A)
    return N3
                
N = int(rr())
A = rrm()
B = rrm()
print solve(N, A, B)