# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
886846 | rafc | Knapsack (NOI18_knapsack) | Pypy 3 | 30 ms | 18372 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import sys
def main():
read = sys.stdin.readline
s, n = (int(i) for i in read().split())
values = []
weights = []
quantities = []
sorted_values = []
for index in range(n):
v_i, w_i, k_i = (int(i) for i in read().split())
values.append(v_i)
weights.append(w_i)
quantities.append(k_i)
sorted_values.append((v_i / w_i, index))
sorted_values.sort(reverse=True)
curr_weight = 0
curr_total = 0
for i in range(len(sorted_values)):
_, idx = sorted_values[i]
value = values[idx]
weight = weights[idx]
quantity = quantities[idx]
remaining_weight = s - curr_weight
quantity_to_grab = min(remaining_weight // weight, quantity)
curr_total += quantity_to_grab * value
curr_weight += quantity_to_grab * weight
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |