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())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
dp = [0]*(n+1)
fir = []
sec = []
for i in range(3):
  if a[i]>b[i]:
    sec.append((b[i],a[i]))
  else:
    fir.append((a[i],b[i]))
for i in range(1,n+1):
  dp[i] = i
  for x,y in fir:
    if i-x >= 0:
      dp[i] = max(dp[i],dp[i-x]+y)
n = dp[n]
dp = [0]*(n+1)
for i in range(1,n+1):
  dp[i] = i
  for x,y in sec:
    if i-x >= 0:
      dp[i] = max(dp[i],dp[i-x]+y)
print(dp[n])

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.readline
from sys import setrecursionlimit
setrecursionlimit(10**9)

def inpl(): return list(map(int, input().split()))
N = int(input())
GA = inpl()
GB = inpl()

typ = [GA[i] <= GB[i] for i in range(3)]

if sum(typ) == 3:
    ans = 0
    for g in range(N//GA[0] + 1):
        D = N - GA[0]*g
        for s in range(D//GA[1] + 1):
            b, D2 = divmod(D - GA[1]*s, GA[2])
            ans = max(ans, D2 + g*GB[0] + s*GB[1] + b*GB[2])

elif sum(typ) == 2:
    ans = 0
    x, y = [i for i in range(3) if typ[i]]
    z = [i for i in range(3) if not typ[i]][0]
    for a in range(N//GA[x] + 1):
        b, D = divmod(N - GA[x]*a, GA[y])
        c, D2 = divmod(D + GB[x]*a + GB[y]*b, GB[z])
        ans = max(ans, D2 + c*GA[z])

elif sum(typ) == 1:
    ans = 0
    x, y = [i for i in range(3) if not typ[i]]
    z = [i for i in range(3) if typ[i]][0]
    c, D = divmod(N, GA[z])
    D += GB[z]*c

    for a in range(D//GB[x] + 1):
        b, D2 = divmod(D-GB[x]*a, GB[y])
        ans = max(ans, D2 + GA[x]*a + GA[y]*b)


else:
    ans = 0
    for g in range(N//GB[0] + 1):
        D = N - GB[0]*g
        for s in range(D//GB[1] + 1):
            b, D2 = divmod(D - GB[1]*s, GB[2])
            ans = max(ans, D2 + g*GA[0] + s*GA[1] + b*GA[2])

print(ans)

Submission status: Accepted

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

Achange = []
Bchange = []

for i in range(3):
  if A[i] > B[i]:
    Bchange.append(i)
  elif A[i] < B[i]:
    Achange.append(i)

#print(Achange, Bchange)

# 最初のA交換所→B交換所
Dmax1 = N
if Achange:
  if len(Achange)==3:
    i = Achange[0]
    j = Achange[1]
    k = Achange[2]
    for x in range(N+1):
      for y in range(N+1):
        if A[i]*x+A[j]*y <= N:
          Dmax1 = max(Dmax1, B[i]*x + B[j]*y + (N-A[i]*x-A[j]*y)%A[k] + (N-A[i]*x-A[j]*y)//A[k] * B[k])
    
  if len(Achange)==2:
    i = Achange[0]
    j = Achange[1]
    for x in range(N+1):
      if A[i]*x <= N:
          Dmax1 = max(Dmax1, B[i]*x + (N-A[i]*x)%A[j] + (N-A[i]*x)//A[j] * B[j])
    
  if len(Achange)==1:
    i = Achange[0]
    Dmax1 = max(Dmax1, N%A[i] + (N//A[i] * B[i]))
    
#print(Dmax1)
#print(Achange, Bchange)
#次のB交換所→A交換所
Achange = Bchange
A,B=B,A
N = Dmax1
#print(Achange, Bchange)

if Achange:
  if len(Achange)==3:
    i = Achange[0]
    j = Achange[1]
    k = Achange[2]
    for x in range(N+1):
      for y in range(N+1):
        if A[i]*x+A[j]*y <= N:
          Dmax1 = max(Dmax1, B[i]*x + B[j]*y + (N-A[i]*x-A[j]*y)%A[k] + (N-A[i]*x-A[j]*y)//A[k] * B[k])
    
  if len(Achange)==2:
    i = Achange[0]
    j = Achange[1]
    for x in range(N+1):
      if A[i]*x <= N:
          Dmax1 = max(Dmax1, B[i]*x + (N-A[i]*x)%A[j] + (N-A[i]*x)//A[j] * B[j])
    
  if len(Achange)==1:
    i = Achange[0]
    Dmax1 = max(Dmax1, N%A[i] + (N//A[i] * B[i]))
    
print(Dmax1)

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.readline
from sys import setrecursionlimit
setrecursionlimit(10**9)

def inpl(): return list(map(int, input().split()))
N = int(input())
GA = inpl()
GB = inpl()

typ = [GA[i] <= GB[i] for i in range(3)]

if sum(typ) == 3:
    ans = 0
    for g in range(N//GA[0] + 1):
        D = N - GA[0]*g
        for s in range(D//GA[1] + 1):
            b, D2 = divmod(D - GA[1]*s, GA[2])
            ans = max(ans, D2 + g*GB[0] + s*GB[1] + b*GB[2])

elif sum(typ) == 2:
    ans = 0
    x, y = [i for i in range(3) if typ[i]]
    z = [i for i in range(3) if not typ[i]][0]
    for a in range(N//GA[x] + 1):
        b, D = divmod(N - GA[x]*a, GA[y])
        c, D2 = divmod(D + GB[x]*a + GB[y]*b, GB[z])
        ans = max(ans, D2 + c*GA[z])

elif sum(typ) == 1:
    ans = 0
    x, y = [i for i in range(3) if not typ[i]]
    z = [i for i in range(3) if typ[i]][0]
    c, D = divmod(N, GA[z])
    D += GB[z]*c

    for a in range(D//GB[x] + 1):
        b, D2 = divmod(D-GB[x]*a, GB[y])
        ans = max(ans, D2 + GA[x]*a + GA[y]*b)

    for b in range(D//GB[y] + 1):
        a, D2 = divmod(D-GB[y]*b, GB[x])
        ans = max(ans, D2 + GA[x]*a + GA[y]*b)

else:
    ans = 0
    for g in range(N//GB[0] + 1):
        D = N - GB[0]*g
        for s in range(D//GB[1] + 1):
            b, D2 = divmod(D - GB[1]*s, GB[2])
            ans = max(ans, D2 + g*GA[0] + s*GA[1] + b*GA[2])

print(ans)

Submission status: Accepted

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

ans = 0

if gB > gA and sB > sA and bB > bA:
    for g in range(N // gA + 1):
        n = N - g * gA
        for s in range(n // sA + 1):
            m = n - s * sA
            b = m // bA
            m = m % bA
            ans = max(ans, g * gB + s * sB + b * bB + m)
elif gB > gA and sB > sA and bB <= bA:
    for g in range(N // gA + 1):
        n = N - g * gA
        for s in range(n // sA + 1):
            m = n - s * sA
            m = g * gB + s * sB + m
            b = m // bB
            m = m % bB
            ans = max(ans, b * bA + m)
elif gB > gA and sB <= sA and bB > bA:
    for g in range(N // gA + 1):
        n = N - g * gA
        for b in range(n // bA + 1):
            m = n - b * bA
            m = g * gB + b * bB + m
            s = m // sB
            m = m % sB
            ans = max(ans, s * sA + m)
elif gB <= gA and sB > sA and bB > bA:
    for s in range(N // sA + 1):
        n = N - s * sA
        for b in range(n // bA + 1):
            m = n - b * bA
            m = s * sB + b * bB + m
            g = m // gB
            m = m % gB
            ans = max(ans, g * gA + m)
elif gB > gA and sB <= sA and bB <= bA:
    g = N // gA
    n = N % gA
    n = g * gB + n
    for s in range(n // sB + 1):
        m = n - s * sB
        b = m // bB
        m = m % bB
        ans = max(ans, s * sA + b * bA + m)
elif gB <= gA and sB > sA and bB <= bA:
    s = N // sA
    n = N % sA
    n = s * sB + n
    for g in range(n // gB + 1):
        m = n - g * gB
        b = m // bB
        m = m % bB
        ans = max(ans, g * gA + b * bA + m)
elif gB <= gA and sB <= sA and bB > bA:
    b = N // bA
    n = N % bA
    n = b * bB + n
    for s in range(n // sB + 1):
        m = n - s * sB
        g = m // gB
        m = m % gB
        ans = max(ans, g * gA + s * sA + m)
else:
    for g in range(N // gB + 1):
        n = N - g * gB
        for s in range(n // sB + 1):
            m = n - s * sB
            b = m // bB
            m = m % bB
            ans = max(ans, g * gA + s * sA + b * bA + m)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
GA, SA, BA = map(int, input().split())
GB, SB, BB = map(int, input().split())
rate1 = [(a, b - a) for a, b in ((GA, GB), (SA, SB), (BA, BB)) if a < b]
rate2 = [(b, a - b) for a, b in ((GA, GB), (SA, SB), (BA, BB)) if a > b]


def visit(n, rate):
    if len(rate) == 1:
        m, d = rate[0]
        n += (n // m) * d
    elif len(rate) == 2:
        m1, d1 = rate[0]
        m2, d2 = rate[1]
        ans = 0
        for i in range(n // m1 + 1):
            j = (n - i * m1) // m2
            ans = max(ans, d1 * i + d2 * j)
        n += ans
    elif len(rate) == 3:
        m1, d1 = rate[0]
        m2, d2 = rate[1]
        m3, d3 = rate[2]
        ans = 0
        for i in range(n // m1 + 1):
            for j in range((n - i * m1) // m2 + 1):
                k = (n - i * m1 - j * m2) // m3
                ans = max(ans, d1 * i + d2 * j + d3 * k)
        n += ans
    return n


N = visit(N, rate1)
N = visit(N, rate2)
print(N)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import random
import collections
import math
import itertools

def real_main():
    n = read_int()
    aprice = read_int_array()
    bprice = read_int_array()

    print(solve(n, aprice, bprice))


def solve(n, aprice, bprice):
    ab, ba = [], []
    for i in range(3):
        if aprice[i] < bprice[i]:
            ab.append((aprice[i], bprice[i]))
        elif aprice[i] > bprice[i]:
            ba.append((bprice[i], aprice[i]))

    return aux(ba, aux(ab, n))

def aux(ab, n):
    dp = [0] * (n + 1)
    for w, c in ab:
        for i in range(w, len(dp)):
            dp[i] = max(dp[i], dp[i - w] + c)
    new_n = n
    for i in range(len(dp)):
        new_n = max(new_n, n - i + dp[i])
    return new_n


def main():
    if False and 'PYCHARM_HOSTED' in os.environ:
        main_pycharm()
    else:
        real_main()


from copy import deepcopy
def main_pycharm():
    solution = solve

    test_inputs = None
    test_outputs = None
    judge = None
    slow_solution = None
    if solution is not None:
        if test_outputs is not None:
            test_with_answers(solution, test_inputs, test_outputs)
        if judge is not None:
            test_with_judge(solution, test_inputs, judge)
        if slow_solution is not None:
            test_with_slow_solution(solution, test_inputs, slow_solution)


def test_with_answers(solution, inputs_answers):
    total, wrong = 0, 0
    for args, test_ans in inputs_answers:
        ans = solution(*args.copy())
        if ans != test_ans:
            print('WRONG! ans=%s, test_ans=%s, args=%s' % (ans, test_ans, args))
            wrong += 1
        else:
            print('GOOD')
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_judge(solution, inputs_gen, judge):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        if not judge(deepcopy(ans), *deepcopy(args)):
            print('WRONG! ans=%s, args=%s' % (ans, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_slow_solution(solution, inputs_gen, solution_slow):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        slow = solution_slow(*deepcopy(args))
        if ans != slow:
            print('WRONG! ans=%s, slow=%s, args=%s' % (ans, slow, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

read = input
read_int = lambda: int(input())
read_array = lambda sep=None, maxsplit=-1: input().split(sep, maxsplit)
read_int_array = lambda: [int(a) for a in read_array()]

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
a1, a2, a3 = map(int, input().split())
b1, b2, b3 = map(int, input().split())
A = [a1, a2, a3]
B = [b1, b2, b3]
if (a1<=b1 and a2<=b2 and a3<=b3) or (a1>=b1 and a2>=b2 and a3>=b3):
    if a1>b1 or a2>b2 or a3>b3:
        A, B = B, A
    dp = [[-float("inf")]*(N+1) for _ in range(4)]
    dp[0][0] = 0
    for i in range(3):
        ai = A[i]
        bi = B[i]
        for j in range(N+1):
            if j-ai>=0:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j-ai]+bi)
            else:
                dp[i+1][j] = dp[i][j]
    ans = 0
    for i, v in enumerate(dp[3]):
        ans = max(ans, v+(N-i))
    print(ans)

    #print(dp[3][:30])
else:
    C, D = [], []
    for a, b in zip(A, B):
        if a <= b:
            C.append([a, b])
        else:
            D.append([b, a])

    if len(C)==1:
        a, b = C[0]
        q, n = divmod(N, a)
        N_ = q*b + n
    else:
        N_ = N
        (a1, b1), (a2, b2) = C
        for i in range(N + 1):
            j = N - i
            q1, n1 = divmod(i, a1)
            q2, n2 = divmod(j, a2)
            N_ = max(N_, q1 * b1 + q2 * b2 + n1 + n2)

    if len(D)==1:
        a, b = D[0]
        q, n = divmod(N_, a)
        print(q*b + n)
        #print("a")
    else:
        ans = N_
        (a1, b1), (a2, b2) = D
        for i in range(N_+1):
            j = N_ - i
            q1, n1 = divmod(i, a1)
            q2, n2 = divmod(j, a2)
            ans = max(ans, q1*b1+q2*b2+n1+n2)
        print(ans)

Submission status: Accepted

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

ANS=N

def acorns(N,ga,sa,ba,gb,sb,bb):
    X=[]
    if ga<gb:
        X.append((ga,gb))
    if sa<sb:
        X.append((sa,sb))
    if ba<bb:
        X.append((ba,bb))

    if len(X)==0:
        return N
    
    if len(X)==1:
        ga,gb=X[0][0],X[0][1]
        t=N//ga
        return N-t*ga+t*gb
    
    if len(X)==2:
        ga,gb=X[0][0],X[0][1]
        sa,sb=X[1][0],X[1][1]
        ANS=N
        
        t=N//ga
        for i in range(t+1):
            M=i*gb
            R=N-i*ga
            u=R//sa

            ANS=max(ANS,M+R+u*(sb-sa))
        return ANS
    
    if len(X)==3:
        ga,gb=X[0][0],X[0][1]
        sa,sb=X[1][0],X[1][1]
        ba,bb=X[2][0],X[2][1]
        ANS=N

        t=N//ga
        for i in range(t+1):

            R=N-i*ga
            u=R//sa
            
            for j in range(u+1):
                R2=R-j*sa

                ANS=max(ANS,i*gb+j*sb+R2+R2//ba*(bb-ba))

        return ANS

N2=acorns(N,ga,sa,ba,gb,sb,bb)
print(acorns(N2,gb,sb,bb,ga,sa,ba))

Submission status: Accepted

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

#[重さ,価値]を要素とする配列
lstAB_2 = [[gA, gB-gA], [sA, sB-sA], [bA, bB-bA]]
lstBA_2 = [[gB, gA-gB], [sB, sA-sB], [bB, bA-bB]]
lstAB = []
for i in range(3):
    if lstAB_2[i][1] > 0:
        lstAB += [lstAB_2[i]]  

lstBA = []
for i in range(3):
    if lstBA_2[i][1] > 0:
        lstBA += [lstBA_2[i]]

dp = [[0] * (N+1) for _ in range(len(lstAB)+1)]
for i in range(len(lstAB)):
    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[len(lstAB)][N]
# print (N)

dp2 = [[0] * (N+1) for _ in range(len(lstBA)+1)]
for i in range(len(lstBA)):
    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[len(lstBA)][N])

Submission status: Accepted

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]
    r = sorted(rate, key=lambda r: float(r[0]) / float(r[1]))[0]
    p = n - 10000000
    if p // r[0] > 0:
        d = p // r[0]
        n -= d * r[0]
        dp = [d * r[1]]
    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: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    n = get_int()
    ga, sa, ba = get_li()
    gb, sb, bb = get_li()
    dp1 = [0] * (n + 1)
    dp1[0] = n
    for i in range(1, n + 1):
        _max = dp1[i-1]
        if i - ga >= 0:
            _max = max(_max, dp1[i-ga] + gb - ga)
        if i - sa >= 0:
            _max = max(_max, dp1[i-sa] + sb - sa)
        if i - ba >= 0:
            _max = max(_max, dp1[i-ba] + bb - ba)
        dp1[i] = _max
    n = dp1[n]
    dp2 = [0] * (n + 1)
    dp2[0] = n
    for i in range(1, n + 1):
        _max = dp2[i-1]
        if i - gb >= 0:
            _max = max(_max, dp2[i-gb] + ga - gb)
        if i - sb >= 0:
            _max = max(_max, dp2[i-sb] + sa - sb)
        if i - bb >= 0:
            _max = max(_max, dp2[i-bb] + ba - bb)
        dp2[i] = _max
    print(dp2[n])
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


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


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Accepted

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)

num = (n+1)*(len(w_ab)+1)
dp = [0]*num
for i in range(len(w_ab)):
    for j in range(n+1):
        if j < w_ab[i]:
            dp[(i+1)*(n+1) + j] = dp[i*(n+1) + j]
        else:
            dp[(i+1)*(n+1) + j] = max(dp[i*(n+1) + j], dp[(i+1)*(n+1) + j - w_ab[i]] + v_ab[i])
ans = 0
length = len(w_ab)
for j in range(n+1):
    ans = max(ans, dp[length*(n+1) + j] + n-j)
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)

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

length = len(w_ab)
ans = 0
for j in range(n+1):
    ans = max(ans, dp[length*(n+1) + j] + n-j)
print(ans)

Submission status: Accepted

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

    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 = [0]*(n+1)
    if len(ab) > 0:
        for i in range(n+1):
            dp[i] = i
            for x,y in ab:
                if i >= x:
                    dp[i] = max(dp[i],dp[i-x]+y)
    p = max(n,dp[n])

    dp2 = [0]*(p+1)

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

Submission status: Accepted

Solution code:
N = int(input())
Ga, Sa, Ba = map(int, input().split())
Gb, Sb, Bb = map(int, input().split())

dp = [0]
for i in range(1, N+1):
  tmp = dp[-1] + 1
  if Ga <= i:
    t2 = dp[-Ga] + Gb
    tmp = tmp if tmp > t2 else t2
  if Sa <= i:
    t2 = dp[-Sa] + Sb
    tmp = tmp if tmp > t2 else t2
  if Ba <= i:
    t2 = dp[-Ba] + Bb
    tmp = tmp if tmp > t2 else t2
  dp.append(tmp)
N2 = dp[-1]

dp = [0]
for i in range(1, N2+1):
  tmp = dp[-1] + 1
  if Gb <= i:
    t2 = dp[-Gb] + Ga
    tmp = tmp if tmp > t2 else t2
  if Sb <= i:
    t2 = dp[-Sb] + Sa
    tmp = tmp if tmp > t2 else t2
  if Bb <= i:
    t2 = dp[-Bb] + Ba
    tmp = tmp if tmp > t2 else t2
  dp.append(tmp)
print(dp[-1])

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
C=[(B[i]-A[i],A[i],B[i]) for i in range(3)]
C.sort()
ans=0
#print(C)
if C[2][0]<=0:
  for i in range(3):
    C[i]=(A[i]-B[i],B[i],A[i])
  C.sort()
  A,B=B,A
#print(A,B)

if C[0][0]>=0:
  for p in range(N+1):
    for q in range(N+1):
      if p*A[0]+q*A[1]<=N:
        r=(N-p*A[0]-q*A[1])//A[2]
        s=N-(p*A[0]+q*A[1]+r*A[2])
        ans=max(ans,p*B[0]+q*B[1]+r*B[2]+s)
elif C[0][0]<0 and C[1][0]>=0:
  for p in range(N+1):
    if p*C[1][1]<=N:
      q=(N-C[1][1]*p)//C[2][1]
      s=N-(p*C[1][1]+q*C[2][1])
      n=p*C[1][2]+q*C[2][2]+s
      r,m=n//C[0][2],n-C[0][2]*(n//C[0][2])
      n=m+C[0][1]*r
      ans=max(ans,n)
else:
  r,m=N//C[2][1],N-C[2][1]*(N//C[2][1])
  N_=m+C[2][2]*r
  for p in range(N_+1):
    if p*C[0][2]<=N_:
      q=(N_-C[0][2]*p)//C[1][2]
      s=N_-(p*C[0][2]+q*C[1][2])
      n=p*C[0][1]+q*C[1][1]+s
      #print(p,q,s,n)
      ans=max(ans,n)
        
  
    
print(ans)

Submission status: Accepted

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):
    if len(AB_use) == 1:
        w, v = AB_use[0]
        ans = v * (ans//w) + (ans % w)
    else:
        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):
    if len(BA_use) == 1:
        w, v = BA_use[0]
        ans = v * (ans//w) + (ans % w)
    else:
        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: Accepted

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

def calc(n, X, Y):
    Z = [(X[i], Y[i]) for i in range(3) if Y[i] > X[i]]
    k = len(Z)
    if k == 0:
        return n
    if k == 1:
        a = n//Z[0][0]
        return n + a*(Z[0][1]-Z[0][0])
    if k == 2:
        ma = 0
        for a in range(n+1):
            b = (n-a*Z[0][0])//Z[1][0]
            if b >= 0:
                ma = max(ma, n + a*(Z[0][1]-Z[0][0]) + b*(Z[1][1]-Z[1][0]))
        return ma
    ma = 0
    for a in range(n+1):
        for b in range(n+1-a):
            c = (n-a*Z[0][0]-b*Z[1][0])//Z[2][0]
            if c >= 0:
                ma = max(ma, n + a*(Z[0][1]-Z[0][0]) + b*(Z[1][1]-Z[1][0]) + c*(Z[2][1]-Z[2][0]))
    return ma

print(calc(calc(N, A, B), B, A))

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]
    get_back = B[j]
    if get_back > sell:
        for i in reversed(range(sell,len(DP))):
            val1 = DP[i - sell]
            val2 = DP[i] + get_back - sell
            if val2 > val1:
                DP[i-sell] = val2
n = max(DP)
A,B = B,A

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

print(max(DP))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = tuple(map(int, input().split()))
b = tuple(map(int, input().split()))
dp = [0] * (N + 1)
res = 0
for i in range(N, -1, -1):
  for j in range(3):
    if a[j] < b[j] and (i - a[j] >= 0): dp[i - a[j]] = max(dp[i - a[j]], dp[i] + b[j])
  res = max(res, i + dp[i])
#print(res)
d = []
for i in range(3):
  if a[i] > b[i]: d.append((b[i], a[i]))
if len(d) == 0: print(res)
elif len(d) == 1:
  res = res // d[0][0] * d[0][1] + res % d[0][0]
  print(res)
elif len(d) == 2:
  dp = [0] * (res + 1)
  rres = 0
  for i in range(res, -1, -1):
    for x, y in d:
      if i - x >= 0: dp[i - x] = max(dp[i - y], dp[i] + y)
    rres = max(rres, i + dp[i])
  print(rres)
else:
  dp = [0] * (res + 1)
  rres = 0
  for i in range(res, -1, -1):
    for j in range(3):
      if a[j] > b[j] and (i - b[j] >= 0): dp[i - b[j]] = max(dp[i - b[j]], dp[i] + a[j])
    rres = max(rres, i + dp[i])
  print(rres)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = tuple(map(int, input().split()))
b = tuple(map(int, input().split()))
dp = [0] * (N + 1)
res = 0
for i in range(N, -1, -1):
  for j in range(3):
    if a[j] < b[j] and (i - a[j] >= 0): dp[i - a[j]] = max(dp[i - a[j]], dp[i] + b[j])
  res = max(res, i + dp[i])
#print(res)
d = []
for i in range(3):
  if a[i] > b[i]: d.append((b[i], a[i]))
if len(d) == 0: print(res)
elif len(d) == 1:
  res = res // d[0][0] * d[0][1] + res % d[0][0]
  print(res)
elif len(d) == 2:
  dp = [0] * (res + 1)
  rres = 0
  for i in range(res, -1, -1):
    for x, y in d:
      if i - x >= 0: dp[i - x] = max(dp[i - y], dp[i] + y)
    rres = max(rres, i + dp[i])
  print(rres)
else:
  dp = [0] * (res + 1)
  for i in range(res, -1, -1):
    for j in range(3):
      if a[j] > b[j] and (i - b[j] >= 0): dp[i - b[j]] = max(dp[i - b[j]], dp[i] + a[j])
    res = max(res, i + dp[i])
  print(res)

Submission status: Runtime Error

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

n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
def f(n):
  dp = list(range(n+1))
  for a, b in zip(A, B):
    if b <= a:
      continue
    for i in range(n+1):
      if i-a >= 0:
        dp[i] = max(dp[i], dp[i-a]+b)
  return max(dp[n])
m = f(n)
A, B = B, A
ans = f(m)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

def solve(n, a, b):
  ab = [(ai, bi) for ai, bi in zip(a, b) if ai < bi]
  dp = [[j for j in range(n+1)] for i in range(len(ab)+1)]
  if len(ab) == 0:
    return n
  if len(ab) == 1:
    a0, b0 = ab[0]
    return (n//a0)*b0 + n%a0
  if len(ab) == 2:
    a0, b0 = ab[0]; a1, b1 = ab[1]
    if a0 < a1: a0, b0, a1, b1 = a1, b1, a0, b0
    t = n // a0
    return max(((n-a0*i)//a1)*b1 + (n-a0*i)%a1 + i*bi for i in range(t+1))
  else:
    dp = np.arange(n+1)
    for ai, bi in ab:
      dp[ai:] = np.maximum(dp[ai:], dp[:-ai]+bi)
    return dp[-1]

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

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