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

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,A,B = [int(i) for i in readline().split()]
abc = [[int(i) for i in readline().split()] for j in range(n)]

ans = 10**9

d = {0:0}
for i in range(n):
    nd = {}
    a,b,c = abc[i]
    for amari,yen in d.items():
        if amari in nd:
            nd[amari] = min(nd[amari],yen)
        else:
            nd[amari] = yen

        yen += c
        amari += a*B-b*A
        if amari == 0 and yen != 0:
            ans = min(ans,yen)
        elif amari in nd:
            nd[amari] = min(nd[amari],yen)
        else:
            nd[amari] = yen
    d = nd
#    print(d,nd)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, Ma, Mb = l_inpl()
    abc = []
    for _ in range(N):
        abci = l_inpl()
        abc.append(abci)

    max_ab = 40*10

    # dp[i][j][k]: i番目までの薬品の組み合わせで，物質aがjグラム，物質bがkグラムのときのコスト
    dp = [[[INF for _ in range(max_ab+1)] for _ in range(max_ab+1) ] for _ in range(N+1)]
    dp[0][0][0] = 0

    for i in range(N):
        for j in range(max_ab+1):
            for k in range(max_ab+1):
                # ここでのINFはNoneと同じ意味なので
                if dp[i][j][k] == INF:
                    continue
                # i番目の薬品を加えない
                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
                # i番目の薬品を加える
                dp[i+1][j+abc[i][0]][k+abc[i][1]] = min(dp[i+1][j+abc[i][0]][k+abc[i][1]], dp[i+1][j][k] + abc[i][2])
                
    ans = INF
    for ca in range(1, max_ab+1):
        for cb in range(1, max_ab+1):
            if ca*Mb == cb*Ma:
                ans = min(ans, dp[N][ca][cb])
    
    if ans == INF:
        print(-1)
    else:
        print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, Ma, Mb = l_inpl()
    abc = []
    for _ in range(N):
        abci = l_inpl()
        abc.append(abci)

    max_ab = 40*10

    # dp[i][j][k]: i番目までの薬品の組み合わせで，物質aがjグラム，物質bがkグラムのときのコスト
    dp = [[[INF for _ in range(max_ab+1)] for _ in range(max_ab+1) ] for _ in range(N+1)]
    dp[0][0][0] = 0

    for i in range(N):
        for j in range(max_ab+1):
            for k in range(max_ab+1):
                # ここでのINFはNoneと同じ意味なので
                if dp[i][j][k] == INF:
                    continue
                # i番目の薬品を加えない
                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
                # i番目の薬品を加える
                dp[i+1][j+abc[i][0]][k+abc[i][1]] = min(dp[i+1][j+abc[i][0]][k+abc[i][1]], dp[i+1][j][k] + abc[i][2])
                
    ans = INF
    for ca in range(1, max_ab+1):
        for cb in range(1, max_ab+1):
            if ca*Mb == cb*Ma:
                ans = min(ans, dp[N][ca][cb])
    
    if ans == INF:
        print(-1)
    else:
        print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e50)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, Ma, Mb = l_inpl()
    abc = []
    for _ in range(N):
        abci = l_inpl()
        abc.append(abci)

    max_ab = 40*10

    # dp[i][j][k]: i番目までの薬品の組み合わせで，物質aがjグラム，物質bがkグラムのときのコスト
    dp = [[[INF for _ in range(max_ab+1)] for _ in range(max_ab+1) ] for _ in range(N+1)]
    dp[0][0][0] = 0

    for i in range(N):
        for j in range(max_ab+1):
            for k in range(max_ab+1):
                # ここでのINFはNoneと同じ意味なので
                if dp[i][j][k] == INF:
                    continue
                # i番目の薬品を加えない
                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
                # i番目の薬品を加える
                dp[i+1][j+abc[i][0]][k+abc[i][1]]
                dp[i+1][j+abc[i][0]][k+abc[i][1]] = min(dp[i+1][j+abc[i][0]][k+abc[i][1]], dp[i+1][j][k] + abc[i][2])
                
    ans = INF
    for ca in range(1, max_ab+1):
        for cb in range(1, max_ab+1):
            if ca*Mb == cb*Ma:
                ans = min(ans, dp[N][ca][cb])
    
    if ans == INF:
        print(-1)
    else:
        print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,Ma,Mb = map(int,input().split())
table = []
sum_a,sum_b,sum_c = 0,0,0

for i in range(N):
  a,b,c=map(int,input().split())
  sum_a += a 
  sum_b += b
  sum_c += c
  table.append((a,b,c))
  
INF = sum_c+1
ans = INF
dp=[[[INF]*(401) for i in range(401)] for i in range(N+1)]
dp[0][0][0] = 0
for i in range(1,N+1):
  a,b,c = table[i-1]
  for ca in range(401):
    for cb in range(401):
      dp[i][ca][cb] = min(dp[i-1][ca][cb],dp[i][ca][cb])
      if ca+a < sum_a and cb+b < sum_b:
        dp[i][ca+a][cb+b] = min(dp[i][ca+a][cb+b],dp[i][ca][cb]+c)

for ca in range(sum_a+1):
  for cb in range(sum_b+1):
    if ca*Ma == cb*Mb and ca*cb != 0:
      for i in range(N+1):
        ans = min(ans,dp[i][ca][cb])
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC54 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n,ma,mb = map(int,input().split())
x = [list(map(int,input().split())) for _ in range(n)]
sa = 0
sb = 0
for a,b,c in x:
    sa += a
    sb += b
dp = [[float('inf')]*(sb+1) for _ in range(sa+1)]
dp[0][0] = 0
for a,b,c in x:
    y = [[0]*(sb+1) for _ in range(sa+1)]
    for i in range(sa+1):
        for j in range(sb+1):
            if i+a < sa+1 and j+b < sb+1:
                if y[i][j] == 0:
                    dp[i+a][j+b] = min(dp[i+a][j+b],dp[i][j]+c)
                    y[i+a][j+b] = 1
ans = float('inf')
for i in range(1,sa+1):
    for j in range(1,sb+1):
        if i*mb == j*ma:
            ans = min(ans,dp[i][j])
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC54 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n,ma,mb = map(int,input().split())
x = [list(map(int,input().split())) for _ in range(n)]
sa = 0
sb = 0
for a,b,c in x:
    sa += a
    sb += b
dp = [[float('inf')]*(sb+1) for _ in range(sa+1)]
dp[0][0] = 0
for a,b,c in x:
    for i in range(sa+1):
        for j in range(sb+1):
            if i+a < sa+1 and j+b < sb+1:
                dp[i+a][j+b] = min(dp[i+a][j+b],dp[i][j]+c)
                flg = 0

ans = float('inf')
for i in range(1,sa+1):
    for j in range(1,sb+1):
        if i*mb == j*ma:
            ans = min(ans,dp[i][j])
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC54 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n,ma,mb = map(int,input().split())
x = [list(map(int,input().split())) for _ in range(n)]
sa = 0
sb = 0
for a,b,c in x:
    sa += a
    sb += b
dp = [[float('inf')]*(sb+1) for _ in range(sa+1)]
dp[0][0] = 0
for a,b,c in x:
    for i in range(sb+1):
        for j in range(sa+1):
            if i+a < sa+1 and j+b < sb+1:
                dp[i+a][j+b] = min(dp[i+a][j+b],dp[i][j]+c)

ans = float('inf')
for i in range(1,sa+1):
    for j in range(1,sb+1):
        if i*mb == j*ma:
            ans = min(ans,dp[i][j])
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:


import math
N,Ma,Mb = map(int,input().split(" "))
drags = [list(map(int,input().split(" "))) for  _ in range(N)]
INF = 10 ** 9
lim = N * 10 + 1
dp = [[[ INF for i in range(lim)] for j in range(lim)] for _ in range(N+1)]
dp[0][0][0] = 0
for num in range( N ):
    a,b,c = drags[num]
    for i in range(a,lim): #薬品厨のa の量
        for j in range(b,lim ):#薬品厨のb の量
             dp[num + 1][i][j] = min(dp[num][i ][j] ,dp[num][i - a][j - b]  + c)

ans = INF
for i in range(1,41):
    MA = Ma * i
    MB = Mb * i
    if MA >= lim or MB >= lim:
        break
    ans = min(ans, dp[-1][MA][MB])
if ans == INF:
    ans = -1
print(ans)

Submission status: Wrong Answer

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

INF = 10 ** 5
nums = 7

dp = [[[INF for _ in range(nums+100)] for _ in range(nums+100)] for _ in range(N+1)]

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

for i in range(N):
    for sum_a in range(nums):
        for sum_b in range(nums):
            if dp[i][sum_a][sum_b] == INF:
                continue
            dp[i+1][sum_a+a[i]][sum_b+b[i]] = min(dp[i+1][sum_a+a[i]][sum_b+b[i]], dp[i][sum_a][sum_b] + c[i])
            dp[i+1][sum_a][sum_b] = min(dp[i+1][sum_a][sum_b], dp[i][sum_a][sum_b])
            #dp[i+1][sum_a+a[i]][sum_b+b[i]] = min(dp[i+1][sum_a+a[i]][sum_b+b[i]], dp[i][sum_a][sum_b] + c[i])
            #print(i, dp[i][sum_a][sum_b], sum_a, sum_b)


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

if res == INF:
    res = -1

print(res)

Submission status: Wrong Answer

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

INF = 10 ** 5
nums = 7

dp = [[[INF for _ in range(nums+100)] for _ in range(nums+100)] for _ in range(N+1)]

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

for i in range(N):
    for sum_a in range(nums):
        for sum_b in range(nums):
            #if dp[i][sum_a][sum_b] == INF:
            #    continue
            dp[i+1][sum_a+a[i]][sum_b+b[i]] = min(dp[i+1][sum_a+a[i]][sum_b+b[i]], dp[i][sum_a][sum_b] + c[i])
            dp[i+1][sum_a][sum_b] = min(dp[i+1][sum_a][sum_b], dp[i][sum_a][sum_b])
            #dp[i+1][sum_a+a[i]][sum_b+b[i]] = min(dp[i+1][sum_a+a[i]][sum_b+b[i]], dp[i][sum_a][sum_b] + c[i])
            #print(i, dp[i][sum_a][sum_b], sum_a, sum_b)


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

if res == INF:
    res = -1

print(res)

Submission status: Wrong Answer

Solution code:
N,Ma,Mb = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in [0]*N]
INFTY = 10**8
dp = [[[INFTY]*10*(N+1) for _ in [0]*10*(N+1)] for _ in [0]*(N+1)]
for i in range(1,N+1):
    a,b,c = ABC[i-1]
    for j in range(10*(N+1)):
        for k in range(10*(N+1)):
            dp[i][j][k] = dp[i-1][j][k]
            if j-a>=0 and k-b>=0:
                dp[i][j][k] = min(dp[i][j][k],dp[i-1][j-a][k-b]+c)
ans = min(dp[-1][Ma*k][Mb*k] for k in range(1,(10*(N+1)-1)//max(Ma,Mb)+1))
if ans == INFTY : ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
N,Ma,Mb = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in [0]*N]
INFTY = 10**8
dp = [[[INFTY]*10*(N+1) for _ in [0]*10*(N+1)] for _ in [0]*(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    a,b,c = ABC[i-1]
    for j in range(a,10*(N+1)):
        for k in range(b,10*(N+1)):
            dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
ans = min(dp[-1][Ma*k][Mb*k] for k in range(1,(10*(N+1)-1)//max(Ma,Mb)+1))
if ans == INFTY : ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
N,Ma,Mb = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in [0]*N]
INFTY = 10**8
dp = [[[INFTY]*10*(N+1) for _ in [0]*10*(N+1)] for _ in [0]*(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    a,b,c = ABC[i-1]
    for j in range(a,10*(N+1)):
        for k in range(b,10*(N+1)):
            dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
ans = min(dp[-1][Ma*k][Mb*k] for k in range(1,10*(N+1)//max(Ma,Mb)))
if ans == INFTY : ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math

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

def getN():
    return int(input())

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

n, ma, mb = getlist()
prices = [4002 for i in range(401 * 401)]
prices[0] = 0

bought = [0]
for ch in range(n):
    a, b, c = getlist()
    # print(a,b,c)
    tmp = []
    for tgt in bought:
        nxt = tgt + a + b * 401
        # print(tgt, nxt)
        if prices[nxt] > prices[tgt] + c:
            prices[nxt] = prices[tgt] + c
        tmp.append(nxt)
    bought = bought + tmp

ans = 4001
for i in range(1, 400//max(ma, mb)):
    tgt = prices[ma*i + mb*i*401]
    if ans > tgt:
        ans = tgt


if ans == 4001:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

dp = [defaultdict(lambda : float('inf')) for _ in range(2)]
zero = float('inf')

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

for _ in range(N) :
    a, b, c = map(int, input().split())
    d = a * Mb - b * Ma
    if d == 0 :
        zero = min(zero, c)
    else :
        i = 0 if d > 0 else 1
        d = abs(d)
        item = list(dp[i].items())
        for k, v in item :
            dp[i][k+d] = min(dp[i][k+d], dp[i][k] + c)

ret = zero       
for k, v in dp[0].items() :
    if k in dp[1] and k != 0 :
        ret = min(ret, v + dp[1][k])
        
if ret == float('inf') :
    print(-1)
else :
    print(ret)

Submission status: Wrong Answer

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

for _ in range(N) :
    a, b, c = map(int, input().split())
    abc.append([a * Mb - b * Ma, c])

abc.sort(key=lambda x: x[1])    

ret = float('inf')

def rec(n, d, c) :
    global ret
    if c > ret or n == N :
        return
        
    if d == 0 and c != 0 :
        ret = min(ret, c)
        return
    
    rec(n + 1, d, c)    
    rec(n + 1, d + abc[n][0], c + abc[n][1])

rec(0, 0, 0)

if ret == float('inf') :
    print(-1)
else :
    print(ret)

Submission status: Wrong Answer

Solution code:
N, MA, MB = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(N)]

inf = 1000 * N
M = N * 10 + 1
DP = [[[inf] * M for _ in range(M)] for _ in range(N)]

a, b, c = abc[0]
DP[0][a][b] = c

for i in range(1, N):
  a, b, c = abc[i]
  DP[i][a][b] = min(DP[i - 1][a][b], c)
  for j in range(M):
    for k in range(M):
      jj = j - a
      kk = k - b
      if jj >= 0 and kk >= 0:
        DP[i][j][k] = min(DP[i - 1][j][k], DP[i - 1][jj][kk] + c)
      else:
        DP[i][j][k] = DP[i - 1][j][k]


ans = inf
i = MA
j = MB
while i < M and j < M:
  ans = min(ans, DP[-1][i][j])
  i += MA
  j += MB

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

Submission status: Wrong Answer

Solution code:
N, MA, MB = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(N)]

inf = 1000 * N
M = N * 10 + 1
DP = [[[inf] * M for _ in range(M)] for _ in range(N)]

a, b, c = abc[0]
DP[0][a][b] = c

for i in range(1, N):
  a, b, c = abc[i]
  DP[i][a][b] = min(DP[i - 1][a][b], c)
  for j in range(M - 10):
    for k in range(M - 10):
      if DP[i - 1][j][k] < inf:
        jj = j + a
        kk = k + b
        DP[i][jj][kk] = min(DP[i - 1][jj][kk], DP[i - 1][j][k] + c)

ans = inf
i = MA
j = MB
while i < M and j < M:
  ans = min(ans, DP[-1][i][j])
  i += MA
  j += MB

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

Submission status: Wrong Answer

Solution code:
from sys import stdin

N, Ma, Mb = [int(x) for x in stdin.readline().rstrip().split()]
med = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]
dp = [(0, 0, 0)]
dp.append((med[0][0], med[0][1], med[0][2]))
for k in range(1, N):
    li = []
    for l in range(k + 1):
        li.append((dp[l][0] + med[k][0], dp[l][1] + med[k][1], dp[l][2] + med[k][2]))
    li.sort(key=lambda x: (max((x[0] * Mb) / (x[1] * Ma), (x[1] * Ma) / (x[0] * Mb)), x[2]))
    dp.append(li[0])

dp.pop(0)
dp.sort(key=lambda x: (max((x[0] * Mb) / (x[1] * Ma), (x[1] * Ma) / (x[0] * Mb)), x[2]))
if dp[0][0] * Mb != dp[0][1] * Ma:
    print('-1')
else:
    print(dp[0][2])

Submission status: Wrong Answer

Solution code:
from sys import stdin

N, Ma, Mb = [int(x) for x in stdin.readline().rstrip().split()]
med = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]
dp = [(0, 0, 0)]
dp.append((med[0][0], med[0][1], med[0][2]))
for k in range(1, N):
    li = []
    for l in range(k + 1):
        li.append((dp[l][0] + med[k][0], dp[l][1] + med[k][1], dp[l][2] + med[k][2]))
    li.sort(key=lambda x: (max((x[0] * Mb) / (x[1] * Ma), (x[1] * Ma) / (x[0] * Mb)), x[2]))
    dp.append(li[0])

dp.pop(0)
dp.sort(key=lambda x: (max((x[0] * Mb) / (x[1] * Ma), (x[1] * Ma) / (x[0] * Mb))))
if dp[0][0] * Mb != dp[0][1] * Ma:
    print('-1')
else:
    print(dp[0][2])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_right
INF = float('inf')
N, Ma, Mb = map(int, input().split())
a, b, c = [None] * N, [None] * N, [None] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
hN = N // 2
dic1 = defaultdict(lambda : INF)
for i in range(1 << hN):
    _a, _b, _c = 0, 0, 0
    for j in range(hN):
        if (i >> j) & 1:
            _a += a[j]
            _b += b[j]
            _c += c[j]
    if _c < dic1[(_a, _b)]:
        dic1[(_a, _b)] = _c
dic2 = defaultdict(lambda : INF)
for i in range(1 << (N - hN)):
    _a, _b, _c = 0, 0, 0
    for j in range(N - hN):
        if (i >> j) & 1:
            _a += a[j]
            _b += b[j]
            _c += c[j]
    if _c < dic2[(_a, _b)]:
        dic2[(_a, _b)] = _c
ans = INF
for k in dic1:
    _a, _b = k
    v = dic1[k]
    for i in range(1, N+1):
        ans = min(ans, v + dic2[(Ma*i-_a,Mb*i-_b)])
ans = ans if ans < INF else -1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, Ma, Mb = map(int, input().split())
a, b, c = [None] * N, [None] * N, [None] * N
INF, MAX = 1000000000, 10 * N + 1
dp = defaultdict(lambda : INF)
dp[(0, 0)] = 0
for i in range(N):
    a, b, c = map(int, input().split())
    predp = dp.copy()
    for ab, v in predp.items():
        _a, _b = ab
        dp[(_a+a, _b+b)] = min(dp[(_a+a, _b+b)], dp[(_a, _b)]+c)
ans = INF
for i in range(1, N+1):
    ans = min(ans, dp[(Ma*i, Mb*i)])
ans = -1 if ans == INF else ans
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 100000
N, Ma, Mb = map(int, input().split())
a, b, c = [None] * N, [None] * N, [None] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
dp = [[[INF] * (10*N+1) for j in range(10*N+1)] for i in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
    for j in range(10*N+1):
        for k in range(10*N+1):
            if j >= a[i] and k >= b[i]:
                dp[i+1][j][k] = min(dp[i][j][k], dp[i][j-a[i]][k-b[i]]+c[i])
ans = INF
for i in range(1, 10*N+1):
    for j in range(1, 10*N+1):
        if i * Mb == j * Ma and ans > dp[N][i][j]:
            ans = dp[N][i][j]
ans = -1 if ans == INF else ans
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
N, Ma, Mb = map(int, input().split())
a, b, c = [None] * N, [None] * N, [None] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
dp = [[[INF] * (10*N+1) for j in range(10*N+1)] for i in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
    for j in range(10*N+1):
        for k in range(10*N+1):
            if j >= a[i] and k >= b[i]:
                dp[i+1][j][k] = min(dp[i][j][k], dp[i][j-a[i]][k-b[i]]+c[i])
ans = INF
for i in range(1, 10*N+1):
    for j in range(1, 10*N+1):
        if i * Mb == j * Ma and ans < dp[N][i][j]:
            ans = dp[N][i][j]
ans = -1 if ans == INF else ans
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
N, Ma, Mb = map(int, input().split())
a, b, c = [None] * N, [None] * N, [None] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
dp = [[[INF] * (10*N+1) for j in range(10*N+1)] for i in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
    for j in range(10*N+1):
        for k in range(10*N+1):
            if j >= a[i] and k >= b[i]:
                dp[i+1][j][k] = min(dp[i][j][k], dp[i][j-a[i]][k-b[i]]+c[i])
ans = INF
for i in range(10*N+1):
    for j in range(10*N+1):
        if i * Mb == j * Ma:
            ans = min(ans, dp[N][i][j])
ans = -1 if ans == INF else ans
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_right
INF = float('inf')
N, Ma, Mb = map(int, input().split())
a, b, c = [None] * N, [None] * N, [None] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
hN = N // 2
dic1 = defaultdict(lambda : INF)
for i in range(1 << hN):
    _a, _b, _c = 0, 0, 0
    for j in range(hN):
        if (i >> j) & 1:
            _a += a[j]
            _b += b[j]
            _c += c[j]
    if _c < dic1[(_a, _b)]:
        dic1[(_a, _b)] = _c
dic2 = defaultdict(lambda : INF)
for i in range(1 << (N - hN)):
    _a, _b, _c = 0, 0, 0
    for j in range(N - hN):
        if (i >> j) & 1:
            _a += a[j]
            _b += b[j]
            _c += c[j]
    if _c < dic2[(_a, _b)]:
        dic2[(_a, _b)] = _c
dic2[(0, 0)] = INF
ans = INF
for d1 in dic1:
    for d2 in dic2:
        if (d1[0] + d2[0]) * Mb == (d1[1] + d2[1]) * Ma:
            ans = min(ans, dic1[d1] + dic2[d2])
ans = ans if ans < INF else -1
print(ans)

Submission status: Wrong Answer

Solution code:
N, Ma, Mb = map(int, input().split())
A = [0]*N
B = [0]*N
C = [0]*N

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

# print(N, Ma, Mb, A, B, C)

A = [Mb * a for a in A]
B = [Ma * b for b in B]
D = []
for i in range(N):
    D.append((A[i] - B[i], C[i]))
# print(N, Ma, Mb, A, B, C, D)

Dp = []
Dn = []
Dz = []
for d in D:
    if d[0] == 0:
        Dz.append(d)
    elif d[0] > 0:
        Dp.append(d)
    else:
        Dn.append(d)

Dp.sort(key=lambda x: x[0])
Dn.sort(key=lambda x: x[0])
Dz.sort(key=lambda x: x[1])
min_c = 100*41
if len(Dz) > 0:
    min_c = Dz[0][1]
# print(Dp, Dn, Dz, min_c)

Ds = Dn
Dl = Dp
# if len(Dp) < len(Dn):
#     Ds, Dl = Dp, Dn
# else:
#     Ds, Dl = Dn, Dp

if len(Ds) == 0 or len(Dl) == 0:
    if min_c == 100*41:
        print(-1)
    else:
        print(min_c)
    exit()

def calc(D, l):
    s = 0
    c = 0
    for i in range(len(D)):
        if (l >> i) & 1 != 0:
            s += D[i][0]
            c += D[i][1]
    return (s, c)

Ls = len(Ds)
Ll = len(Dl)
Ds_memo = []
Dl_memo = []

for ls in range(1 << (Ls - 1)):
    Ds_memo.append(calc(Ds, ls + 1))
for ll in range(1 << (Ll - 1)):
    Dl_memo.append(calc(Dl, ll + 1))

Ds_memo.sort(key=lambda x: x[1])
Dl_memo.sort(key=lambda x: x[0])

# print(Ds_memo, Dl_memo)

for ls in Ds_memo:
    s = ls[0]
    c = ls[1]
    # print('ls', ls, s, c)
    if c >= min_c:
        break
    for ll in Dl_memo:
        sl = ll[0]
        cl = ll[1]
        # print('ll', ll, sl, cl)
        if s + sl > 0:
            break
        if c + cl >= min_c:
            continue
        if s + sl == 0:
            min_c = c + cl

if min_c == 100*41:
    print(-1)
else:
    print(min_c)

Submission status: Wrong Answer

Solution code:
N, Ma, Mb = map(int, input().split())
A = [0]*N
B = [0]*N
C = [0]*N

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

# print(N, Ma, Mb, A, B, C)

A = [Mb * a for a in A]
B = [Ma * b for b in B]
D = []
for i in range(N):
    D.append((A[i] - B[i], C[i]))
# print(N, Ma, Mb, A, B, C, D)

Dp = []
Dn = []
Dz = []
for d in D:
    if d[0] == 0:
        Dz.append(d)
    elif d[0] > 0:
        Dp.append(d)
    else:
        Dn.append(d)

Dp.sort(key=lambda x: x[0])
Dn.sort(key=lambda x: x[0])
Dz.sort(key=lambda x: x[1])
min_c = 100*41
if len(Dz) > 0:
    min_c = Dz[0][1]
# print(Dp, Dn, Dz, min_c)

Ds = []
Dl = []
if len(Dp) < len(Dn):
    Ds, Dl = Dp, Dn
else:
    Ds, Dl = Dn, Dp

if len(Ds) == 0:
    if min_c == 100*41:
        print(-1)
    else:
        print(min_c)
    exit()

def calc(D, l):
    s = 0
    c = 0
    for i in range(len(D)):
        if (l >> i) & 1 != 0:
            s += D[i][0]
            c += D[i][1]
    return (s, c)

Ls = len(Ds)
Ll = len(Dl)
Ds_memo = []
Dl_memo = []

for ls in range(1 << (Ls - 1)):
    Ds_memo.append(calc(Ds, ls + 1))
for ll in range(1 << (Ll - 1)):
    Dl_memo.append(calc(Dl, ll + 1))

Ds_memo.sort(key=lambda x: x[1])
Dl_memo.sort(key=lambda x: x[0])

# print(Ds_memo, Dl_memo)

for ls in Ds_memo:
    s = ls[0]
    c = ls[1]
    # print('ls', ls, s, c)
    if c >= min_c:
        break
    for ll in Dl_memo:
        sl = ll[0]
        cl = ll[1]
        # print('ll', ll, sl, cl)
        if s < 0 and s + sl > 0:
            break
        if s > 0 and s + sl < 0:
            break
        if c + cl >= min_c:
            continue
        if s + sl == 0 and c + cl < min_c:
            min_c = c + cl

if min_c == 100*41:
    print(-1)
else:
    print(min_c)