No.1615 Double Down
Problem Statement
At an auction with $N$ buyers, $M$ items are put up for sale. In this auction,
- each item can be sold to at most $1$ buyer, and
- each buyer can buy at most $1$ item.
Since D.D. found it tedious to determine selling prices in detail, he carried out the following procedure for each item $j$.
- First, have all buyers who are willing to buy item $j$ raise their hands.
- For $k = 0, 1, \dots, K$, have the buyers who are willing to buy item $j$ if it is sold at $2^k$ yen keep their hands raised, and have the other buyers lower their hands.
You are given $L$ pieces of information of the form "buyer $X$ kept their hand raised for item $Y$ up to the point $k = Z$". On behalf of the lazy D.D., decide well which item to sell to which buyer and at what price, so as to maximize the total sales. Note that only sales for which the buyer's willingness to buy is clear from the given information are possible.
Input
$N\ \ M\ \ K\ \ L$
$X_1\ \ Y_1\ \ Z_1$
$X_2\ \ Y_2\ \ Z_2$
$\vdots$
$X_L\ \ Y_L\ \ Z_L$
- $1 \le N, M \le 25000$
- $0 \le K \le 30$
- $0 \le L \le 25000$
- $1 \le X_i \le N \ \ (1 \le i \le L)$
- $1 \le Y_i \le M \ \ (1 \le i \le L)$
- $0 \le Z_i \le K \ \ (1 \le i \le L)$
- The same pair $(X_i, Y_i)$ may be given multiple times.
- All input values are integers.
- The buyers are numbered $1, 2, \dots, N$.
- The items are numbered $1, 2, \dots, M$.
- Each $(X_i, Y_i, Z_i)$ means that "item $Y_i$ can be sold to buyer $X_i$ for $2^{Z_i}$ yen (or less)".
Output
Output the maximum possible total sales (in yen) when the combination of buyer and selling price for each item (including the option of not selling it) is decided.
Sample
Sample 1
Input
2 2 2 4 1 1 2 1 2 2 2 1 1 2 2 0
Output
6
If item $1$ is sold to buyer $1$ and item $2$ to buyer $2$, the selling prices are at most $2^2 = 4$ yen and $2^0 = 1$ yen respectively, and the total sales are $4 + 1 = 5$ yen. If item $2$ is sold to buyer $1$ and item $1$ to buyer $2$, the selling prices are at most $2^2 = 4$ yen and $2^1 = 2$ yen respectively, and the total sales are $4 + 2 = 6$ yen. The latter is higher, so output $6$.
Sample 2
Input
3 3 4 3 1 1 4 2 1 3 1 2 2
Output
16
There may be buyers who are not willing to buy anything, and items that nobody is willing to buy. Also, the number of items sold is not necessarily maximized.
Sample 3
Input
5 7 30 16 3 1 29 1 3 29 5 6 28 4 7 30 1 1 30 1 7 29 3 6 30 5 3 28 2 1 29 4 3 30 4 2 28 4 1 29 1 5 30 2 4 29 3 3 29 3 4 29
Output
4026531840
The answer may not fit in a 32-bit integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
tatyam