問題一覧 > 通常問題

No.1615 Double Down

レベル : / AI推定難易度 : 3125 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : ygussany / テスター : tatyam iaNTU
お気に入りにしたユーザー ProblemId : 6380 / 自分の提出
問題文最終更新日: 2026-10-23 19:08:43
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 305 (順位表) の他の問題:

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.
The auctioneer, D.D., is free to decide which item to sell to which buyer and at what price. However, each buyer has decided in advance, for each item, the maximum price at which they would buy it (or that they would not buy it at any price), and the items cannot be sold in a way that goes against their will.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。