题目详情题解（0）讨论（0）提交记录（0）

AT_joi2026final_h.かかし 2 (Scarecrows 2)

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

JOI 村には，広大な畑がある． この畑は無限に広がる $ xy $ 座標平面で表され， $ x $ 軸正の向きが東方向， $ y $ 軸正の向きが北方向である．

JOI 村の村長は，畑を外敵から守るために，畑にいくつかのかかしを配置しようと考えている． 配置されたそれぞれのかかしは，その場所と向きに応じて，平面上の特定の領域を守ることができる．

現在，かかしを配置するための $ N $ 個の計画が提案されており， $ 1 $ から $ N $ までの番号が付けられている． 計画 $ i $ ( $ 1\leqq i\leqq N $ ) を実行するために必要なコストは $ C_i $ であり，その内容は整数 $ T_i, X_i, Y_i $ を用いて以下のように表される．

  • $ T_i = 1 $ のとき，かかし $ 1 $ 体を点 $ (X_i,Y_i) $ に西向きに配置する．このかかしは平面上の $ x \leqq X_i $ の領域を守る．
  • $ T_i = 2 $ のとき，かかし $ 1 $ 体を点 $ (X_i,Y_i) $ に東向きに配置する．このかかしは平面上の $ x \geqq X_i $ の領域を守る．
  • $ T_i = 3 $ のとき，かかし $ 1 $ 体を点 $ (X_i,Y_i) $ に南向きに配置する．このかかしは平面上の $ y \leqq Y_i $ の領域を守る．
  • $ T_i = 4 $ のとき，かかし $ 1 $ 体を点 $ (X_i,Y_i) $ に北向きに配置する．このかかしは平面上の $ y \geqq Y_i $ の領域を守る．

村長は，これらの $ N $ 個の計画のうちいくつかを選んで実行することで，できるだけ少ない合計コストで，平面上のどの点も $ K $ 体以上のかかしによって守られているようにしたいと考えている．ただし， $ N $ 個の計画においてかかしを配置する点の座標はすべて相異なることが保証される．

かかしを配置する計画の情報が与えられたとき，いくつかの計画を選んで実行することで平面上のどの点も $ K $ 体以上のかかしによって守られているようにすることが可能かどうか判定し，可能な場合は実行する計画の合計コストの最小値を求めるプログラムを作成せよ．

输入格式

入力は以下の形式で標準入力から与えられる．

$ N $ $ K $ $ T_1 $ $ X_1 $ $ Y_1 $ $ C_1 $ $ T_2 $ $ X_2 $ $ Y_2 $ $ C_2 $ $ \vdots $ $ T_{N} $ $ X_{N} $ $ Y_{N} $ $ C_{N} $

输出格式

平面上のどの点も $ K $ 体以上のかかしによって守られているように配置するために必要な合計コストの最小値を出力せよ． ただし，条件を満たす計画の選び方が存在しない場合は -1 を出力せよ．

输入输出样例

  • 输入#1

    7 1
2 45 21 96
1 5 85 70
1 36 73 78
1 28 12 80
2 15 49 21
1 45 11 96
2 63 26 19

    输出#1

    99

  • 输入#2

    7 3
2 45 21 96
1 5 85 70
1 36 73 78
1 28 12 80
2 15 49 21
1 45 11 96
2 63 26 19

    输出#2

    -1

  • 输入#3

    19 5
2 36 42 64
2 7 89 74
1 0 15 82
1 10 63 55
2 58 28 19
2 45 91 3
2 2 34 97
1 7 55 82
1 17 12 17
2 59 76 82
1 7 4 68
2 51 98 47
1 51 21 38
2 19 0 72
1 73 73 11
2 62 19 74
1 45 7 94
1 79 32 21
1 85 50 21

    输出#3

    315

  • 输入#4

    8 3
4 4 21 80
2 59 65 69
4 63 36 3
2 29 13 23
1 37 45 95
2 79 14 89
3 91 54 76
1 85 46 62

    输出#4

    328

说明/提示

小課題

  1. ( $ 4 $ 点) $ K = 1 $ ．
  2. ( $ 6 $ 点) $ K \leqq 2 $ ．
  3. ( $ 11 $ 点) $ N \leqq 500 $ ， $ K \leqq 300 $ ．
  4. ( $ 27 $ 点) $ N \leqq 6,000 $ ．
  5. ( $ 19 $ 点) $ N \leqq 75,000 $ ．
  6. ( $ 33 $ 点) 追加の制約はない．

Sample Explanation 1

例えば計画 $ 3,5 $ を実行すると，以下のようにかかしが配置される．

  • 計画 $ 3 $ では，かかし $ 1 $ 体を点 $ (36,73) $ に西向きに配置する．コストは $ 78 $ である．
  • 計画 $ 5 $ では，かかし $ 1 $ 体を点 $ (15,49) $ に東向きに配置する．コストは $ 21 $ である．

このとき，座標平面上のどの点も $ 1 $ 体以上のかかしで守られている．例えば，点 $ (0, 0) $ は計画 $ 3 $ で点 $ (36,73) $ に西向きに配置したかかしによって守られている． また，合計コストは $ 78+21=99 $ である． これより少ない合計コストで平面上のすべての点を $ 1 $ 体以上のかかしで守ることはできないので， $ 99 $ を出力する．

この入力例はすべての小課題の制約を満たす．

Sample Explanation 2

入力例 $ 1 $ とは $ K $ の値のみが異なる．

座標平面上のすべての点を $ 3 $ 体以上のかかしによって守ることはできないため，-1 を出力する．

この入力例は小課題 $ 3,4,5,6 $ の制約を満たす．

Sample Explanation 3

この入力例は小課題 $ 3,4,5,6 $ の制約を満たす．

Sample Explanation 4

この入力例は小課題 $ 3,4,5,6 $ の制約を満たす．

Constraints

  • $ 1 \leqq K \leqq N \leqq 200,000 $ ．
  • $ T_i $ は $ 1, 2, 3, 4 $ のいずれかである ( $ 1 \leqq i \leqq N $ )．
  • $ 0 \leqq X_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )．
  • $ 0 \leqq Y_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )．
  • $ (X_i, Y_i) \neq (X_j, Y_j) $ ( $ 1 \leqq i < j \leqq N $ )．
  • $ 0 \leqq C_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )．
  • 入力される値はすべて整数である．

输入解题思路，AI测评打分。不知道怎么写?

首页