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

Solution code:
import numpy as np
n, ma, mb = map(int, input().split())

a = [0]*n
b = [0]*n
c = [0]*n
min_cost = 1000000000

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

for i in range(2**n):
    total_a = 0
    total_b = 0
    total_cost = 0
    for j in range(n):
        if((i >> j) & 1):
            total_a += a[j]
            total_b += b[j]
            total_cost += c[j]
    if (total_cost != 0 and total_a/total_b == ma/mb):
        min_cost = min(min_cost,total_cost)
    
if (min_cost < 1000000000):
    print(min_cost)
else:
    print('-1')

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,Ma,Mb = map(int,input().split())
    abc = [list(map(int,input().split())) for i in range(N)]

    INF = N * 100 + 1

    dp = [[[INF for cb in range(411)] for ca in range(411)] for i in range(N+1)]
    dp[0][0][0] = 0

    for i in range(N):
        for ca in range(N*10):
            for cb in range(N*10):
                dp[i+1][ca][cb] = min(dp[i+1][ca][cb],dp[i][ca][cb])
                d = abc[i]
                dp[i+1][ca+d[0]][cb+d[1]] = min(dp[i+1][ca+d[0]][cb+d[1]],dp[i][ca][cb]+d[2])

    res = INF

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

    if res == INF:
        res = -1

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,Ma,Mb = map(int,input().split())
    abc = [list(map(int,input().split())) for i in range(N)]

    INF = N * 100 + 1

    dp = [[[INF for cb in range(N*10+11)] for ca in range(N*10+11)] for i in range(N+1)]
    dp[0][0][0] = 0

    for i in range(N):
        for ca in range(N*10):
            for cb in range(N*10):
                dp[i+1][ca][cb] = min(dp[i+1][ca][cb],dp[i][ca][cb])
                d = abc[i]
                dp[i+1][ca+d[0]][cb+d[1]] = min(dp[i+1][ca+d[0]][cb+d[1]],dp[i][ca][cb]+d[2])

    res = INF
    ratio = 0

    while True:
        ratio += 1
        rMa = ratio * Ma
        rMb = ratio * Mb
        if (rMa > N*10) | (rMb > N*10):
            break
        res = min(res,dp[N][rMa][rMb])

    if res == INF:
        res = -1

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
n,ma,mb=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(n)]
dp=[[[10**9]*401 for i in range(401)] for j 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):
      if j-abc[i-1][0]>=0 and k-abc[i-1][1]>=0:
        dp[i][j][k]=min(dp[i-1][j][k],dp[i-1][j-abc[i-1][0]][k-abc[i-1][1]]+abc[i-1][2])
      else:
        dp[i][j][k]=dp[i-1][j][k]
ans=10**18
for j in range(1,401):
  for k in range(1,401):
    if dp[n][j][k]<10**9 and k*ma==j*mb:
      ans=min(ans,dp[n][j][k])
if ans==10**18:
  print(-1)
else: 
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, Ma, Mb = map(int, input().split())
a = [[0, 0, 0] for _ in range(N)]
sa = 0
sb = 0
for i in range(N):
    a[i][0], a[i][1], a[i][2] = map(int, input().split())
    sa += a[i][0]
    sb += a[i][1]
INF = 1000000  

DP = [[[INF for _ in range(sb+1)] for _ in range(sa+1)] for _ in range(N+1)]
DP[0][0][0] = 0

for i in range(N):
    for j in range(sa+1):
        for k in range(sb+1):
            if(j >= a[i][0] and k >= a[i][1]):
                DP[i+1][j][k] = min(DP[i][j-a[i][0]][k-a[i][1]] + a[i][2], DP[i][j][k])
            else:
                DP[i+1][j][k] = DP[i][j][k]
ans = INF
for i in range(1, min(sa//Ma, sb//Mb)+1):
    ans = min(ans, DP[N][Ma*i][Mb*i])
    
if(ans == INF):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n,ma,mb=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(n)]
dp=[[float('inf')]*500000 for i in range(n+1)]
dp[0][0]=0
for i in range(n):
    for j in range(500000):
        if dp[i][j]!=float('inf'):
            a=j//1000
            b=j%1000
            dp[i+1][(a+abc[i][0])*1000+b+abc[i][1]]=min(dp[i][j]+abc[i][2],dp[i+1][(a+abc[i][0])*1000+b+abc[i][1]])
            dp[i+1][j]=min(dp[i+1][j],dp[i][j])
ans=float('inf')
now=[ma,mb]
while 1:
    a,b=now
    ans=min(ans,dp[n][a*1000+b])
    if a+ma>400 or b>400:
        break
    now=[a+ma,b+mb]
if ans==float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,Ma,Mb= (int(x) for x in input().split())
a = [0]*N
b = [0]*N
c = [0]*N
# use = [0]*N
ans = 40*100+1
for i in range (N):
    a[i],b[i],c[i] = (int(x) for x in input().split())
# 0ならつかわない1なら使う
A = 0
B = 0
C = 0
def search(N,Ma,Mb,a,b,c,A,B,C,answer):
    if (B!= 0 and A/B == Ma/Mb):
            answer = C
            return C
    if(N==1):
#         use[N-1] = 0
#         if (B!= 0 and A/B == Ma/Mb):
#             return C
#         use[N-1] = 1
        A += a[N-1]
        B += b[N-1]
        C += c[N-1]
        if (B!= 0 and A/B == Ma/Mb):
            answer = C
            return C
        else: C = ans
        return C
    else:
#         use[N-1] = 0
        c0 = search(N-1,Ma,Mb,a,b,c,A,B,C,answer)
#         use[N-1] = 1
        A += a[N-1]
        B += b[N-1]
        C += c[N-1]
        if(C > ans):
            return ans
        else: 
            c1 = search(N-1,Ma,Mb,a,b,c,A,B,C,answer)
    return min(c0,c1)

Ans = search(N,Ma,Mb,a,b,c,A,B,C,ans)
if(Ans == ans):
    print("-1")
else: print(Ans)

Submission status: Time Limit Exceeded

Solution code:
N,Ma,Mb= (int(x) for x in input().split())
a = [0]*N
b = [0]*N
c = [0]*N
# use = [0]*N
ans = 40*100+1
for i in range (N):
    a[i],b[i],c[i] = (int(x) for x in input().split())
# 0ならつかわない1なら使う
A = 0
B = 0
C = 0
def search(N,Ma,Mb,a,b,c,A,B,C):
    if (B!= 0 and A/B == Ma/Mb):
            return C
    if(N==1):
#         use[N-1] = 0
#         if (B!= 0 and A/B == Ma/Mb):
#             return C
#        use[N-1] = 1
        A += a[N-1]
        B += b[N-1]
        C += c[N-1]
        if (B!= 0 and A/B == Ma/Mb):
             return C
        else: C = ans
        return C
    else:
#         use[N-1] = 0
        c0 = search(N-1,Ma,Mb,a,b,c,A,B,C)
#         use[N-1] = 1
        A += a[N-1]
        B += b[N-1]
        C += c[N-1]
        c1 = search(N-1,Ma,Mb,a,b,c,A,B,C)
    return min(c0,c1)

Ans = search(N,Ma,Mb,a,b,c,A,B,C)
if(Ans == ans):
    print("-1")
else: print(Ans)

Submission status: Time Limit Exceeded

Solution code:
N,Ma,Mb= (int(x) for x in input().split())
a = [0]*N
b = [0]*N
c = [0]*N
use = [0]*N
ans = 40*100+1
for i in range (N):
    a[i],b[i],c[i] = (int(x) for x in input().split())
# 0ならつかわない1なら使う
A = 0
B = 0
C = 0
def search(N,Ma,Mb,a,b,c,use,A,B,C):
    if (B!= 0 and A/B == Ma/Mb):
            return C
    if(N==1):
#         use[N-1] = 0
#         if (B!= 0 and A/B == Ma/Mb):
#             return C
        use[N-1] = 1
        A += a[N-1]
        B += b[N-1]
        C += c[N-1]
        if (B!= 0 and A/B == Ma/Mb):
             return C
        else: C = ans
        return C
    else:
        use[N-1] = 0
        c0 = search(N-1,Ma,Mb,a,b,c,use,A,B,C)
        use[N-1] = 1
        A += a[N-1]
        B += b[N-1]
        C += c[N-1]
        c1 = search(N-1,Ma,Mb,a,b,c,use,A,B,C)
    return min(c0,c1)

if search(N,Ma,Mb,a,b,c,use,A,B,C) == ans:
    print("-1")
else: print(search(N,Ma,Mb,a,b,c,use,A,B,C))

Submission status: Time Limit Exceeded

Solution code:
N,Ma,Mb= (int(x) for x in input().split())
a = [0]*N
b = [0]*N
c = [0]*N
use = [0]*N
ans = 40*100+1
for i in range (N):
    a[i],b[i],c[i] = (int(x) for x in input().split())
# 0ならつかわない1なら使う
A = 0
B = 0
C = 0
def search(N,Ma,Mb,a,b,c,use,A,B,C):
    if(N==1):
        use[N-1] = 0
        if (B!= 0 and A/B == Ma/Mb):
            return C
        use[N-1] = 1
        A += a[N-1]
        B += b[N-1]
        C += c[N-1]
        if (B!= 0 and A/B == Ma/Mb):
             return C
        else: C = ans
        return C
    else:
        use[N-1] = 0
        c0 = search(N-1,Ma,Mb,a,b,c,use,A,B,C)
        use[N-1] = 1
        A += a[N-1]
        B += b[N-1]
        C += c[N-1]
        c1 = search(N-1,Ma,Mb,a,b,c,use,A,B,C)
    return min(c0,c1)

if search(N,Ma,Mb,a,b,c,use,A,B,C) == ans:
    print("-1")
else: print(search(N,Ma,Mb,a,b,c,use,A,B,C))

Submission status: Time Limit Exceeded

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 = []
    S2 = []

    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))
        S2.append((A2, B2, C2))

    D = dict()
    S2.sort(key=lambda x: x[2], reverse=True)

    res = INF

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

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

Solution code:
INF = 10**18

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

if N % 2 == 1:
    sol.append((0, 0, 0))
    N += 1

M = N // 2

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

S1 = []
S2 = []

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))
    S2.append((A2, B2, C2))

D = dict()
S2.sort(key=lambda x: x[2], reverse=True)

res = INF

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



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)

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

Submission status: Time Limit Exceeded

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)]
infi=10**15
dp=[[[infi]*(401) for _ in range(401)]for _ in range(41)]
dp[0][0][0]=0
for i in range(n):
    a,b,c=ABC[i]
    for j in range(401-a):
        for k in range(401-b):
            ni=i+1
            nj=j+a
            nk=k+b
            dp[ni][j][k]=min(dp[ni][j][k], dp[i][j][k])
            dp[ni][nj][nk]=min(dp[i][j][k]+c,dp[ni][nj][nk])

ans=infi
for i in range(1,401):
    if ma*i>400:
        break
    if mb*i>400:
        break    
    ans=min(ans, dp[n][ma*i][mb*i])
print(ans if ans!=infi else -1)

Submission status: Time Limit Exceeded

Solution code:
n, ma, mb = map(int, input().split())

a = [0]*n
b = [0]*n
c = [0]*n
min_cost = 1000000000

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

for i in range(2**n):
    total_a = 0
    total_b = 0
    total_cost = 0
    for j in range(n):
        if((i >> j) & 1):
            total_a += a[j]
            total_b += b[j]
            total_cost += c[j]
    if (total_cost != 0 and total_a/total_b == ma/mb):
        min_cost = min(min_cost,total_cost)
    
if (min_cost < 1000000000):
    print(min_cost)
else:
    print('-1')

Submission status: Time Limit Exceeded

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(2**(N+1))] for i in range(N)]

dp[0][1]=ABC[0][2]

for n in range(1,N):
    a,b,c=ABC[n]
    for i in range(2**(N+1)):
        if i|2**n<len(dp[0]):
            dp[n][i|2**n]=min(dp[n-1][i]+c,dp[n-1][i|2**n],dp[n][i])
        dp[n][i]=min(dp[n-1][i],dp[n][i])
value=idle_max

for i in range(len(dp[0])):
    A=0;B=0
    for n in range(N):
        a,b,c=ABC[n]
        if (i>>n)&1:
            A+=a
            B+=b
    Z=gcd(A,B)
    if A and B and Ma==A//Z and Mb==B//Z:
        value=min(value,dp[-1][i])
if value!=idle_max:
    print(value)
else:
    print(-1)

Submission status: Time Limit Exceeded

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]*(100*n+1) for i in range(100*n+1)]
dp[0][0] = 0
for t in range(n):
    dp2 = [[BIG]*(100*n+1) for i in range(100*n+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*100:
        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: Time Limit Exceeded

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

INF = 40 * 100 + 1
ab_max = 10 * n

dp = [[[INF] * (ab_max + 1) for _ in range(ab_max + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0

for i, (a, b, c) in enumerate(abc, 1):
    for j in range(ab_max + 1):
        for k in range(ab_max + 1):
            dp[i][j][k] = dp[i-1][j][k]
            if j - a >= 0 and k - b >= 0:
                if dp[i-1][j-a][k-b] != INF:
                    dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-a][k-b] + c)


ans = INF
for j in range(1, ab_max + 1):
    for k in range(1, ab_max + 1):
        if j * mb == k * ma:
            ans = min(ans, dp[n][j][k])

if ans == INF:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

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())
    for j in range(r):
        for k in range(r):
            if j + a < r and k + b < r:
                dp[i+1][j+a][k+b] = min(
                    dp[i][j][k] + c, dp[i][j+a][k+b]
                )
            dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])

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

Solution code:
#!/usr/bin/env python3
def solve():
    N, M_a, M_b = [int(x) for x in input().split()]
    inf = 100000
    t = [[inf] * (10 * N + 1) for _ in range(10 * N + 1)]
    t[0][0] = 0
    for _ in range(N):
        ai, bi, ci = [int(x) for x in input().split()]
        for ta in reversed(range(ai, len(t))):
            for tb in reversed(range(bi, len(t[0]))):
                t[ta][tb] = min(t[ta][tb], t[ta - ai][tb - bi] + ci)
    ans = min(
        t[k * M_a][k * M_b]
        for k in range(1, min((len(t) - 1) // M_a, (len(t[0]) - 1) // M_b) + 1)
    )
    print(-1 if ans >= inf else ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


N, M_a, M_b = [int(x) for x in input().split()]
inf = 100000
t = [[inf] * (10 * N + 1) for _ in range(10 * N + 1)]
t[0][0] = 0
for _ in range(N):
    ai, bi, ci = [int(x) for x in input().split()]
    for ta in reversed(range(ai, len(t))):
        for tb in reversed(range(bi, len(t[0]))):
            t[ta][tb] = min(t[ta][tb], t[ta - ai][tb - bi] + ci)
ans = min(
    t[k * M_a][k * M_b]
    for k in range(1, min((len(t) - 1) // M_a, (len(t[0]) - 1) // M_b) + 1)
)
print(-1 if ans >= inf else ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M_a: int, M_b: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    inf = 100000
    t = [[inf] * (10 * N + 1) for _ in range(10 * N + 1)]
    t[0][0] = 0
    for ai, bi, ci in zip(a, b, c):
        for ta in reversed(range(ai, len(t))):
            for tb in reversed(range(bi, len(t[0]))):
                t[ta][tb] = min(t[ta][tb], t[ta - ai][tb - bi] + ci)
    ans = min(
        t[k * M_a][k * M_b]
        for k in range(1, min((len(t) - 1) // M_a, (len(t[0]) - 1) // M_b) + 1)
    )
    print(-1 if ans >= inf else ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M_a = int(next(tokens))  # type: int
    M_b = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M_a, M_b, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M_a: int, M_b: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    t = [[float("inf")] * (10 * N + 1) for _ in range(10 * N + 1)]
    t[0][0] = 0
    for ai, bi, ci in zip(a, b, c):
        for ta in reversed(range(ai, len(t))):
            for tb in reversed(range(bi, len(t[0]))):
                t[ta][tb] = min(t[ta][tb], t[ta - ai][tb - bi] + ci)
    ans = min(
        t[k * M_a][k * M_b]
        for k in range(1, min((len(t) - 1) // M_a, (len(t[0]) - 1) // M_b) + 1)
    )
    print(-1 if ans == float("inf") else ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M_a = int(next(tokens))  # type: int
    M_b = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M_a, M_b, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

# 行列のDPを持つ　縦軸がa
N, Ma, Mb = lr()
INF = 5000
limit = N * 10 + 1
dp = [[INF] * limit for _ in range(limit)]
dp[0][0] = 0
for _ in range(N):
    a, b, c = lr()
    used = set()
    for i in range(limit):
        if i < a:
            continue
        for j in range(limit):
            if j < b:
                continue
            # 商品は１個しか買えない            
            if (i-a, j-b) not in used:
                if dp[i][j] > dp[i-a][j-b] + c:
                    used.add((i, j))
                    dp[i][j] = dp[i-a][j-b] + c

answer = INF
for i in range(1, limit):
    if i % Ma != 0:
        continue
    for j in range(1, limit):
        if j % Mb != 0:
            continue
        if i // Ma == j // Mb:
            if dp[i][j] < answer:
                answer = dp[i][j]

print(answer if answer != INF else -1)
# 10

Submission status: Time Limit Exceeded

Solution code:
n, ma, mb = map(int, input().split())
U = 400
dp = [[[float("inf")]*(U+1) for _ in range(U+1)] 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(U+1):
    for k in range(U+1):
      if j<a or k<b:
        dp[i+1][j][k] = dp[i][j][k]
      else:
        dp[i+1][j][k] = min(dp[i][j][k], dp[i][j-a][k-b]+c)
ans = float("inf")
for i in range(1, 1+U//max(ma, mb)):
  na, nb = i*ma, i*mb
  ans = min(ans, dp[-1][na][nb])
if ans == float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from bisect import bisect_left
N,Ma,Mb = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
if N==1:
    if A[0][0]*Mb==A[0][1]*Ma:
        print(A[0][2])
    else:
        print(-1)
else:
    A1 = A[:N//2]  # N//2
    A2 = A[N//2:]  # N-N//2
    B1 = []
    for x in product((0,1),repeat=N//2):
        cnt1 = 0
        cnt2 = 0
        for i in range(N//2):
            cnt1 += x[i]*(Ma*A1[i][1]-Mb*A1[i][0])
            cnt2 += x[i]*A1[i][2]
        B1.append((cnt1,cnt2))
    B2 = []
    for x in product((0,1),repeat=N-N//2):
        cnt1 = 0
        cnt2 = 0
        for i in range(N-N//2):
            cnt1 += x[i]*(Ma*A2[i][1]-Mb*A2[i][0])
            cnt2 += x[i]*A2[i][2]
        B2.append((cnt1,cnt2))
    B1 = sorted(B1,key=lambda x:x[1])
    B1 = sorted(B1,key=lambda x:x[0])
    B2 = sorted(B2,key=lambda x:x[1])
    B2 = sorted(B2,key=lambda x:x[0])
    cmin = 10000
    for b1 in B1:
        b,c = b1[0],b1[1]
        if c==0:
            ind = bisect_left(B2,(-b,1))
        else:
            ind = bisect_left(B2,(-b,0))
        if ind<len(B2) and B2[ind][0]==-b:
            cmin = min(cmin,c+B2[ind][1])
    if cmin>=10000:
        print(-1)
    else:
        print(cmin)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from bisect import bisect_left
N,Ma,Mb = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
if N==1:
    if A[0][0]*Mb==A[0][1]*Ma:
        print(A[0][2])
    else:
        print(-1)
else:
    A1 = A[:N//2]  # N//2
    A2 = A[N//2:]  # N-N//2
    B1 = []
    for x in product((0,1),repeat=N//2):
        cnt1 = 0
        cnt2 = 0
        for i in range(N//2):
            if x[i]==1:
                cnt1 += Ma*A1[i][1]-Mb*A1[i][0]
                cnt2 += A1[i][2]
        B1.append((cnt1,cnt2))
    B2 = []
    for x in product((0,1),repeat=N-N//2):
        cnt1 = 0
        cnt2 = 0
        for i in range(N-N//2):
            if x[i]==1:
                cnt1 += Ma*A2[i][1]-Mb*A2[i][0]
                cnt2 += A2[i][2]
        B2.append((cnt1,cnt2))
    B1 = sorted(B1,key=lambda x:x[1])
    B1 = sorted(B1,key=lambda x:x[0])
    B2 = sorted(B2,key=lambda x:x[1])
    B2 = sorted(B2,key=lambda x:x[0])
    cmin = 10000
    for b1 in B1:
        b,c = b1[0],b1[1]
        if c==0:
            ind = bisect_left(B2,(-b,1))
        else:
            ind = bisect_left(B2,(-b,0))
        if ind<len(B2) and B2[ind][0]==-b:
            cmin = min(cmin,c+B2[ind][1])
    if cmin>=10000:
        print(-1)
    else:
        print(cmin)

Submission status: Time Limit Exceeded

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


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

Solution code:
n,ma,mb=map(int,input().split())
dpn=400001
dp=[10**6]*dpn
dp[0]=0
for i in range(n):
    a,b,c=map(int,input().split())
    for j in range(dpn-1,-1,-1):
        if j==0 or dp[j]!=10**6:
            dp[j+a*1000+b]=min(dp[j+a*1000+b],dp[j]+c)
ans=10**6
s=1000*ma+mb
p=1
while s*p<dpn:
    ans=min(ans,dp[s*p])
    p+=1
if ans==10**6:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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)

import itertools
l = list(itertools.product([False,True], repeat=N))

min_cost = 1000000000000000000
for comb in l[1:]:
  idx = [i for i, x in enumerate(comb) if x == True]
  cost = sum([costs[i] for i in idx])
  mass = [mas[i] for i in idx]
  mbss = [mbs[i] for i in idx]
  if ((sum(mass) // Ma) == (sum(mbss) // Mb)) & (sum(mass)%Ma==0) & (sum(mbss)%Mb==0) & (cost < min_cost):
    min_cost = cost
if min_cost == 1000000000000000000:
  print("-1")
else:
  print(min_cost)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

items = []
for i in range(N):
  items.append(list(map(int, input().split())))

items = np.array(items)

import itertools
l = list(itertools.product([False,True], repeat=N))

min_cost = 1000000000000000000
for comb in l[1:]:
  idx = np.where(comb)
  cost = items[idx,2].sum()
  if ((items[idx,0].sum() // Ma) == (items[idx,1].sum() // Mb)) & (items[idx,0].sum()%Ma==0) & (items[idx,1].sum()%Mb==0) & (cost < min_cost):
    min_cost = cost
if min_cost == 1000000000000000000:
  print("-1")
else:
  print(min_cost)

Submission status: Time Limit Exceeded

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, cost):
        if not i < N:
            if 0 < a and 0 < b:
                g = fractions.gcd(a, b)
                if (MA, MB) == (a / g, b / g):
                    return cost
            return float("inf")

        return min(recur(i + 1, a, b, cost), recur(i + 1, a + A[i], b + B[i], cost + C[i]))

    ans = recur(0, 0, 0, 0)

    return ans


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

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

Submission status: Time Limit Exceeded

Solution code:
import sys


n,a,b=[int(x) for x in str(input()).split()]
A=[]
for i in range(n):
  A.append([int(x) for x in sys.stdin.readline().split()])



#print(A)
def f(ma,mb,cost,index):

  newa=ma+A[index][0]
  newb=mb+A[index][1]
  newc=cost+A[index][2]
  
  #print(index,newa,newb,newc)
  if newa*b==a*newb:
    return newc
  elif index==n-1:
    return 100000000000000000000
  else:
    ith=f(newa,newb,newc,index+1)
    return min(ith,f(ma,mb,cost,index+1))



if f(0,0,0,0)<100000000000000000000:
  print(f(0,0,0,0))
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
MAX = 10**9

def solve():
    N, M_a, M_b = map(int, input().split())
    A = []
    B = []
    C = []
    for _ in range(N):
        a,b,c = map(int, input().split())
        A.append(a)
        B.append(b)
        C.append(c)
        
    max_A = sum(A)
    max_B = sum(B)
    dp_table = [[[MAX for _ in range(max_B+1)] for _ in range(max_A+1)] for _ in range(N+1)]
    dp_table[0][0][0] = 0
    for i in range(N):
        for ca in range(max_A-1):
            for cb in range(max_B-1):
                dp_table[i+1][ca][cb] = min(dp_table[i][ca][cb], dp_table[i+1][ca][cb])
                if ca-A[i] >= 0 and cb-B[i] >= 0:
                    dp_table[i+1][ca][cb] = min(dp_table[i+1][ca][cb], dp_table[i][ca-A[i]][cb-B[i]]+C[i])
                    # print(i+1, ca, cb, dp_table[i+1][ca][cb])
    
    k = 1
    # print(dp_table)
    ret = MAX
    while k*M_a < max_A and k*M_b < max_B:
        ret = min(ret, dp_table[N][k*M_a][k*M_b])
        k += 1
        
    print(ret if ret < MAX else '-1')
    
solve()