Submission #1592681


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 = [[[10**15 for i in range(n + 1)] for j in range(401)] \
    for k in range(401)]

dp[0][0][0] = 0
sa = [0] * (n + 1)
sb = [0] * (n + 1)

for i in range(1, n + 1):
    sa[i] = sa[i - 1] + a[i]
    sb[i] = sb[i - 1] + b[i]

for i in range(1, n + 1):
    for j in range(401):
        if j > sa[i]:
            break
        for k in range(401):
            if k > sb[i]:
                break
            # 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 = 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 1148 Byte
Status AC
Exec Time 545 ms
Memory 137176 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 387 ms 87768 KB
sample_02.txt AC 308 ms 80600 KB
subtask_1_01.txt AC 326 ms 88024 KB
subtask_1_02.txt AC 310 ms 82136 KB
subtask_1_03.txt AC 324 ms 88024 KB
subtask_1_04.txt AC 344 ms 98904 KB
subtask_1_05.txt AC 349 ms 99800 KB
subtask_1_06.txt AC 368 ms 111576 KB
subtask_1_07.txt AC 378 ms 111576 KB
subtask_1_08.txt AC 377 ms 111576 KB
subtask_1_09.txt AC 464 ms 124120 KB
subtask_1_10.txt AC 459 ms 124120 KB
subtask_1_11.txt AC 478 ms 136920 KB
subtask_1_12.txt AC 545 ms 136920 KB
subtask_1_13.txt AC 529 ms 137176 KB
subtask_1_14.txt AC 507 ms 136920 KB
subtask_1_15.txt AC 505 ms 136920 KB
subtask_1_16.txt AC 516 ms 137176 KB
subtask_1_17.txt AC 526 ms 137176 KB
subtask_1_18.txt AC 518 ms 137176 KB