問題一覧 > 通常問題

No.165 四角で囲え！

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 97
作問者 : nmnmnmnmnmnmnm
8 ProblemId : 264 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:31

問題文

XY座標上に異なるN個の整数座標上の点が与えられる。
各点にはそれぞれ得点が定められている。
A君はX軸、Y軸に辺が平行な四角形で点と重ならないように多くの点を囲いたい。
ただし、条件として囲った点の得点の合計がB以下でないといけない。
囲える点の最大の数はいくつだろうか？

入力

N B
X0 Y0 P0
X1 Y1 P1
 ...
XN−1 YN−1 PN−1

点の数Nが与えられる。(1≤N≤400)
超えてはならない点数Bが与えられる。(1≤B≤4000000)
整数座標上のN個の点の情報がN行で与えられる。
Xi,Yiはi番目の座標(Xi,Yi)の情報。(−1000000000≤Xi,Yi≤1000000000)
Piはi番目の座標の得点。(1≤Pi≤10000)
i≠jであれば(Xi,Yi)≠(Xj,Yj)である

出力

囲える最大の点の数を答えよ。
ただし、最後に改行を忘れずに。

サンプル

サンプル1
入力
3 3
-1 0 1
0 0 2
1 0 3
出力
2

3つの点(-1,0)、(0,0)、(1,0)がある。
それぞれ得点は1点、2点、3点である。
(-1,0)と(0,0)の合計点数は3以下なのでこの2点を四角形で囲うことができる。

サンプル2
入力
3 3
-1 0 1
0 0 3
0 1 2
出力
1

3つの点(-1,0)、(0,0)、(0,1)がある。
それぞれ得点は1点、3点、2点である。
(-1,0)か(0,0)か(0,1)のいずれか1点を四角形で囲うことができる。
四角形で囲うということは(0,0)を囲わずに(-1,0)と(0,1)のみ囲うことができないことに注意せよ。

サンプル3
入力
5 3
-1 0 100
0 1 100
0 0 2
0 -1 100
1 0 100
出力
1

5つの点がある。
中央の1点のみ四角形で囲うことができる。

サンプル4
入力
12 345
-3 74 32
68 -19 9
46 2 48
-20 -42 24
18 3 85
-31 -76 8
-80 32 82
-47 74 34
68 2 37
36 74 69
-50 -55 65
-55 18 26
出力
8

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