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: Accepted

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

A = (gA, sA, bA)
B = (gB, sB, bB)


# 各貴金属について、買う／売る可能性のある取引所は一意に定まることを用いて
# 全探索により解を求める
def f(n, r):
    R = len(r)
    if R == 0:
        return n
    elif R == 1:
        return n + (r[-1][1] - r[-1][0]) * (n // r[-1][0])
    elif R == 2:
        dr0 = r[0][1] - r[0][0]
        dr1 = r[-1][1] - r[-1][0]
        res = 0
        for x in range(n // r[0][0] + 1):
            res = max(res, dr0 * x + dr1 * ((n - r[0][0] * x) // r[-1][0]))
        return n + res
    else:
        dr0 = r[0][1] - r[0][0]
        dr1 = r[1][1] - r[1][0]
        dr2 = r[-1][1] - r[-1][0]
        res = 0
        for x in range(n // r[0][0] + 1):
            m = n - r[0][0] * x
            for y in range(m // r[1][0] + 1):
                res = max(
                    res,
                    dr0 * x + dr1 * y + dr2 * ((m - r[1][0] * y) // r[-1][0])
                )
        return n + res


ans = f(
    f(
        N,
        [
            (a, b)
            for a, b in zip(A, B)
            if a < b
        ]
    ),
    [
        (b, a)
        for b, a in zip(B, A)
        if a > b
    ]
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
def change(N, A, B):
    ans = N
    dp = list(range(N+1))
    for i in range(3):
        w = A[i]
        v = B[i]
        for j in range(N+1):
            if w <= j:
                dp[j] = max(dp[j], dp[j-w] + v)
    return dp[N]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    N1 = change(N, A, B)
    N2 = change(N1, B, A)
    print(N2)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def count(n, a, b):
    a0, a1, a2 = a
    b0, b1, b2 = b
    dp = [0] * (n + 1)
    for i in range(n + 1):
        c0 = dp[i - a0] + b0 if i - a0 >= 0 else 0
        c1 = dp[i - a1] + b1 if i - a1 >= 0 else 0
        c2 = dp[i - a2] + b2 if i - a2 >= 0 else 0
        dp[i] = max(i, c0, c1, c2)
    return dp[n]


print(count(count(N, A, B), B, A))

# https://atcoder.jp/contests/diverta2019-2/submissions/5942579

Submission status: Accepted

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


def count(n, a, b):
    a0, a1, a2 = a
    b0, b1, b2 = b
    dp = [0] * (n + 1)
    for i in range(n + 1):
        c0 = dp[i - a0] + b0 if i - a0 >= 0 else 0
        c1 = dp[i - a1] + b1 if i - a1 >= 0 else 0
        c2 = dp[i - a2] + b2 if i - a2 >= 0 else 0
        dp[i] = max(i, c0, c1, c2)
    return dp[n]


print(count(count(N, A, B), B, A))

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
# def main():
N = int( input())
A = list( map( int, input().split()))
B = list( map( int ,input().split()))
dpOne = [0]*(N+1)
for i in range(3):
    a, b = A[i], B[i]
    for j in range(N-a+1):
        if dpOne[j+a] < dpOne[j]+b:
            dpOne[j+a] = dpOne[j]+b
donguri = N
for i in range(N+1):
    if donguri < N-i+dpOne[i]:
        donguri = N - i +dpOne[i]
K = donguri
dpTwo = [0]*(K+1)
for i in range(3):
    a, b  = A[i], B[i]
    for j in range(K-b+1):
        if dpTwo[j+b] < dpTwo[j]+a:
            dpTwo[j+b] = dpTwo[j]+a
ans = K
for i in range(K+1):
    if ans < K - i + dpTwo[i]:
        ans = K-i+dpTwo[i]
print( ans)
# if __name__ == '__main__':
#     main()

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
def main():
    N = int( input())
    A = list( map( int, input().split()))
    B = list( map( int ,input().split()))
    dpOne = [0]*(N+1)
    for i in range(3):
        a, b = A[i], B[i]
        for j in range(N-a+1):
            if dpOne[j+a] < dpOne[j]+b:
                dpOne[j+a] = dpOne[j]+b
    donguri = N
    for i in range(N+1):
        if donguri < N-i+dpOne[i]:
            donguri = N - i +dpOne[i]
    K = donguri
    dpTwo = [0]*(K+1)
    for i in range(3):
        a, b  = A[i], B[i]
        for j in range(K-b+1):
            if dpTwo[j+b] < dpTwo[j]+a:
                dpTwo[j+b] = dpTwo[j]+a
    ans = K
    for i in range(K+1):
        if ans < K - i + dpTwo[i]:
            ans = K-i+dpTwo[i]
    print( ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def napzak(w,v,limit):
    dp = [0]*(limit+1)
    wv = [(weight,value) for weight,value in zip(w,v) if value>weight]
    if wv == []:
        return limit
    for i in range(1,limit+1):
        for j,value in wv:
            if (i-j)>=0 and dp[i]<(dp[i-j]+value-j):
                dp[i] = dp[i-j]+value-j
    return dp[limit]+limit

n = int(input())
wa = list(map(int,input().split()))
wb = list(map(int,input().split()))

m = napzak(wa,wb,n)
ans = napzak(wb,wa,m)

print(ans)

Submission status: Accepted

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

    def f(c,n):
        c0 = c[0]
        if len(c) == 1:
            return n % c0[0] + n // c0[0] * c0[1]

        r = n
        for i in range(0,n+1,c0[0]):
            t = i // c0[0] * c0[1] + f(c[1:], n-i)
            if r < t:
                r = t
        return r

    c = sorted([(ai,bi) for ai,bi in zip(a,b) if ai < bi], reverse=True)
    t = n
    if len(c) > 0:
        t = f(c,n)

    d = sorted([(ai,bi) for ai,bi in zip(b,a) if ai < bi], reverse=True)
    r = t
    if len(d) > 0:
        r = f(d,t)

    return r


print(main())

Submission status: Accepted

Solution code:
N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
def solve(N, P):
    V = []; W = []
    for w, v in P:
        if w < v:
            V.append(v); W.append(w)
    if len(V) == 1:
        v = V[0]; w = W[0]
        k = N // w
        return N - k*w + k*v
    if len(V) == 2:
        w1, w2 = W
        M = w1 * w2
        dp = [i for i in range(M+1)]
        for v, w in zip(V, W):
            if v <= w:
                continue
            for k in range(w, M+1):
                dp[k] = max(dp[k], dp[k-w] + v)
        for i in range(M):
            dp[i+1] = max(dp[i+1], dp[i])
        ans = 0
        for i in range(M):
            k, r = divmod(N, (i+1))
            ans = max(ans, dp[i+1] * k + dp[r])
        return ans
    dp = [i for i in range(N+1)]
    for v, w in zip(V, W):
        if v <= w:
            continue
        for k in range(w, N+1):
            dp[k] = max(dp[k], dp[k-w] + v)
    return max(dp)

A = solve(N, [[ga, gb], [sa, sb], [ba, bb]])
B = solve(A, [[gb, ga], [sb, sa], [bb, ba]])
print(B)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
def nap(N,goods):
    dp=[-1*float('inf')]*(N+1)
    dp[0]=0
    for i in range(N):
        for w,v in goods:
            if i+w<=N:
                dp[i+w]=max(dp[i+w],dp[i]+v)
    return max([dp[i]+N-i for i in range(N+1)])
goods1=[(a,b) for a,b in zip(A,B) if a<b]
goods2=[(b,a) for a,b in zip(A,B) if a>b]
if len(goods1)>0:
    N=nap(N,[(a,b) for a,b in zip(A,B)])
if len(goods2)==0:
    print(N)
elif len(goods2)==1:
    print(N%goods2[0][0]+(N//goods2[0][0])*goods2[0][1])
elif len(goods2)==3:
    print(nap(N,goods2))
else:
    a,b,c,d=goods2[0][0],goods2[0][1],goods2[1][0],goods2[1][1]
    if (b-a)/a<(d-c)/c:
        a,b,c,d=c,d,a,b
    elif (b-a)/a==(d-c)/c and a>c:
        a,b,c,d=c,d,a,b
    bord=(N//a)*b+((N%a)//c)*d+(N%a)%c
    x=N//a
    ans=bord
    for i in range(1,1+x):
        now=(x-i)*b+((N-(x-i)*a)//c)*d+(N-(x-i)*a)%c
        if now+d<ans:
            break
        else:
            ans=max(ans,now)
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
GA, SA, BA = map(int, input().split())
GB, SB, BB = map(int, input().split())

def napsac(x, g1, s1, b1, g2, s2, b2):
    dp = [0 for _ in range(x+1)]
    dp[0] = 0

    def case(i, m1, m2):
        return 0 if i - m1 < 0 else dp[i-m1] + m2

    for i in range(1,x+1):
        dp[i] = max(i, case(i, g1, g2), case(i, s1, s2), case(i, b1, b2))

    return dp[-1]

print(napsac(napsac(N, GA, SA, BA, GB, SB, BB), GB, SB, BB, GA, SA, BA))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

def donguri(n, a, b):
    dp = [0]*(n+1)
    for w in range(n+1):
        x0 = dp[w-a[0]] + b[0] if (w-a[0]>=0) else w
        x1 = dp[w-a[1]] + b[1] if (w-a[1]>=0) else w
        x2 = dp[w-a[2]] + b[2] if (w-a[2]>=0) else w
        dp[w] = max(w, x0, x1, x2)
    return dp[-1]

print(donguri(donguri(N,A,B),B,A))

Submission status: Accepted

Solution code:
N = int(input())						# 5
A = list( map(int, input().split()) )	# 1 2 3 4 5 ...
B = list( map(int, input().split()) )	# 1 2 3 4 5 ...


def F(N,A,B):
	dp=[0]*(N+1)
	for n in range(N+1):
		v=n
		for i in range(3):
			if n>=A[i]:
				x = dp[n-A[i]]+B[i]
				if x>v:
					v = x
		dp[n]=v

		#for a,b in zip(A,B):
		#	if n>=a:
		#		v = max(v, dp[n-a]+b)
		#dp[n]=v

		#dp[n] = max(n, max(dp[n-a]+b for a,b in zip(A,B) if n>=a))
	
	return dp[N]

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

Submission status: Accepted

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

    # A : ドングリと金属に変える
    # B : 全部ドングリに変える
    # B : ドングリと金属に変える（無駄な操作でロスがないので、いったんドングリ化してよい）
    # A : ドングリに変える

    dp1 = list(range(N + 1))  # dp1[巣から持ってきたドングリ数] = 取引所 B で持てる最大ドングリ数
    dp1[0] = 0
    for i in range(N + 1):
        if i >= ga:
            dp1[i] = max(dp1[i], dp1[i - ga] + gb)
        if i >= sa:
            dp1[i] = max(dp1[i], dp1[i - sa] + sb)
        if i >= ba:
            dp1[i] = max(dp1[i], dp1[i - ba] + bb)

    N = dp1[N]
    dp2 = list(range(N + 1))  # dp2[取引所 B から持ってきたドングリ数] = 巣に持ち帰れる最大ドングリ数
    for i in range(N + 1):
        if i >= gb:
            dp2[i] = max(dp2[i], dp2[i - gb] + ga)
        if i >= sb:
            dp2[i] = max(dp2[i], dp2[i - sb] + sa)
        if i >= bb:
            dp2[i] = max(dp2[i], dp2[i - bb] + ba)
    print(dp2[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    # 1 周目 : dp[巣から持ってきたドングリ数] = 取引所 B で持てる最大ドングリ数
    dp = list(range(N + 1))
    mas = tuple(zip(a, b))
    for i in range(N + 1):
        for to_metal, to_acorn in mas:
            if i >= to_metal:
                dp[i] = max(dp[i], dp[i - to_metal] + to_acorn)
    N = dp[N]

    # 2 周目 : dp[取引所 B から持ってきたドングリ数] = 巣に持ち帰れる最大ドングリ数
    dp = list(range(N + 1))
    mas = tuple(zip(b, a))
    for i in range(N + 1):
        for to_metal, to_acorn in mas:
            if i >= to_metal:
                dp[i] = max(dp[i], dp[i - to_metal] + to_acorn)
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
import copy

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, GSB):
    def f(N, gsb):
        dp0 = [0] * (N+1)
        dp1 = [0] * (N+1)
        for i in range(3):
            v = gsb[1][i] - gsb[0][i]
            a = gsb[0][i]
            if v > 0:
                for w in range(N+1):
                    if w >= a:
                        dp1[w] = max(dp0[w], dp1[w-a] + v)
            else:
                dp1 = dp0
            dp0 = dp1
            dp1 = copy.copy(dp0)
        return dp0[N] + N
    tmp = f(N, GSB)
    # print(tmp)
    GSB[0], GSB[1] = GSB[1], GSB[0]
    return f(tmp, GSB)


def main():
    N = read_int()
    GSB = [read_int_n() for _ in range(2)]
    print(slv(N, GSB))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = [int(item) for item in input().split()]
B = [int(item) for item in input().split()]
 
dp = [0] * (n+1)
AB = [] 
for a, b in zip(A, B):
    if b > a:
        AB.append((a, b))
for i in range(n+1):
    for a, b in AB:
        if i - a >= 0:
            y = dp[i-a] + b - a
            if y > dp[i]:
                dp[i] = y
n += dp[n]
dp = [0] * (n+1)
BA = []
for b, a in zip(B, A):
    if a > b:
        BA.append((b, a))
for i in range(n+1):
    for b, a in BA:
        if i - b >= 0:
            y = dp[i-b] + a - b
            if y > dp[i]:
                dp[i] = y 
print(n + dp[n])

Submission status: Accepted

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

# A : ドングリと金属に変える
# B : 全部ドングリに変える
# B : ドングリと金属に変える（無駄な操作でロスがないので、いったんドングリ化してよい）
# A : ドングリに変える

dp1 = list(range(N + 1))  # dp1[巣から持ってきたドングリ数] = 取引所 B で持てる最大ドングリ数
dp1[0] = 0
for i in range(N + 1):
    if i >= ga:
        dp1[i] = max(dp1[i], dp1[i - ga] + gb)
    if i >= sa:
        dp1[i] = max(dp1[i], dp1[i - sa] + sb)
    if i >= ba:
        dp1[i] = max(dp1[i], dp1[i - ba] + bb)

N = dp1[N]
dp2 = list(range(N + 1))  # dp2[取引所 B から持ってきたドングリ数] = 巣に持ち帰れる最大ドングリ数
for i in range(N + 1):
    if i >= gb:
        dp2[i] = max(dp2[i], dp2[i - gb] + ga)
    if i >= sb:
        dp2[i] = max(dp2[i], dp2[i - sb] + sa)
    if i >= bb:
        dp2[i] = max(dp2[i], dp2[i - bb] + ba)
print(dp2[N])

Submission status: Accepted

Solution code:
def main():
    N=int(input())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    dp=[N]*(N+1)
    #dp[i];=i個目まで選んで交換したときの最大
    C=[B[i]-A[i] for i in range(3)]
    for i in range(N):
        dp[i+1]=max(dp[i+1],dp[i])
        for j in range(3):
            if i+1-A[j]>=0:
                dp[i+1]=max(dp[i+1],dp[i+1-A[j]]+C[j])
    M=dp[N]
    dp=[0]*(M+1)
    C=[A[i]-B[i] for i in range(3) if A[i]-B[i]>=0]
    C=[]
    b=[]
    a=[]
    for i in range(3):
        if A[i]-B[i]>=0:
            C.append(A[i]-B[i])
            b.append(B[i])
            a.append(A[i])
    B=b
    A=a
    for i in range(M):
        dp[i+1]=max(dp[i+1],dp[i])
        for j in range(len(C)):
            if i+1-B[j]>=0:
                dp[i+1]=max(dp[i+1],dp[i+1-B[j]]+C[j])
    print(M+dp[M])
if __name__=='__main__':#おまじない
  main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
dp=[N]*(N+1)
#dp[i];=i個目まで選んで交換したときの最大
C=[B[i]-A[i] for i in range(3)]
for i in range(N):
    dp[i+1]=max(dp[i+1],dp[i])
    for j in range(3):
        if i+1-A[j]>=0:
            dp[i+1]=max(dp[i+1],dp[i+1-A[j]]+C[j])
M=dp[N]
dp=[0]*(M+1)
C=[A[i]-B[i] for i in range(3) if A[i]-B[i]>=0]
C=[]
b=[]
a=[]
for i in range(3):
    if A[i]-B[i]>=0:
        C.append(A[i]-B[i])
        b.append(B[i])
        a.append(A[i])
B=b
A=a
for i in range(M):
    dp[i+1]=max(dp[i+1],dp[i])
    for j in range(len(C)):
        if i+1-B[j]>=0:
            dp[i+1]=max(dp[i+1],dp[i+1-B[j]]+C[j])
print(M+dp[M])

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ea=[]
eb=[]
for i in range(3):
    if(a[i]<b[i]):
        ea.append((a[i],b[i]))
    elif(a[i]>b[i]):
        eb.append((b[i],a[i]))
ea.sort(reverse=True)
eb.sort(reverse=True)
def main(ea,n):
    if(len(ea)==1):
        fa=n%ea[0][0]+n//ea[0][0]*ea[0][1]
    elif(len(ea)==2):
        ga,gb=ea[0]
        ba,bb=ea[1]
        fa=n
        for i in range(n+1):
            if(ga*i>n):
                break
            k=n-ga*i
            tmp=i*gb+k%ba+(k//ba)*bb
            fa=max(tmp,fa)
    elif(len(ea)==3):
        ga,gb=ea[0]
        sa,sb=ea[1]
        ba,bb=ea[2]
        fa=n
        if(ga==sa):
            return main([ea[0],ea[2]],n)
        if(sa==ba):
            return main([ea[0],ea[1]],n)
        for i in range(n+1):
            if(ga*i>n):
                break
            for j in range(n+1):
                if(ga*i+sa*j>n):
                    break
                k=n-ga*i-sa*j
                tmp=i*gb+j*sb+k%ba+k//ba*bb
                fa=max(tmp,fa)
    else:
        fa=n
    return fa
n=main(ea,n)
n=main(eb,n)
print(n)

Submission status: Accepted

Solution code:
n = int(input())
w1 = list(map(int,input().split()))
w2 = list(map(int,input().split()))
v1 = [0,0,0]
for i in range(3):
    v1[i] = w2[i] - w1[i]
dp1 = [0] * (n+1)
for i in range(n):
    p = 0
    q = 0
    r = 0
    if i+1 - w1[0] >= 0:
        p = dp1[i+1 - w1[0]] + v1[0]
    if i+1 - w1[1] >= 0:
        q = dp1[i+1 - w1[1]] + v1[1]
    if i+1 - w1[2] >= 0:
        r = dp1[i+1 - w1[2]] + v1[2]
    dp1[i+1] = max(p,q,r,dp1[i])
m = dp1[-1] + n

v2 = [0,0,0]
for i in range(3):
    v2[i] = w1[i] - w2[i]
dp2 = [0] * (m+1)
for i in range(m):
    p = 0
    q = 0
    r = 0
    if i+1 - w2[0] >= 0:
        p = dp2[i+1 - w2[0]] + v2[0]
    if i+1 - w2[1] >= 0:
        q = dp2[i+1 - w2[1]] + v2[1]
    if i+1 - w2[2] >= 0:
        r = dp2[i+1 - w2[2]] + v2[2]
    dp2[i+1] = max(p,q,r,dp2[i])
print(m + dp2[-1])

Submission status: Accepted

Solution code:
def knapsack_123(values,weights,capacity):
    work = [0 for i in range(capacity+1)]
    for v,w in zip(values,weights):
        for c in range(w, capacity+1):
            work[c]=max(work[c],work[c-w]+v)
    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: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,k = LI()
    print(n%k)
    return

#B
def B():
    n = I()
    po = LIR(n)
    if n == 1:
        print(1)
        quit()
    ans = float("inf")
    for i in range(n):
        for j in range(n):
            if i == j:continue
            x,y = po[i]
            s,t = po[j]
            p,q = s-x,t-y
            m = n
            for k in range(n):
                for l in range(n):
                    if (po[k][0]-po[l][0],po[k][1]-po[l][1]) == (p,q):m -= 1
            if m < ans:
                ans = m
    print(ans)
    return

#C
def C():
    n = I()
    a = LI()
    a.sort()
    if a[0] >= 0:
        print(sum(a)-2*a[0])
        for i in range(1,n-1):
            print(a[0],a[i])
            a[0] -= a[i]
        print(a[n-1],a[0])
    else:
        if a[-1] < 0:
            print(2*a[-1]-sum(a))
            for i in range(n-1):
                print(a[-1],a[i])
                a[-1] -= a[i]
        else:
            m = bisect.bisect_left(a,0)
            p = n-m
            ans = -sum(a[:m])+sum(a[m:])
            print(ans)
            if p > m:
                l = a[-1]
                a = a[:-1]
                a = a[::-1]
                p -= 1
                p,m = m,p
                k = a[m]-a[m-1]
                print(a[m],a[m-1])
                for i in range(p-1):
                    print(a[m-i-2],k)
                    k = a[m-i-2]-k
                    print(a[m+i+1],k)
                    k = a[m+i+1]-k
                for i in range(m-p):
                    print(k,a[i])
                    k -= a[i]
                print(l,k)
            else:
                k = a[m]-a[m-1]
                print(a[m],a[m-1])
                for i in range(p-1):
                    print(a[m-i-2],k)
                    k = a[m-i-2]-k
                    print(a[m+i+1],k)
                    k = a[m+i+1]-k
                for i in range(m-p):
                    print(k,a[i])
                    k -= a[i]
    return

#D
def D():
    n = I()
    a = LI()
    b = LI()
    dp = [0 for i in range(n+1)]
    for w in range(n+1):
        dp[w] = w
        x0 = dp[w-a[0]]+b[0] if w-a[0] >= 0 else w
        x1 = dp[w-a[1]]+b[1] if w-a[1] >= 0 else w
        if x0 > x1:
            x1 = x0
        x2 = dp[w-a[2]]+b[2] if w-a[2] >= 0 else w
        if x1 > x2:
            x2 = x1
        if x2 > dp[w]:
            dp[w] = x2
    n = dp[-1]
    dp = [0 for i in range(n+1)]
    for w in range(n+1):
        dp[w] = w
        x0 = dp[w-b[0]]+a[0] if w-b[0] >= 0 else w
        x1 = dp[w-b[1]]+a[1] if w-b[1] >= 0 else w
        if x0 > x1:
            x1 = x0
        x2 = dp[w-b[2]]+a[2] if w-b[2] >= 0 else w
        if x1 > x2:
            x2 = x1
        if x2 > dp[w]:
            dp[w] = x2
    print(dp[n])
    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#G
def G():
    n = I()

    return

#H
def H():
    n = I()

    return

#I
def I_():
    n = I()

    return

#J
def J():
    n = I()

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
A=tuple(map(int,input().split()))
B=tuple(map(int,input().split()))

def exchange(n,A,B):
    R=[]
    for a,b in zip(A,B):
        if a<b:
            R.append((a,b))
    if len(R)==0:
        return n
    if len(R)==1:
        a,b=R[0]
        return n+n//a*(b-a)
    if len(R)==2:
        a0,b0=R[0]; a1,b1=R[1]
        ans=n
        s=n//a0
        for i in range(s+1):
            p=b0*i
            q=n-a0*i
            r=q//a1
            ans=max(ans,p+q+r*(b1-a1))
        return ans
    a0,b0=R[0]; a1,b1=R[1]; a2,b2=R[2]
    ans=n
    s=n//a0
    for i in range(s+1):
        p=n-a0*i
        t=p//a1
        for j in range(t+1):
            q=p-a1*j
            ans=max(ans,b0*i+b1*j+q+q//a2*(b2-a2))
    return ans

tmp=exchange(n,A,B)
print(exchange(tmp,B,A))

Submission status: Accepted

Solution code:
def solve(n, ga, sa, ba, gb, sb, bb):
    gd, sd, bd = gb - ga, sb - sa, bb - ba

    if bd <= 0:
        if sd <= 0:
            if gd <= 0:
                return n
            return n + n // ga * gd
        if gd <= 0:
            return n + n // sa * sd
        return max(n + g * gd + (n - g * ga) // sa * sd for g in range(n // ga + 1))
    if sd <= 0:
        if gd <= 0:
            return n + n // ba * bd
        return max(n + g * gd + (n - g * ga) // ba * bd for g in range(n // ga + 1))
    if gd <= 0:
        return max(n + s * sd + (n - s * sa) // ba * bd for s in range(n // sa + 1))
    (_, ga, gd), (_, sa, sd), (_, ba, bd) = \
        sorted([(gb / ga, -ga, gd), (sb / sa, -sa, sd), (bb / ba, -ba, bd)], reverse=True)
    ga, sa, ba = -ga, -sa, -ba
    sga = 0 if n // ga < 1000 else n // ga // 2
    return max(n + g * gd + s * sd + (n - g * ga - s * sa) // ba * bd
               for g in range(sga, n // ga + 1)
               for s in range((n - g * ga) // sa + 1))


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: Accepted

Solution code:
import sys
range = xrange
input = raw_input
 
def main():
  n = int(input())
  A = [int(x) for x in input().split()]
  B = [int(x) for x in input().split()]
 
  DP = [0]*(n+1)
  DP[n] = n
  for j in range(3):
      sell = A[j]
      extra = B[j] - sell
      if extra > 0:
          for i in reversed(range(len(DP) - sell)):
              DP[i] = max(DP[i], DP[i + sell] + extra)
  n = max(DP)
  A,B = B,A
 
  DP = [0]*(n+1)
  DP[n] = n
  for j in range(3):
      sell = A[j]
      extra = B[j] - sell
      if extra > 0:
          for i in reversed(range(len(DP) - sell)):
              DP[i] = max(DP[i], DP[i + sell] + extra) 
  print(max(DP))
 
main()

Submission status: Accepted

Solution code:
import sys
range = xrange
input = raw_input
 
def main():
  n = int(input())
  A = [int(x) for x in input().split()]
  B = [int(x) for x in input().split()]
 
  DP = [0]*(n+1)
  DP[n] = n
  for j in range(3):
      sell = A[j]
      extra = B[j] - sell
      if extra > 0:
          for i in reversed(range(sell,len(DP))):
              DP[i - sell] = max(DP[i - sell], DP[i] + extra)
  n = max(DP)
  A,B = B,A
 
  DP = [0]*(n+1)
  DP[n] = n
  for j in range(3):
      sell = A[j]
      extra = B[j] - sell
      if extra > 0:
          for i in reversed(range(sell,len(DP))):
              DP[i - sell] = max(DP[i - sell], DP[i] + extra) 
  print(max(DP))
 
main()

Submission status: Accepted

Solution code:
import sys
range = xrange
input = raw_input
 
def main():
  n = int(input())
  A = [int(x) for x in input().split()]
  B = [int(x) for x in input().split()]

  DP = [0]*(n+1)
  DP[n] = n
  for j in range(3):
      sell = A[j]
      extra = B[j] - sell
      if extra > 0:
          for i in reversed(range(sell,len(DP))):
              if DP[i] + extra > DP[i - sell]:
                  DP[i-sell] = DP[i] + extra
  n = max(DP)
  A,B = B,A

  DP = [0]*(n+1)
  DP[n] = n
  for j in range(3):
      sell = A[j]
      extra = B[j] - sell
      if extra > 0:
          for i in reversed(range(sell,len(DP))):
              if DP[i] + extra > DP[i - sell]:
                  DP[i-sell] = DP[i] + extra

  print(max(DP))

main()

Submission status: Accepted

Solution code:
import sys
range = xrange
input = raw_input

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

DP = [0]*(n+1)
DP[n] = n
for j in range(3):
    sell = A[j]
    extra = B[j] - sell
    if extra > 0:
        for i in reversed(range(sell,len(DP))):
            if DP[i] + extra > DP[i - sell]:
                DP[i-sell] = DP[i] + extra
n = max(DP)
A,B = B,A
 
DP = [0]*(n+1)
DP[n] = n
for j in range(3):
    sell = A[j]
    extra = B[j] - sell
    if extra > 0:
        for i in reversed(range(sell,len(DP))):
            if DP[i] + extra > DP[i - sell]:
                DP[i-sell] = DP[i] + extra
 
print(max(DP))

Submission status: Accepted

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


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

    # A->Bでのトレード成果
    dp = [0] * (n + 1)

    for i in range(1, len(dp)):
        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)
    # print(dp)
    a_result = dp[-1]

    # B->Aでのトレード成果
    dp = [0] * (a_result + 1)

    for i in range(1, len(dp)):
        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)
    print(dp[-1])

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

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

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)


def f(N,A,B):
    dp = [0]*(N+1)
    for i in range(N+1):
        x = i
        for j in range(3):
            if i >= A[j]:
                y = dp[i-A[j]]+B[j]
                if x < y:
                    x = y
        dp[i] = x
    return dp[N]
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
print(f(f(N,A,B),B,A))