Submission #1592659


Source Code Expand

import fractions

n, ma, mb = map(int,input().split())
a = [0] * (n + 1)
b = [0] * (n + 1)
c = [0] * (n + 1)
for i in range(1, n + 1):
    a[i], b[i], c[i] = map(int,input().split())

#iまでの薬品で、aがj(g),bがk(g)となるときの最小コスト
dp = [[[float('inf') for i in range(n + 1)] for j in range(401)] \
    for k in range(401)]

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

for i in range(1, n + 1):
    for j in range(401):
        for k in range(401):
            if dp[k][j][i - 1] == float('inf'):
                continue
            # i番目を買うか、買わないか
            if j < a[i] or k < b[i]:
                dp[k][j][i] = dp[k][j][i - 1]
            else:
                dp[k][j][i] = min(dp[k][j][i - 1], \
                    dp[k - b[i]][j - a[i]][i - 1] + c[i])

i = 1
ans = float('inf')
while True:
    if i * ma > 400 or i * mb > 400:
        break
    ans = min(ans, dp[i * mb][i * ma][n])
    i += 1

if ans == float('inf'):
    ans = -1

print(ans)

Submission Info

Submission Time
Task D - Mixing Experiment
User ophelia
Language PyPy3 (2.4.0)
Score 0
Code Size 1016 Byte
Status WA
Exec Time 2112 ms
Memory 125928 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 1
WA × 1
AC × 5
WA × 6
TLE × 9
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt
Case Name Status Exec Time Memory
sample_01.txt WA 482 ms 83160 KB
sample_02.txt AC 381 ms 83032 KB
subtask_1_01.txt AC 608 ms 88152 KB
subtask_1_02.txt AC 431 ms 83032 KB
subtask_1_03.txt AC 616 ms 88152 KB
subtask_1_04.txt AC 917 ms 98648 KB
subtask_1_05.txt WA 1101 ms 98648 KB
subtask_1_06.txt WA 1385 ms 110680 KB
subtask_1_07.txt WA 1576 ms 110552 KB
subtask_1_08.txt WA 1699 ms 110552 KB
subtask_1_09.txt WA 2000 ms 124248 KB
subtask_1_10.txt TLE 2110 ms 125928 KB
subtask_1_11.txt TLE 2111 ms 124120 KB
subtask_1_12.txt TLE 2112 ms 124504 KB
subtask_1_13.txt TLE 2111 ms 124504 KB
subtask_1_14.txt TLE 2111 ms 124504 KB
subtask_1_15.txt TLE 2111 ms 124504 KB
subtask_1_16.txt TLE 2111 ms 124504 KB
subtask_1_17.txt TLE 2112 ms 124504 KB
subtask_1_18.txt TLE 2111 ms 124504 KB