問題一覧 > 通常問題

No.1615 Double Down

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 : 👑 ygussanyygussany / テスター : 👑 tatyamtatyam iaNTUiaNTU
1 ProblemId : 6380 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-21 18:13:07

問題文

$N$ 人の買い手が居るオークションで $M$ 個の商品が出品されています. このオークションでは,

  • 各商品は高々 $1$ 人の買い手に売ることができ,
  • 各買い手は高々 $1$ 個の商品を買うことができます.
どの商品をどの買い手にいくらで売るかは,オークショニアの D.D. 君が自由に決められます. ただし,各買い手は各商品がいくら以下なら買うか(あるいは,いくらであっても買わないこと)を心に決めており,その意思に反する売り方はできません.

売り値を細かく決めるのが億劫だった D.D. 君は,各商品 $j$ に対して以下の手順を実行しました.

  • はじめに,商品 $j$ を買う意思がある買い手全員に挙手をさせる.
  • $k = 0, 1, \dots, K$ に対し,商品 $j$ が $2^k$ 円で売られた場合に買う意思のある買い手には挙手を続けさせ,そうでない買い手には手を下ろさせる.

「買い手 $X$ が商品 $Y$ に対して $k = Z$ 時点まで挙手を続けた」という情報が $L$ 個与えられます. 面倒くさがり屋な D.D. 君の代わりに,どの商品をどの買い手にいくらで売るかを上手く決めて,総売り上げを最大化してあげてください. ただし,与えられる情報から買い手の買う意思が明確であるような売り方のみが可能であるとします.

入力

$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)$
  • $X_i \neq X_j$ または $Y_i \neq Y_j \ \ (1 \le i < j \le L)$
  • 入力は全て整数である.
  • 買い手には $1, 2, \dots, N$ の番号が付いている.
  • 商品には $1, 2, \dots, M$ の番号が付いている.
  • 各 $(X_i, Y_i, Z_i)$ は「買い手 $X_i$ に商品 $Y_i$ を $2^{Z_i}$ 円(以下)で売ることができる」ことを表す.

出力

各商品の買い手と売り値の組合せ(売らない場合を含む)を決めたときにあり得る総売り上げ(円)の最大値を出力してください.

サンプル

サンプル 1
入力
2 2 2 4
1 1 2
1 2 2
2 1 1
2 2 0
出力
6

買い手 $1$ に商品 $1$ を,買い手 $2$ に商品 $2$ を売ると,売り値はそれぞれ最大で $2^2 = 4$ 円と $2^0 = 1$ 円となり,総売り上げは $4 + 1 = 5$ 円となります. 買い手 $1$ に商品 $2$ を,買い手 $2$ に商品 $1$ を売ると,売り値はそれぞれ最大で $2^2 = 4$ 円と $2^1 = 2$ 円となり,総売り上げは $4 + 2 = 6$ 円となります. 後者の方が高くなるので,$6$ を出力します.

サンプル 2
入力
3 3 4 3
1 1 4
2 1 3
1 2 2
出力
16

何も買う意思が無い買い手が居たり,誰も買う意思を持ってくれない商品があったりすることもあります. また,売る商品の数が最大になるとは限りません.

サンプル 3
入力
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
出力
4026531840

答えは 32bit 整数に収まらないことがあります.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。