Akcija
레이팅 미적용의견: 0
Christmas, a time for giving. Mr. Malnar is in need of gift ideas. Although deep in
thought, the television program grabs his attention: “Special offer! This amazing
product is on sale for just \(w\) kunas. Call now because the offer is available only
if you call within the next \(d\) minutes. But that’s not all...”
There are \(n\) different products on sale, where the \(i-th\) product has a cost of \(w@@RISE_MATH_BLOCK_0@@i\) (inclusive). Making a call to place
an order requires one minute. A subset of products is called obtainable if it is possible to make a sequence
of calls which order those products while meeting the mentioned deadlines. No product can be ordered
more than once.
Mr. Malnar intends to buy as many products as possible, at the least possible price, but he’s not yet
sure which products he should buy. He compares two obtainable subsets in the following way: the better
obtainable subset is the one with more products, and if they have equal size, it’s the one that has a smaller
total cost (sum of costs of chosen products).
Mr. Malnar will rank the obtainable subsets in the described manner and he will take into consideration \(k\)
of the best ones. Write a program which determines the size and the total cost for \(k\) of the best obtainable
subsets.
Subtask 1 (10 points): \(k = 1\), \(w_{1}\) = ... = \(w_{n}\)
Subtask 2 (20 points): \(k = 1\)
Subtask 3 (20 points): \(k = 2\)
Subtask 4 (10 points): \(1 \le n \le 20\)
Subtask 5 (30 points): \(1 \le n\), \(k \le 100\)
Subtask 6 (20 points): No additional constraints.
The first line contains positive integers \(n\) and \(k - th\)e number of different products and the number of
obtainable subsets to be taken into consideration, respectively. \(k\) will be less than or equal to the total
number of obtainable subsets.
The following \(n\) lines contain two positive integers \(w@@RISE_MATH_BLOCK_0@@i \le 10^{9}\)) and \(d@@RISE_MATH_BLOCK_1@@i \le n\)) - the cost of the
\(i-th\) product and the last minute for which the offers stands, respectively.
In the \(i-th\) line print the size and the total cost of the \(i-th\) best obtainable subset.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(k = 1\), \(w_{1}\) = ... = \(w_{n}\) |
2 | 20점 | \(k = 1\) |
3 | 20점 | \(k = 2\) |
4 | 10점 | \(1 \le n \le 20\) |
5 | 30점 | \(1 \le n\), \(k \le 100\) |
6 | 20점 | No additional constraints. |
3 1
1 1
1 1
1 32 24 3
1 1
10 1
2 3
10 33 13
3 22
2 32 4
1 1
2 22 3
1 1
1 2
0 0Clarification of the second example:
Products 1 and 2 can’t simultaneously be in an obtainable subset, so the three best obtainable subsets are
{1, 3, 4}, {2, 3, 4} i {1, 3}.
평가 및 의견
Akcija
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Akcija