Problem:


Score : 400 points

Problem Statement

Dolphin is planning to generate a small amount of a certain chemical substance C.

In order to generate the substance C, he must prepare a solution which is a mixture of two substances A and B in the ratio of M_a:M_b.

He does not have any stock of chemicals, however, so he will purchase some chemicals at a local pharmacy.

The pharmacy sells N kinds of chemicals. For each kind of chemical, there is exactly one package of that chemical in stock.

The package of chemical i contains a_i grams of the substance A and b_i grams of the substance B, and is sold for c_i yen (the currency of Japan).

Dolphin will purchase some of these packages. For some reason, he must use all contents of the purchased packages to generate the substance C.

Find the minimum amount of money required to generate the substance C.

If it is not possible to generate the substance C by purchasing any combination of packages at the pharmacy, report that fact.  

Constraints

1≦N≦40 

1≦a_i,b_i≦10 

1≦c_i≦100 

1≦M_a,M_b≦10 

gcd(M_a,M_b)=1

a_i, b_i, c_i, M_a and M_b are integers.

Input

The input is given from Standard Input in the following format:

N M_a M_b  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_N b_N c_N  

Output

Print the minimum amount of money required to generate the substance C. If it is not possible to generate the substance C, print -1 instead.

Sample Input 1

3 1 1
1 2 1
2 1 2
3 3 10

Sample Output 1

3

The amount of money spent will be minimized by purchasing the packages of chemicals 1 and 2.

In this case, the mixture of the purchased chemicals will contain 3 grams of the substance A and 3 grams of the substance B, which are in the desired ratio: 3:3=1:1.

The total price of these packages is 3 yen.  

Sample Input 2

1 1 10
10 10 10

Sample Output 2

-1

The ratio 1:10 of the two substances A and B cannot be satisfied by purchasing any combination of the packages. Thus, the output should be -1.



Sample input:
3 1 1
1 2 1
2 1 2
3 3 10


Sample output:
3

Submission status: Accepted

Solution code:
n, A, B = map(int, input().split())
z = [tuple(map(int, input().split())) for _ in range(n)]

inf = 10 ** 18

d = {(0, 0):0}
for a, b, cost in z:
    newd = []
    for (x, y), c in d.items():
        new = (a+x, b+y)
        if new not in d or d[new] > c + cost:
            newd.append((new, c+cost))
    for new, newc in newd:
        d[new] = newc

ans = inf
for i in range(1, 10 * n):
    t = (A * i, B * i)
    if t in d:
        ans = min(ans, d[t])
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
INF = 10**18

N, Ma, Mb = map(int, input().split())

dp = [[[INF for k in range(401)] for j in range(401)] for i in range(N + 1)]
dp[0][0][0] = 0

for i in range(N):
    a, b, c = map(int, input().split())
    for j in range(400):
        for k in range(400):
            dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])
            if j + a <= 400 and k + b <= 400:
                dp[i + 1][j + a][k + b] = min(dp[i + 1][j + a][k + b], dp[i][j][k] + c)

res = INF

for j in range(1, 401):
    for k in range(1, 401):
        if k * Ma == j * Mb:
            res = min(res, dp[N][j][k])

print(res if res != INF else -1)

Submission status: Accepted

Solution code:
INF = 10**18

def solve(N, Ma, Mb, sol):
    if N % 2 == 1:
        sol.append((0, 0, 0))
        N += 1

    M = N // 2

    sol1 = sol[:M]
    sol2 = sol[M:]

    S1 = []
    D = dict()
    res = INF

    for i in range(2**M):
        A1, B1, C1 = 0, 0, 0
        A2, B2, C2 = 0, 0, 0
        for j in range(M):
            if (i >> j) & 1:
                a1, b1, c1 = sol1[j]
                a2, b2, c2 = sol2[j]
                A1 += a1
                B1 += b1
                C1 += c1
                A2 += a2
                B2 += b2
                C2 += c2
        S1.append((A1, B1, C1))
        x = Mb * A2 - Ma * B2
        if x == 0 and C2 > 0:
            res = min(res, C2)
        if not x in D or 0 < C2 < D[x]:
            D[x] = C2

    for i in range(2**M):
        a, b, c = S1[i]
        x = Ma * b - Mb * a
        if x == 0 and c > 0:
            res = min(res, c)
        if x in D and D[x] + c > 0:
            res = min(res, D[x] + c)

    return res

N, Ma, Mb = map(int, input().split())
sol = [tuple(map(int, input().split())) for _ in range(N)]

res = solve(N, Ma, Mb, sol)

print(res if res != INF else -1)

Submission status: Accepted

Solution code:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline


#N=int(input())

N,Ma,Mb=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(N)]
idle_max=10**9
dp=[[[idle_max for b in range(400)] for a in range(400)] for i in range(N)]
used=set()
a,b,c=ABC[0]
dp[0][a][b]=c

for n in range(1,N):
    a,b,c=ABC[n]

    for x in range(400):
        for y in range(400):
            if x-a>=0 and y-b>=0 and dp[n-1][x-a][y-b]!=idle_max:
                dp[n][x][y]=min(dp[n-1][x-a][y-b]+c,dp[n-1][x][y])
            else:
                dp[n][x][y]=dp[n-1][x][y]
    dp[n][a][b]=min(dp[n-1][a][b],c)
value=idle_max
for x in range(1,400):
    for y in range(1,400):
        z=gcd(x,y)
        a=x//z;b=y//z
        if Ma==a and Mb==b:
            value=min(dp[-1][x][y],value)

if value!=idle_max:
    print(value)
else:
    print(-1)

Submission status: Accepted

Solution code:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline


#N=int(input())

N,Ma,Mb=map(int,input().split())
ABC=[list(map(int,input().split())) for i in range(N)]
idle_max=10**9
dp=[[idle_max for m in range(403*400)] for i in range(N)]
used=set()
a,b,c=ABC[0]
dp[0][a*401+b]=c
for n in range(1,N):
    a,b,c=ABC[n]
    for i in range(len(dp[0])):
        if i-(a*401+b)>=0 and dp[n-1][i-(a*401+b)]!=idle_max:
            dp[n][i]=min(dp[n-1][i-(a*401+b)]+c,dp[n-1][i])
        else:
            dp[n][i]=dp[n-1][i]
    dp[n][a*401+b]=min(dp[n-1][a*401+b],c)

value=idle_max
for i in range(len(dp[0])):
    if dp[-1][i]:
        A=i//401;B=i%401
        if A and B:
            Z=gcd(A,B)
            A//=Z;B//=Z
            if Ma==A and Mb==B:
                value=min(value,dp[-1][i])
if value!=idle_max:
    print(value)
else:
    print(-1)

Submission status: Accepted

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,Ma,Mb=MI()
    a=[0]*N
    b=[0]*N
    c=[0]*N
    cab=[[0,0,0] for _ in range(N)]
    for i in range(N):
        cab[i][1],cab[i][2],cab[i][0]=MI()
    cab.sort()
    for i in range(N):
        a[i]=cab[i][1]
        b[i]=cab[i][2]
        c[i]=cab[i][0]
        
    
    inf=10**5
    #dp[i][j][k]はi番目の商品まででaがjg,bがkgをとるときの最低金額
    dp=[[[inf]*(N*10+1) for _ in range(N*10+1)] for i in range(N+1)]
    dp[0][0][0]=0
    
    ans=inf
    for i in range(N):
        for j in range(N*10+1-a[i]):
            for k in range(N*10+1-b[i]):
                if dp[i][j][k]!=inf:
                    dp[i+1][j][k]=dp[i][j][k]
                    dp[i+1][j+a[i]][k+b[i]]=min(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i])
                    if (j+a[i])*Mb==(k+b[i])*Ma:
                        ans=min(ans,dp[i+1][j+a[i]][k+b[i]])
                    
    if ans==inf:
        print(-1)
    else:
        print(ans)
    
    
    

main()

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,ma,mb = inm()
a = []
b = []
c = []
for i in range(n):
    aa,bb,cc = inm()
    a.append(aa)
    b.append(bb)
    c.append(cc)
dp = [[BIG]*(10+1) for i in range(10+1)]
dp[0][0] = 0
for t in range(n):
    dp2 = [[BIG]*(10*(t+1)+1) for i in range(10*(t+1)+1)]
    for i in range(10*t+1):
        for j in range(10*t+1):
            if dp[i][j]<BIG:
                dp2[i][j] = min(dp2[i][j],dp[i][j])
                dp2[i+a[t]][j+b[t]] = min( \
                     dp2[i+a[t]][j+b[t]], dp[i][j]+c[t])
    dp = dp2
mn = BIG
for i in range(1,5000):
    if i*max(ma,mb)>n*10:
        break
    #ddprint(f"i {i} n {n} ma {ma} mb {mb} ima {i*ma}")
    mn = min(mn, dp[i*ma][i*mb])
print(-1 if mn==BIG else mn)

Submission status: Accepted

Solution code:

N, Ma, Mb = map(int,input().split())
rate = Ma / Mb
a = [0] * N
b = [0] * N
c = [0] * N
MA = 0
MB = 0
MC = 0
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
    MA += a[i]
    MB += b[i]
    MC += c[i]
    
dp = [[[MC for i in range(MB+1)] for j in range(MA+1)] for k in range(N+1)]
dp[0][0][0] = 0

for it_N in range(N):
    for it_MA in range(MA+1):
        for it_MB in range(MB+1):
            if it_MA >= a[it_N] and it_MB >= b[it_N]:
                if dp[it_N][it_MA-a[it_N]][it_MB-b[it_N]] != MC:
                    dp[it_N+1][it_MA][it_MB] = min(dp[it_N][it_MA-a[it_N]][it_MB-b[it_N]] + c[it_N], dp[it_N][it_MA][it_MB])
                else:
                    dp[it_N+1][it_MA][it_MB]=dp[it_N][it_MA][it_MB]
            else:
                dp[it_N+1][it_MA][it_MB]=dp[it_N][it_MA][it_MB]

ans = -1
for a in range(1, MA+1):
    for b in range(1, MB+1):
        if a/b == rate and dp[N][a][b] != MC:
            if ans == -1:
                ans = dp[N][a][b]
            else:
                ans = min(dp[N][a][b], ans)
print(ans)

Submission status: Accepted

Solution code:
n,ma,mb = map(int, input().split())
l = []
for i in range(n):
    l.append(list(map(int,input().split())))

dp = [[[10**10 for _ in range(430)] for _ in range(430)] for _ in range(45)]

dp[0][0][0] = 0

for i in range(n):
    a=l[i][0]
    b=l[i][1]
    c=l[i][2]
    for j in range(410):
        for k in range(410):
            dp[i+1][j][k] = min(dp[i+1][j][k] ,dp[i][j][k])
            dp[i+1][j+a][k+b] =min(dp[i+1][j+a][k+b], dp[i][j][k] +c)

ans=10**10
for j in range(1,410):
    for k in range(1,410):
        if ma*k == mb*j:
            ans=min(ans,dp[n][j][k])
if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

def main():
    N,A,B = map(int,input().split())
    INF = 10**10
    dp = np.full((N+1,10*N+1,10*N+1),INF)
    dp[0][0][0] = 0
    
    for i in range(N):
        a,b,c = map(int,input().split())
        dp[i+1][a:,b:] = np.minimum(dp[i][a:,b:],dp[i][:10*N+1-a,:10*N+1-b]+c)
        dp[i+1] = np.minimum(dp[i],dp[i+1])
    
    ans = INF
    x,y = A,B
    while x < 10*N+1 and y < 10*N+1:
        ans = min(ans,dp[N][x][y])
        x += A
        y += B
        
    print(int(ans) if ans != INF else -1)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N,A,B = map(int,input().split())
    INF = 10**10
    dp = np.full((N+1,10*N+2,10*N+2),INF)
    dp[0][0][0] = 0
    
    for i in range(N):
        a,b,c = map(int,input().split())
        dp[i+1][a:,b:] = np.minimum(dp[i][a:,b:],dp[i][:10*N+2-a,:10*N+2-b]+c)
        dp[i+1] = np.minimum(dp[i],dp[i+1])
    
    ans = INF
    x,y = A,B
    while x <= 10*N+1 and y <= 10*N+1:
        ans = min(ans,dp[N][x][y])
        x += A
        y += B
        
    print(int(ans) if ans != INF else -1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
n, ma, mb = map(int, input().split())
r = 10 * n + 6
inf = 10**5
dp = np.full((n+1, r, r), inf)
dp[0][0][0] = 0
for i in range(n):
    a, b, c = map(int, input().split())
    dp[i+1][a:, b:] = np.minimum(
        dp[i][:r-a, :r-b] + c, dp[i][a:, b:]
    )
    dp[i+1] = np.minimum(dp[i+1], dp[i])

ans = inf
x, y = 0, 0
while True:
    x += ma
    y += mb
    if x < r and y < r:
        ans = min(ans, dp[n][x][y])
    else:
        break
if ans == inf:
    print(-1)
else:
    print(int(ans))

Submission status: Accepted

Solution code:
n,ma,mb = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
#dp[i][j][k] := i番目まで考えたとき,薬品がjg, kgになる最小コスト
inf = 10**9
dp = [[[inf for i in range(n*11)] for j in range(n*11)] for k in range(n+1)]
for i in range(n):
    #0g, 0g にするためのコストは0
    dp[i][0][0] = 0
for i in range(1,n+1):
    typeA,typeB,cost = data[i-1]
    for j in range(n*11-typeA):
        for k in range(n*11-typeB):
            if dp[i][j+typeA][k+typeB] > dp[i-1][j][k] + cost:
                dp[i][j+typeA][k+typeB] = dp[i-1][j][k] + cost
            dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k])
ans = inf
for i in range(1,n*11):
    for j in range(1,n*11):
        if i / j == ma / mb:
            #print("{} {} {}".format(i,j,dp[n][i][j]))
            ans = min(ans, dp[n][i][j])
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,ma,mb = map(int,input().split())
abc = [list(map(int,input().split())) for i in range(n)]
dp = [[[10000 for i in range(n*10+1)] for j in range(n*10+1)] for k in range(n+1)]
for i in range(n+1):
  dp[i][0][0] = 0
for i in range(1,n+1):
  x,y,c = abc[i-1]
  for j in range(1,n*10+1):
    for k in range(1,n*10+1):
      if j>=x and k>=y:
        dp[i][j][k] = min(dp[i][j][k],dp[i-1][j][k],dp[i-1][j-x][k-y]+c)
      else:
        dp[i][j][k] = min(dp[i][j][k],dp[i-1][j][k])
ans = 10000000
for i in range(1,n*10+1):
  for j in range(1,n*10+1):
    if i*mb == j*ma:
      ans = min(ans,dp[n][i][j])
if ans == 10000:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
N, Ma, Mb = map(int, input().split())
abc = []
for i in range(N):
    a, b, c = map(int, input().split())
    abc.append([a, b, c])

W = max([Ma, Mb])*(N+1)
C = 100*(N+1)

dp = [[[10000]*W for _ in range(W)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(1, N+1):
    a, b, c = abc[i-1]
    for j in range(W):
        for k in range(W):
            if (j-a) < 0 or (k-b) < 0:
                dp[i][j][k] = dp[i-1][j][k]
            else:
                dp[i][j][k] = min([
                    dp[i-1][j][k],
                    dp[i-1][j-a][k-b]+c
                ])

ans = C
ma, mb = Ma, Mb
while ma < W and mb < W:
    t = dp[N][ma][mb]
    if t < ans:
        ans = t
    ma += Ma
    mb += Mb

print(ans if ans < C else -1)

Submission status: Accepted

Solution code:
# 半分全列挙バージョン
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def allptn(abc,ma,mb):
    inf=10**9
    # a,b,cの全組合せを作る
    allabc=[(0,0,0)]
    for a,b,c in abc:
        n=len(allabc)
        for i in range(n):
            aa,bb,cc=allabc[i]
            allabc.append((aa+a,bb+b,cc+c))
    # 指標とコストの組合せにする
    # 指標が重複するときはコストが小さいほうだけ残す
    # 指標が0のときは前後半で組み合わせる必要がないので単独で答えを出しておく
    vc={}
    ans=inf
    for a,b,c in allabc[1:]:
        val=a*mb-b*ma
        if val:
            pc=vc.setdefault(val,inf)
            if c<pc:vc[val]=c
        else:
            if c<ans:ans=c
    res=[(val,c) for val,c in sorted(vc.items())]
    return ans,res

def main():
    n,ma,mb=MI()
    abc=[LI() for _ in range(n)]
    inf=10**9
    # 前半の要素をa1,b1、後半の要素をa2,b2とする
    # (a1+a2):(b1+b2)=ma:mbとなればよい。式変形すると
    # (mb*a1-ma*b1)+(mb*a2-ma*b2)=0となる
    # つまり各要素についてmb*a-ma*bという指標を計算し、前半と後半で和が0になる組合せを探せばよい
    # 前半全列挙
    ans,pre=allptn(abc[:n//2],ma,mb)
    # 後半全列挙
    ret,pos=allptn(abc[n//2:],ma,mb)
    ans=min(ans,ret)
    # 指標が昇順になるよう並び替えて、前半は前から後半は後からしゃくとり法で
    # 指標の和が0になるところのコストを求める
    j=len(pos)-1
    for val,c in pre:
        while val+pos[j][0]>0 and j:j-=1
        if val+pos[j][0]==0:ans=min(ans,c+pos[j][1])
    if ans==inf:print(-1)
    else:print(ans)

main()

Submission status: Accepted

Solution code:
import numpy as np
N, ma, mb = map(int, input().split())
abc = tuple(map(int, input().split()) for _ in range(N))

inf = 10000
dp = np.full((401, 401), inf, dtype=int)
dp[0][0] = 0

for a, b, c in abc:
    for i in range(400, a - 1, -1):
        dp[i][b:] = np.minimum(dp[i][b:], dp[i - a][: - b] + c)

ans = inf
x = 1

while True:
    Ma = x * ma
    Mb = x * mb
    if Ma > 400 or Mb > 400:
        break
    ans = min(ans, dp[Ma][Mb])
    x += 1

ans = -1 if ans >= inf else ans
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,ma,mb=MI()
    inf=10**9
    abc=[LI() for _ in range(n)]
    dp=[[[inf]*(n*10+1) for _ in range(10*n+1)] for _ in range(n+1)]
    dp[0][0][0]=0
    for i,(a,b,c) in enumerate(abc):
        for j in range(n*10+1):
            for k in range(n*10+1):
                pre=dp[i][j][k]
                if pre==inf:continue
                dp[i+1][j][k]=min(dp[i+1][j][k],pre)
                dp[i+1][j+a][k+b]=min(dp[i+1][j+a][k+b],pre+c)
    ans=inf
    for i in range(1,105):
        a=i*ma
        b=i*mb
        if a>n*10 or b>n*10:break
        ans=min(ans,dp[n][a][b])
    if ans==inf:print(-1)
    else:print(ans)

main()

Submission status: Accepted

Solution code:
import numpy as np

n, ma, mb = map(int, input().split())
U = 400
dp = np.full((U+1, U+1), float("inf"))
dp[0, 0] = 0
for i in range(n):
  a, b, c = map(int, input().split())
  np.minimum(dp[a:, b:], dp[:-a, :-b]+c, out=dp[a:, b:])
ans = float("inf")
for i in range(1, 1+U//max(ma, mb)):
  na, nb = i*ma, i*mb
  ans = min(ans, dp[na, nb])
if ans == float("inf"):
  print(-1)
else:
  print(int(ans))

Submission status: Accepted

Solution code:
n,ma,mb=map(int,input().split())
INF=10**17
dp=[[[INF]*(10*n+1) for i in range(10*n+1)] for j in range(n+1)]
dp[0][0][0]=0
ans=10**17
for i in range(n):
  a,b,c=map(int,input().split())
  for j in range(10*n+1):
    for k in range(10*n+1):
      if dp[i][j][k]!=INF:
        dp[i+1][j+a][k+b]=min(dp[i+1][j+a][k+b],dp[i][j][k]+c)
      dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k])
for i in range(1,10*n+1):
  for j in range(1,10*n+1):
    if i*mb==j*ma:
      ans=min(ans,dp[n][i][j])
if ans==INF:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
INF = 10**10

n,ma,mb = map(int, input().split())
dp = [[[INF] * 500 for i in range(500)] for i in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
    a,b,c = map(int, input().split())
    for w_a in range(500):
        for w_b in range(500):
            dp[i+1][w_a][w_b] = dp[i][w_a][w_b]
    for w_a in range(500):
        for w_b in range(500):
            if dp[i][w_a][w_b] == INF : continue
            dp[i+1][w_a+a][w_b+b] = min(dp[i][w_a+a][w_b+b], dp[i][w_a][w_b]+c)

a = 0
b = 0
dp[n][0][0] = INF
# ma.mbは互いに素
ans = INF
while a < 500 and b < 500:
    ans = min(ans,dp[n][a][b])
    a += ma
    b += mb
if ans == INF:
    print(-1)
else:print(ans)

Submission status: Accepted

Solution code:
INFTY = 10**4
N,Ma,Mb = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
dp = [[[INFTY for _ in range(401)] for _ in range(401)] for _ in range(N+1)]
dp[0][0][0] = 0
for i in range(1,N+1):
    for j in range(401):
        for k in range(401):
            dp[i][j][k] = dp[i-1][j][k]
            a = A[i-1][0]
            b = A[i-1][1]
            c = A[i-1][2]
            if j>=a and k>=b:
                dp[i][j][k] = min(dp[i][j][k],dp[i-1][j-a][k-b]+c)
cmin = INFTY
for j in range(1,401):
    for k in range(1,401):
        if j*Mb==k*Ma:
            cmin = min(cmin,dp[N][j][k])
if cmin>=INFTY:
    print(-1)
else:
    print(cmin)

Submission status: Accepted

Solution code:
import numpy as np
N, Ma, Mb = map(int, input().split())
ls = []
dp = np.full((1001,1001),float('inf'))
dp[0][0] = 0
for i in range(N):
  a,b,c = map(int, input().split())
  dp[a:,b:] = np.minimum(dp[:1001-a,:1001-b]+c, dp[a:,b:])
ans = float('inf')
for i in range(1,1001):
  if i*Ma>1000 or i*Mb>1000:
    break
  if dp[i*Ma,i*Mb]<ans:
    ans = dp[i*Ma,i*Mb]
if ans==float('inf'):
  ans = -1
print(int(ans))

Submission status: Accepted

Solution code:
N, Ma, Mb = map(int, input().split())
a = [0]*N
b = [0]*N
c = [0]*N
INF = 10000


for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())

#dp[i][j][k]...i番目までの品物で, タイプAの物質をjグラム, タイプBの物質をkグラム調達するのに必要な費用の最小値

dp = [[[INF]*400 for _ in range(400)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(1, N+1):
    for j in range(400):
        for k in range(400):
            if j < a[i-1] or k < b[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            else:
                dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][j-a[i-1]][k-b[i-1]]+c[i-1])

ans = INF

for i in range(1, N+1):
    for j in range(1, 400):
        for k in range(1, 400):
            if j*Mb == k*Ma:
                ans = min(ans, dp[i][j][k])
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
ab=[[float('inf') for j in range(401)] for i in range(401)]
n,ma,mb=map(int,input().split())
a,b,c=map(int,input().split())
ab[a][b]=c
ab[0][0]=0
for i in range(n-1):
    a,b,c=map(int,input().split())
    for j in range(400,-1,-1):
        for k in range(400,-1,-1):
            if ab[j][k]!=float('inf'):
                ab[j+a][k+b]=min(ab[j][k]+c,ab[j+a][k+b])
ans=float('inf')
a,b=ma,mb
while a<401 and b<401:
    ans=min(ans,ab[a][b])
    a+=ma
    b+=mb
if ans==float('inf'):
    ans=-1
print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
n,ma, mb = map(int, input().split())
abc = []
inf = float('INF')
hw = 400 + 1
dp = [[inf for i in range(hw)] for j in range(hw)]
dp[0][0] = 0
for _ in range(n):
    a,b,c = map(int, input().split())
    abc.append((a,b,c))

abc.sort(key = lambda x:(-x[0],x[1]))
for a,b,c in abc:
    for i in range(hw-a)[::-1]:
        for j in range(hw-b)[::-1]:
            if dp[i+a][j+b] > dp[i][j] + c:
                dp[i+a][j+b] = dp[i][j] + c

a,b = ma, mb
ans = [dp[a*i][b*i] for i in range(1,hw // max(a,b)) if dp[a*i][b*i] < inf]
print(min(ans) if len(ans) else -1)
# [print(i, f) for i,f in enumerate(dp[200:])]
# print(ans)

Submission status: Accepted

Solution code:
N, Ma, Mb = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(N)]
INF = float("inf")
DP = [[[INF] * (11*N+1) for _ in range(11*N+1)] for _ in range(N+1)]
DP[0][0][0] = 0
for i, (a, b, c) in enumerate(ABC):
    for j in range(10*N+1):
        for k in range(10*N+1):
            if DP[i][j][k] == INF: continue
            DP[i+1][j][k] = min(DP[i+1][j][k], DP[i][j][k])
            DP[i+1][j+a][k+b] = min(DP[i+1][j+a][k+b], DP[i][j][k] + c)
ans = INF
for j in range(1,10*N+1):
    for k in range(1,10*N+1):
        if Ma * k == Mb * j:
            ans = min(ans, DP[N][j][k])
if ans == INF:
    ans = -1
print(ans)

Submission status: Accepted

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

N, Ma, Mb = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(N)]

sumA = sum([ABC[i][0] for i in range(N)])
sumB = sum([ABC[i][1] for i in range(N)])

INF = 10 ** 15
dp = [[INF for j in range(sumB + 1)] for i in range(sumA + 1)]
dp[0][0] = 0

for a, b, c in ABC:
  for i in range(sumA, -1, -1):
    for j in range(sumB, -1, -1):
      if dp[i][j] != INF:
        dp[i + a][j + b] = min(dp[i + a][j + b], dp[i][j] + c)

answer = INF
for i in range(1, sumA + 1):
  for j in range(1, sumB + 1):
    if dp[i][j] != INF and i / j == Ma / Mb:
      answer = min(answer, dp[i][j])
      
print(answer if answer != INF else -1)

Submission status: Accepted

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

N, Ma, Mb = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(N)]

INF = 10 ** 15
dp = [[INF for j in range(401)] for i in range(401)]
dp[0][0] = 0

for a, b, c in ABC:
  for i in range(400, -1, -1):
    for j in range(400, -1, -1):
      if dp[i][j] != INF:
        dp[i + a][j + b] = min(dp[i + a][j + b], dp[i][j] + c)

answer = INF
for i in range(1, 401):
  for j in range(1, 401):
    if dp[i][j] != INF and i / j == Ma / Mb:
      answer = min(answer, dp[i][j])
      
print(answer if answer != INF else -1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7
INF = int(1e09)


def main():
    # sys.stdin = open("sample.txt")
    N, Ma, Mb = Scanner.map_int()
    A = [0] * N
    B = [0] * N
    C = [0] * N

    for i in range(N):
        a, b, c = Scanner.map_int()
        A[i], B[i], C[i] = a, b, c
    dp = [[[INF for _ in range(401)] for _ in range(401)] for _ in range(41)]
    dp[0][0][0] = 0
    for i in range(N):
        for j in range(401):
            for k in range(401):
                if dp[i][j][k] == INF:
                    continue
                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
                dp[i+1][j + A[i]][k + B[i]] = min(
                    dp[i+1][j + A[i]][k + B[i]], dp[i][j][k] + C[i])

    ans = INF
    for i in range(1, 401):
        for j in range(1, 401):
            if dp[N][i][j] == INF:
                continue
            if Ma * j == Mb * i:
                ans = min(ans, dp[N][i][j])
    if ans == INF:
        ans = -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, Ma, Mb = map(int, input().split())

items = []
mas = []
mbs = []
costs = []
for i in range(N):
  ma, mb, c = map(int, input().split())
  mas.append(ma)
  mbs.append(mb)
  costs.append(c)

max_cost = 5000
dp = [[[max_cost for k in range((N+1)*10)] for j in range((N+1)*10)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
  for j in range(N*10):
    for k in range(N*10):
      if dp[i][j][k] == max_cost:
        continue
      if dp[i+1][j][k] > dp[i][j][k]:
        dp[i+1][j][k] = dp[i][j][k]
      if dp[i+1][j+mas[i]][k+mbs[i]] > dp[i][j][k] + costs[i]:
        dp[i+1][j+mas[i]][k+mbs[i]] = dp[i][j][k] + costs[i]
        
min_cost = max_cost
for wa in range(1, N*10):
  for wb in range(1, N*10):
    if (wa * Mb != wb * Ma):
      continue;
    if min_cost > dp[N][wa][wb]:
      min_cost = dp[N][wa][wb]

  
if min_cost == max_cost:
  print("-1")
else:
  print(min_cost)

Submission status: Accepted

Solution code:
import fractions


def args():
    N, MA, MB = list(map(int, input().split()))

    A, B, C = [], [], []
    for i in range(N):
        a, b, c = list(map(int, input().split()))
        A.append(a)
        B.append(b)
        C.append(c)

    # print(N, MA, MB)
    # print(A)
    # print(B)
    # print(C)

    return N, MA, MB, A, B, C

def solve(N, MA, MB, A, B, C):
    def recur(i, a, b):
        if not MEMO[i][a][b] is None:
            return MEMO[i][a][b]

        if not i < N:
            if 0 < a and 0 < b:
                g = fractions.gcd(a, b)
                if (MA, MB) == (a / g, b / g):
                    return 0
            return float("inf")

        res = min(recur(i + 1, a, b) + 0, recur(i + 1, a + A[i], b + B[i]) + C[i])
        MEMO[i][a][b] = res
        return res

    x, y, z = N + 1, 10 * N + 1, 10 * N + 1
    MEMO = [[[None] * z for _ in range(y)] for _ in range(x)]

    ans = recur(0, 0, 0)

    return ans


if __name__ == '__main__':
    res = solve(*args())

    print(-1) if res == float("inf") else print(res)

Submission status: Accepted

Solution code:
N,Ma,Mb = map(int,input().split())
dp = [[[10**9 for i in range(401)] for j in range(401)] for k in range(N+1)]
dp[0][0][0] = 0
for i in range(1,N+1):
    a,b,c = map(int,input().split())
    for j in range(401):
        for k in range(401):
            if j < a:
                dp[i][j][k] = dp[i-1][j][k]
            else:
                if k < b:
                    dp[i][j][k] = dp[i-1][j][k]
                else:
                    dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b] + c)
m = max(Ma,Mb)
import math
n = math.floor(400 / m)
ans = 10**9
for i in range(1,400):
    x = Ma*i
    y = Mb*i
    if x > 400:
        break
    if y > 400:
        break
    ans = min(dp[N][x][y],ans)
if ans == 10**9:
    print(-1)
    quit()
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, a, b = map(int, input().split())
t = []
dp = [[[float("inf")] * (N * 10 + 1) for _ in range(N * 10 + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
  x, y, c = map(int, input().split())
  for j in range(N * 10 + 1):
    for k in range(N * 10 + 1):
      if dp[i][j][k] != float("inf"):
        dp[i + 1][j + x][k + y] = min(dp[i + 1][j + x][k + y], dp[i][j][k] + c)
      dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k])
res = float("inf")
for j in range(1, N * 10 + 1):
  for k in range(1, N * 10 + 1):
    if j / a == k / b:
      res = min(res, dp[-1][j][k])
if res != float("inf"): print(res)
else: print(-1)