Submission #1592733


Source Code Expand

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 = [[[10 ** 15 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 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 = 10 ** 15
while True:
    if i * ma > 400 or i * mb > 400:
        break
    ans = min(ans, dp[i * mb][i * ma][n])
    i += 1

if ans == 10 ** 15:
    ans = -1

print(ans)

Submission Info

Submission Time
Task D - Mixing Experiment
User ophelia
Language PyPy3 (2.4.0)
Score 400
Code Size 854 Byte
Status AC
Exec Time 1824 ms
Memory 115164 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 20
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 AC 340 ms 58972 KB
sample_02.txt AC 268 ms 58332 KB
subtask_1_01.txt AC 413 ms 63324 KB
subtask_1_02.txt AC 292 ms 58204 KB
subtask_1_03.txt AC 409 ms 63452 KB
subtask_1_04.txt AC 591 ms 74204 KB
subtask_1_05.txt AC 689 ms 73948 KB
subtask_1_06.txt AC 948 ms 86108 KB
subtask_1_07.txt AC 1018 ms 86364 KB
subtask_1_08.txt AC 1136 ms 86108 KB
subtask_1_09.txt AC 1303 ms 100060 KB
subtask_1_10.txt AC 1429 ms 99804 KB
subtask_1_11.txt AC 1729 ms 115164 KB
subtask_1_12.txt AC 1771 ms 115164 KB
subtask_1_13.txt AC 1737 ms 115164 KB
subtask_1_14.txt AC 1758 ms 115164 KB
subtask_1_15.txt AC 1761 ms 115164 KB
subtask_1_16.txt AC 1824 ms 115164 KB
subtask_1_17.txt AC 1714 ms 114908 KB
subtask_1_18.txt AC 1745 ms 115164 KB