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: Wrong Answer

Solution code:
N = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

cur = N
dp = list(range(cur + 1))
for i in range(cur + 1):
    if i >= As[0]:
        if dp[i] < dp[i - As[0]] + Bs[0]:
            dp[i] = dp[i - As[0]] + Bs[0]
    if i >= As[1]:
        if dp[i] < dp[i - As[1]] + Bs[1]:
            dp[i] = dp[i - As[1]] + Bs[1]
    if i >= As[2]:
        if dp[i] < dp[i - As[2]] + Bs[2]:
            dp[i] = dp[i - As[2]] + Bs[2]

print(dp)

cur = dp[cur]
dp = list(range(cur + 1))
As, Bs = Bs, As
for i in range(cur + 1):
    if i >= As[0]:
        if dp[i] < dp[i - As[0]] + Bs[0]:
            dp[i] = dp[i - As[0]] + Bs[0]
    if i >= As[1]:
        if dp[i] < dp[i - As[1]] + Bs[1]:
            dp[i] = dp[i - As[1]] + Bs[1]
    if i >= As[2]:
        if dp[i] < dp[i - As[2]] + Bs[2]:
            dp[i] = dp[i - As[2]] + Bs[2]

print(dp)


print(dp[cur])

Submission status: Wrong Answer

Solution code:
n = int(input())
gsb_a = list(map(int, input().split()))
gsb_b = list(map(int, input().split()))

ans=n

# A->B
for i in range(3):
    now_d = n
    now_z = now_d // gsb_a[i]
    now_d %= gsb_a[i]
    now_d += now_z * gsb_b[i]
    ans=max(ans,now_d)

# B->A
for i in range(3):
    now_d = n
    now_z = now_d // gsb_b[i]
    now_d %= gsb_b[i]
    now_d += now_z * gsb_a[i]
    ans=max(ans,now_d)

# A->B->A
for i in range(3):
    for j in range(3):
        #@A
        now_d=n
        now_z = now_d // gsb_a[i]
        now_d %= gsb_a[i]

        #@B
        now_d += now_z*gsb_b[i]
        now_z = now_d // gsb_b[j]
        now_d %= gsb_b[j]

        #@A
        now_d += now_z * gsb_a[j]
        ans=max(ans,now_d)

print(ans)

Submission status: Wrong Answer

Solution code:
def main(n,A,B):
  g,s,b=0,0,0
  rate=[]
  AB=[[a,b] for a,b in zip(A,B)]
  dp=[0]*(n+1)
  dp[0]=n
  # dp[i]:どんぐりをi個交換した時の最大獲得どんぐり
  for a,b in AB:
    if a>b:continue
    i=0
    ddp=[0]*(n+1)
    ddp[0]=n
    for i in range(a,n+1):
      ddp[i]=max(dp[i],ddp[i-a]+b-a)
    dp=ddp
  n=max(dp)
  dp=[0]*(n+1)
  dp[0]=n
  for a,b in AB:
    if b>a:continue
    i=0
    ddp=[0]*(n+1)
    ddp[0]=n
    for i in range(b,n+1):
      ddp[i]=max(dp[i],ddp[i-b]+a-b)
    dp=ddp
  return max(dp)

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

Submission status: Wrong Answer

Solution code:
def main(n,A,B):
  g,s,b=0,0,0
  rate=[]
  for i,[a,b] in enumerate(zip(A,B)):
    rate.append([i,[b/a],[a/b]])
  rate.sort(key=lambda x:x[1],reverse=True)
  nn=0
  for i,r,_ in rate:
    nn+=(n//A[i])*B[i]
    n%=A[i]
  rate.sort(key=lambda x:x[2],reverse=True)
  nnn=0
  for i,_,r in rate:
    nnn+=(nn//B[i])*A[i]
    nn%=B[i]
  return nnn

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
ga,sa,ba = map(int,input().split())
gb,sb,bb = map(int,input().split())

gc,gd = min(ga,gb), max(ga,gb)
sc,sd = min(sa,sb), max(sa,sb)
bc,bd = min(ba,bb), max(ba,bb)

dp = [0] * (N+1)
ans = N
for i in range(1,N+1):
    if gc <= i:
        dp[i] = max(dp[i], dp[i-gc] + gd)
    if sc <= i:
        dp[i] = max(dp[i], dp[i-sc] + sd)
    if bc <= i:
        dp[i] = max(dp[i], dp[i-bc] + bd)
    ans = max(ans, N-i+dp[i])

print(ans)

Submission status: Wrong Answer

Solution code:
def F(N, A, B):
  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()]
 
answer1 = F(N,B,A)
answer2 = F(N,A,B)

print(max(answer1, answer2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from itertools import permutations

def main():
    N = int(input())
    gsba = list(map(int, input().split()))
    gsbb = list(map(int, input().split()))
    ans = 0

    # 買えるだけ買う作戦 3!通り * 3!通り
    # そもそも買わないか買うかで2^3通り
    for a in range(2**3):
        for p in permutations(range(3),3):
            xyz = [0,0,0]
            donguri = N
            for i in p:
                if a >> i & 1:
                    xyz[i] = donguri // gsba[i]
                    donguri %= gsba[i]

            for i in range(3):
                donguri += xyz[i] * gsbb[i]

            for b in range(2**3):
                for q in permutations(range(3),3):
                    res = donguri
                    stu = [0,0,0]
                    for j in q:
                        if b >> j & 1:
                            stu[j] = res // gsbb[j]
                            res %= gsbb[j]

                    for j in range(3):
                        res += stu[j] * gsba[j]

                    ans = max(ans, res)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from itertools import permutations

def main():
    N = int(input())
    gsba = list(map(int, input().split()))
    gsbb = list(map(int, input().split()))
    ans = 0

    # 買えるだけ買う作戦 3!通り * 3!通り
    for p in permutations(range(3),3):
        # print(p)
        xyz = [0,0,0]
        donguri = N
        for i in p:
            xyz[i] = donguri // gsba[i]
            donguri %= gsba[i]

        # GSBを取引所Bでどんぐりにする
        for i in range(3):
            donguri += xyz[i] * gsbb[i]

        # print(p,xyz,donguri)

        for q in permutations(range(3),3):
            res = donguri
            stu = [0,0,0]
            for j in q:
                stu[j] = res // gsbb[j]
                res %= gsbb[j]

            # GSBを取引所Aでどんぐりにする
            for j in range(3):
                res += stu[j] * gsba[j]

            ans = max(ans, res)
            # print('-',q,stu,donguri)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = [];D = []
for i in range(3):
  temp = A[i]/B[i]
  C.append(temp)
  temp = B[i]/A[i]
  D.append(temp) 
X = [];Y = []
for i in range(3):
  temp = [A[i],B[i],C[i]]
  X.append(temp)
  temp = [B[i],A[i],D[i]]
  Y.append(temp)
X.sort(key=lambda x:x[2])
Y.sort(key=lambda x:x[2])
#print(X,Y)

def exchange(N,Z):
  ret = N
  max0 = N//Z[0][0]
  #print(max0)
  if Z[0][2] >= 1:
    return ret
  for i in range(max0+1):
    temp0 = i*Z[0][1]
    nokori0 = N-i*Z[0][0]
    max1 = nokori0//Z[1][0]
    #print(temp0,nokori0,max1)
    if Z[1][2] >= 1:
      ret = max(ret,temp0+nokori0)
      continue
    for j in range(max1+1):
      temp1 = j*Z[1][1]
      nokori1 = nokori0 - j*Z[1][0]
      max2 = nokori1//Z[2][0]
      if Z[2][2] >= 1:
        ret = max(ret,temp0+temp1+nokori1)
        continue
      for k in range(max2+1):
        temp2 = k*Z[2][1]
        nokori2 = nokori1 - j*Z[2][0]
        ret = max(ret,temp0+temp1+temp2+nokori2)
  return ret
mid = exchange(N,X)
#print(mid)
ans = exchange(mid,Y)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

ans = N
for perm1 in permutations(range(3), 3):
    for perm2 in permutations(range(3), 3):
        for i in range(8):
            for j in range(8):
                donguri = N
                cnt = [0, 0, 0]
                for k in perm1:
                    if i & (1 << k):
                        cnt[k] += donguri // As[k]
                        donguri %= As[k]
                for k in range(3):
                    donguri += cnt[k] * Bs[k]
                    cnt[k] = 0
                for k in perm2:
                    if j & (1 << k):
                        cnt[k] += donguri // Bs[k]
                        donguri %= Bs[k]
                for k in range(3):
                    donguri += cnt[k] * As[k]
                    cnt[k] = 0
                ans = max(ans, donguri)
                
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

ans = N
for perm1 in permutations(range(3), 3):
    for perm2 in permutations(range(3), 3):
        for i in range(8):
            for j in range(8):
                donguri = N
                cnt = [0, 0, 0]
                for k in perm1:
                    if i & (1 << k):
                        cnt[k] += donguri // As[k]
                        donguri %= As[k]
                for k in perm1:
                    if i & (1 << k):
                        donguri += cnt[k] * Bs[k]
                        cnt[k] = 0
                for k in perm2:
                    if j & (1 << k):
                        cnt[k] += donguri // Bs[k]
                        donguri %= Bs[k]
                for k in perm2:
                    if j & (1 << k):
                        donguri += cnt[k] * As[k]
                        cnt[k] = 0
                ans = max(ans, donguri)
                
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N = int(input())
As_ = list(map(int, input().split()))
Bs_ = list(map(int, input().split()))

ans = N
for perm1 in permutations(range(3), 3):
    As = [0] * 3
    Bs = [0] * 3
    for p, q in enumerate(perm1):
        As[p] = As_[q]
        Bs[p] = Bs_[q]
    for perm2 in permutations(range(3), 3):
        for i in range(8):
            for j in range(8):
                donguri = N
                cnt = [0, 0, 0]
                for k in range(3):
                    if i & (1 << k):
                        cnt[k] += donguri // As[k]
                        donguri %= As[k]
                for k in range(3):
                    if i & (1 << k):
                        donguri += cnt[k] * Bs[k]
                        cnt[k] = 0
                As_2 = [0, 0, 0]
                Bs_2 = [0, 0, 0]
                cnt_2 = [0, 0, 0]
                for p, q in enumerate(perm2):
                    As_2[p] = As[q]
                    Bs_2[p] = Bs[q]
                    cnt_2[p] = cnt[q]
                for k in range(3):
                    if j & (1 << k):
                        cnt_2[k] += donguri // Bs_2[k]
                        donguri %= Bs_2[k]
                for k in range(3):
                    if j & (1 << k):
                        donguri += cnt_2[k] * As_2[k]
                        cnt_2[k] = 0
                ans = max(ans, donguri)
                
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N = int(input())
As_ = list(map(int, input().split()))
Bs_ = list(map(int, input().split()))

ans = N
for perm1 in permutations(range(3), 3):
    As = [0] * 3
    Bs = [0] * 3
    for p, q in enumerate(perm1):
        As[p] = As_[q]
        Bs[p] = Bs_[q]
    for perm2 in permutations(range(3), 3):
        for i in range(8):
            for j in range(8):
                donguri = N
                cnt = [0, 0, 0]
                for k in range(3):
                    if i & (1 << k):
                        cnt[k] += donguri // As[k]
                        donguri %= As[k]
                for k in range(3):
                    if i & (1 << k):
                        donguri += cnt[k] * Bs[k]
                        cnt[k] = 0
                As_2 = [0, 0, 0]
                Bs_2 = [0, 0, 0]
                cnt_2 = [0, 0, 0]
                for p, q in enumerate(perm2):
                    As_2[p] = As[q]
                    Bs_2[p] = Bs[q]
                    cnt_2[p] = cnt[q]
                As = As_2
                Bs = Bs_2
                cnt = cnt_2
                for k in range(3):
                    if j & (1 << k):
                        cnt[k] += donguri // Bs[k]
                        donguri %= Bs[k]
                for k in range(3):
                    if j & (1 << k):
                        donguri += cnt[k] * As[k]
                        cnt[k] = 0
                ans = max(ans, donguri)
                
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N = int(input())
As_ = list(map(int, input().split()))
Bs_ = list(map(int, input().split()))

ans = N
for perm1 in permutations(range(3), 3):
    As = [0] * 3
    Bs = [0] * 3
    for p, q in enumerate(perm1):
        As[p] = As_[q]
        Bs[p] = Bs_[q]
    for perm2 in permutations(range(3), 3):
        for i in range(8):
            for j in range(8):
                donguri = N
                cnt = [0, 0, 0]
                for k in range(3):
                    if i & (1 << k):
                        cnt[k] += donguri // As[k]
                        donguri %= As[k]
                for k in range(3):
                    if i & (1 << k):
                        donguri += cnt[k] * Bs[k]
                        cnt[k] = 0
                As_2 = [0, 0, 0]
                Bs_2 = [0, 0, 0]
                for p, q in enumerate(perm2):
                    As_2[p] = As[q]
                    Bs_2[p] = Bs[q]
                As = As_2
                Bs = Bs_2
                for k in range(3):
                    if j & (1 << k):
                        cnt[k] += donguri // Bs[k]
                        donguri %= Bs[k]
                for k in range(3):
                    if j & (1 << k):
                        donguri += cnt[k] * As[k]
                        cnt[k] = 0
                ans = max(ans, donguri)
                
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N = int(input())
As_ = list(map(int, input().split()))
Bs_ = list(map(int, input().split()))

ans = N
for perm in permutations(range(3), 3):
    As = [0] * 3
    Bs = [0] * 3
    for p, q in enumerate(perm):
        As[p] = As_[q]
        Bs[p] = Bs_[q]
    for i in range(8):
        for j in range(8):
            donguri = N
            cnt = [0, 0, 0]
            for k in range(3):
                if i & (1 << k):
                    cnt[k] += donguri // As[k]
                    donguri %= As[k]
            for k in range(3):
                if i & (1 << k):
                    donguri += cnt[k] * Bs[k]
                    cnt[k] = 0
            for k in range(3):
                if j & (1 << k):
                    cnt[k] += donguri // Bs[k]
                    donguri %= Bs[k]
            for k in range(3):
                if j & (1 << k):
                    donguri += cnt[k] * As[k]
                    cnt[k] = 0
            ans = max(ans, donguri)
            
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N = int(input())
As_ = list(map(int, input().split()))
Bs_ = list(map(int, input().split()))

ans = N
for perm in permutations(range(3), 3):
    As = [0] * 3
    Bs = [0] * 3
    for p, q in enumerate(perm):
        As[p] = As_[q]
        Bs[p] = Bs_[q]
    for i in range(8):
        for j in range(8):
            donguri = N
            cnt = [0, 0, 0]
            for k in range(3):
                if i & (1 << k):
                    cnt[k] = donguri // As[k]
                    donguri %= As[k]
            for k in range(3):
                if i & (1 << k):
                    donguri += cnt[k] * Bs[k]
                    cnt[k] = 0
            for k in range(3):
                if j & (1 << k):
                    cnt[k] = donguri // Bs[k]
                    donguri %= Bs[k]
            for k in range(3):
                if j & (1 << k):
                    donguri += cnt[k] * As[k]
                    cnt[k] = 0
            ans = max(ans, donguri)
            
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N = int(input())
As_ = list(map(int, input().split()))
Bs_ = list(map(int, input().split()))

ans = N
for perm in permutations(range(3), 3):
    As = [0] * 3
    Bs = [0] * 3
    for p, q in enumerate(perm):
        As[p] = As_[q]
        Bs[p] = Bs_[q]
    for i in range(8):
        for j in range(8):
            donguri = N
            cnt = [0, 0, 0]
            for k in range(3):
                if i & (1 << k):
                    cnt[k] = donguri // As[k]
                    donguri %= As[k]
            for k in range(3):
                if i & (1 << k):
                    donguri += cnt[k] * Bs[k]
                    cnt[k] = 0
            for k in range(3):
                if j & (1 << k):
                    cnt[k] = donguri // Bs[k]
                    donguri %= As[k]
            for k in range(3):
                if j & (1 << k):
                    donguri += cnt[k] * As[k]
                    cnt[k] = 0
            ans = max(ans, donguri)
            
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
gsb=[list(map(int,input().split())) for _ in range(2)]
gsb+=[gsb[0]]
dp=[0]*4
dp[0]=n
for i in range(1,4):
    gi,si,bi=gsb[i-1]
    for j in range(i):
        gj,sj,bj=gsb[j]
        dp[i]=max(dp[i],dp[j]%min(gsb[j])+dp[j]//min(gsb[j])*max(gsb[i-1]))
    dp[i]=max(dp[i],dp[i-1])
print(dp[3])

Submission status: Wrong Answer

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

n = int(input())
a1, a2, a3 = map(int, input().split())
b1, b2, b3 = map(int, input().split())
def f(n, a1, a2, a3, b1, b2, b3):
  dp = [0]*(n+1)
  for i in range(n+1):
    for a, b in zip((a1, a2, a3), (b1, b2, b3)):
      if i-a >= 0:
        dp[i] = max(dp[i], dp[i-a]+b)
  return max(dp)
m = f(n, a1, a2, a3, b1, b2, b3)
ans = f(m, b1, b2, b3, a1, a2, a3)
print(ans)

Submission status: Wrong Answer

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

n = int(input())
a1, a2, a3 = map(int, input().split())
b1, b2, b3 = map(int, input().split())
def f(n, a1, a2, a3, b1, b2, b3):
  dp = [0]*(n+1)
  for i in range(n):
    for a, b in zip((a1, a2, a3), (b1, b2, b3)):
      if i+a <= n:
        dp[i+a] = max(dp[i+a], dp[i]+b)
  return max(dp)
m = f(n, a1, a2, a3, b1, b2, b3)
ans = f(m, b1, b2, b3, a1, a2, a3)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    ga,sa,ba = map(int,ipt().split())
    gb,sb,bb = map(int,ipt().split())

    dp = [0]*(5005)
    for i in range(n+1):
        dp[i] = dp[i-1]
        if i >= ga and dp[i] < (gb-ga)+dp[i-ga]:
            dp[i] = gb-ga+dp[i-ga]
        if i >= sa and dp[i] < (sb-sa)+dp[i-sa]:
            dp[i] = sb-sa+dp[i-sa]
        if i >= ba and dp[i] < (bb-ba)+dp[i-ba]:
            dp[i] = bb-ba+dp[i-ba]
    ni = n+dp[n]
    dp = [0]*max(5005,ni+5)
    for i in range(ni+1):
        dp[i] = dp[i-1]
        if i >= gb and dp[i] < (ga-gb)+dp[i-gb]:
            dp[i] = ga-gb+dp[i-gb]
        if i >= sb and dp[i] < (sa-sb)+dp[i-sb]:
            dp[i] = sa-sb+dp[i-sb]
        if i >= bb and dp[i] < (bb-ba)+dp[i-bb]:
            dp[i] = ba-bb+dp[i-bb]
    print(ni+dp[ni])



    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=LI()
    B=LI()
    
    dp=[0]*(N+1)
    #i番目まで見てj個使って何個になるか
    

        
    for i in range(3):
        for j in range(A[i],N+1,A[i]):
            dp[j]=max(dp[j-A[i]]+B[i],dp[j])
        #print(dp)
            
    N2=N#A=>Bでどこまで増えたか
    for j in range(N+1):
        temp=dp[j]
        N2=max(N2,temp)

        
    #B=>A
    dp2=[0]*(N2+1)
    for i in range(3):
        for j in range(B[i],N2+1,B[i]):
            dp2[j]=max(dp2[j-B[i]]+A[i],dp2[j])#価値が逆転
            
    ans=N2
    for j in range(N2+1):
        temp=dp2[j]
        ans=max(ans,temp)
        
    print(ans)
            
        
                           
                    
        
    
    
    
    
    ans=0
    

      
            
            

main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=LI()
    B=LI()
    
    dp=[0]*(N+1)
    #i番目まで見てj個使って何個増やせたか
    
    v=[]
    for i in range(3):
        vv=B[i]-A[i]#差分だけ増える
        v.append(vv)
        
    for i in range(3):
        for j in range(A[i],N+1,A[i]):
            dp[j]=max(dp[j-A[i]]+v[i],dp[j])
        #print(dp)
            
    N2=N#A=>Bでどこまで増えたか
    for j in range(N+1):
        temp=N+dp[j]
        N2=max(N2,temp)

        
    #B=>A
    dp2=[0]*(N2+1)
    for i in range(3):
        for j in range(B[i],N2+1,B[i]):
            dp2[j]=max(dp2[j-B[i]]-v[i],dp2[j])#価値が逆転
            
    ans=N2
    for j in range(N2+1):
        temp=N2+dp2[j]
        ans=max(ans,temp)
        
    print(ans)
            
        
                           
                    
        
    
    
    
    
    ans=0
    

      
            
            

main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    ga,sa,ba=MI()
    gb,sb,bb=MI()
    
    ans=0
    
    #A=>Bではなくて，ABAです．レートが小さい方で換金して，レートが大きい方で換ドングリ
    #ga>gbならABの順で，ga<gbならBA
    #違うわ，Aで金にして，Bでドングリにした後，銀にして，Aで再換金のパターンがあるので2回計算する．
        
    
    for i in range(0,N+1,ga):#i個を金にする
        for j in range(0,N-i+1,sb):#j個を銀にする．
            rem=N-i-j
            g=(i//ga)*gb
            s=(j//sa)*sb
            b=(rem//ba)*bb + rem%ba#余ったものは可能な限り銅にする（あまり分も意識して） or 何もしない．なんだけど，この時に
            temp=max(g+s+rem,g+s+b)
            ans=max(temp,ans)
            

    ga,gb=gb,ga
    sa,sb=sb,sa
    ba,bb=bb,ba
    
    N=ans        
    for i in range(0,N+1,ga):#i個を金にする
        for j in range(0,N-i+1,sb):#j個を銀にする．
            rem=N-i-j
            g=(i//ga)*gb
            s=(j//sa)*sb
            b=(rem//ba)*bb + rem%ba#余ったものは可能な限り銅にする（あまり分も意識して） or 何もしない．なんだけど，この時に
            temp=max(g+s+rem,g+s+b)
            ans=max(temp,ans)
            
    print(ans)
            
            

main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    ga,sa,ba=MI()
    gb,sb,bb=MI()
    
    ans=0
    
    #A=>Bではなくて，ABAです
    #ga>gbならABの順で，ga<gbならBA
    
    if gb<ga:
        ga,gb=gb,ga
    
    if sb<sa:
        sa,sb=sb,sa
    
    if bb<ba:
        ba,bb=bb,ba
        
    
    for i in range(0,N+1,ga):#i個を金にする
        for j in range(0,N-i+1,sb):#j個を銀にする．
            rem=N-i-j
            g=(i//ga)*gb
            s=(j//sa)*sb
            b=(rem//ba)*bb + rem%ba#余ったものは可能な限り銅にする（あまり分も意識して） or 何もしない．なんだけど，この時に
            temp=max(g+s+rem,g+s+b)
            ans=max(temp,ans)
            
    print(ans)
            
            

main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    ga,sa,ba=MI()
    gb,sb,bb=MI()
    
    ans=0
    for i in range(0,N+1,ga):#i個を金にする
        for j in range(0,N-i+1,sb):#j個を銀にする．
            rem=N-i-j
            g=(i//ga)*gb
            s=(j//sa)*sb
            b=(rem//ba)*bb + rem%ba
            temp=max(g+s+rem,g+s+b)
            ans=max(temp,ans)
            
    print(ans)
            
            

main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    ga,sa,ba=MI()
    gb,sb,bb=MI()
    
    ans=0
    for i in range(0,N+1,ga):#i個を金にする
        for j in range(0,N-i+1,sb):#j個を銀にする．
            rem=N-i-j
            g=(i//ga)*gb
            s=(j//sa)*sb
            b=(rem//ba)*bb
            temp=max(g+s+rem,g+s+b)
            ans=max(temp,ans)
            
    print(ans)
            
            

main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""
dp, 取引所Bで一度全てacornにする
取引所Aでの通貨の値段を重さとする
"""

N = ir()
A = lr()
B = lr()
dp = [x for x in range(N+1)]
for a, b in zip(A, B):
    for x in range(N):
        if x + a <= N:
            dp[x+a] = max(dp[x+a], dp[x] + b)

half_way = max(dp)
dp = [x for x in range(half_way+1)]
A, B = B, A
for a, b in zip(A, B):
    for x in range(N):
        if x + a <= N:
            dp[x+a] = max(dp[x+a], dp[x] + b)

answer = max(dp)
print(answer)

# 56

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""
dp, 取引所Bで一度全てacornにする
取引所Aでの通貨の値段を重さとする
"""

N = ir()
A = lr()
B = lr()
dp = [x for x in range(N+1)]
for a, b in zip(A, B):
    for x in range(N):
        if x + a <= N:
            dp[x+a] = max(dp[x+a], dp[x] + b)

half_way = max(dp)
dp = [x for x in range(half_way+1)]
A, B = B, A
for a, b in zip(A, B):
    for x in range(N):
        if x + a <= N:
            dp[x+a] = max(dp[x+a], dp[x] + b)

answer = max(dp)
print(answer)

# 56

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from itertools import permutations

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""
逆から、各取引所で金銀銅を経てドングリにすることも可能
dp、一回だけ二回だけの場合を考える
gb - ga の値でsort
全探索
"""

origin_poss = [0, 0, 0, 0]  # gold...acorn
origin_poss[3] = ir()

A = lr()
B = lr()
greater_A = []
greater_B = []
AB = [(a, b) for a, b in zip(A, B)]
cand = [0, 1, 2]
change = [[]] + [[x] for x in range(3)] + [[a, b] for a, b in permutations(cand, 2)] \
        + [[a, b, c] for a, b, c in permutations(cand, 3)]
answer = 0
for X in change:
    poss_first = origin_poss[:]
    for x in X:
        y = A[x]
        z = poss_first[3] // y
        poss_first[x] += z
        poss_first[3] -= z
    # 取引所Bでドングリへ
    for Y in change:
        poss_second = poss_first[:]
        for x in Y:
            y = B[x]
            z = poss_second[x] * y
            poss_second[x] = 0
            poss_second[3] += z

            # 取引所Bで通過へ戻す
            for Z in change:
                poss_third = poss_second[:]
                for x in Z:
                    y = B[x]
                    z = poss_third[3] // y
                    poss_third[x] += z
                    poss_third[3] -= z
                # 取引所Aでドングリへ
                for T in change:
                    poss_forth = poss_third[:]
                    for x in T:
                        y = A[x]
                        z = poss_forth[x] * y
                        poss_forth[x] = 0
                        poss_forth[3] += z
                temp = poss_forth[3]
                if temp > answer:
                    answer = temp

print(answer)

Submission status: Wrong Answer

Solution code:
n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
dp = [0] * (n + 1)
for i in range(n):
    if i + ga <= n:
        dp[i + ga] = max(dp[i + ga], dp[i] + gb)
    if i + sa <= n:
        dp[i + sa] = max(dp[i + sa], dp[i] + sb)
    if i + ba <= n:
        dp[i + ba] = max(dp[i + ba], dp[i] + bb)
ans = 0
for i in range(n + 1):
    ans = max(ans, dp[i] + n - i)
p = min(25000024, ans)
dp = [0] * (p + 1)
for i in range(p):
    if i + gb <= p:
        dp[i + gb] = max(dp[i + gb], dp[i] + ga)
    if i + sb <= p:
        dp[i + sb] = max(dp[i + sb], dp[i] + sa)
    if i + bb <= p:
        dp[i + bb] = max(dp[i + bb], dp[i] + ba)
res = 0
for i in range(p + 1):
    res = max(ans, dp[i] + ans - i)
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
dp = [0] * (n + 1)
for i in range(n):
    if i + ga <= n:
        dp[i + ga] = max(dp[i + ga], dp[i] + gb)
    if i + sa <= n:
        dp[i + sa] = max(dp[i + sa], dp[i] + sb)
    if i + ba <= n:
        dp[i + ba] = max(dp[i + ba], dp[i] + bb)
ans = 0
for i in range(n + 1):
    ans = max(ans, dp[i] + n - i)
p = min(25000024, ans)
dp = [0] * (p + 1)
for i in range(p):
    if i + gb <= p:
        dp[i + gb] = max(dp[i + gb], dp[i] + ga)
    if i + sb <= p:
        dp[i + sb] = max(dp[i + sb], dp[i] + sa)
    if i + bb <= p:
        dp[i + bb] = max(dp[i + bb], dp[i] + ba)
res = 0
for i in range(p + 1):
    res = max(ans, dp[i] + ans - i)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
dp = [0] * (n + 1)
for i in range(n):
    if i + ga <= n:
        dp[i + ga] = max(dp[i + ga], dp[i] + gb)
    if i + sa <= n:
        dp[i + sa] = max(dp[i + sa], dp[i] + sb)
    if i + ba <= n:
        dp[i + ba] = max(dp[i + ba], dp[i] + bb)
ans = 0
for i in range(n + 1):
    ans = max(ans, dp[i] + n - i)
dp = [0] * 25000025
for i in range(25000025):
    if i + gb <= n:
        dp[i + gb] = max(dp[i + gb], dp[i] + ga)
    if i + sb <= n:
        dp[i + sb] = max(dp[i + sb], dp[i] + sa)
    if i + bb <= n:
        dp[i + bb] = max(dp[i + bb], dp[i] + ba)
res = 0
for i in range(min(25000025, ans + 1)):
    res = max(ans, dp[i] + ans - i)
print(ans)