No.165 四角で囲え!

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 60
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
6 ProblemId : 264 / 出題時の順位表

問題文

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

入力

$N$ $B$
$X_0$ $Y_0$ $P_0$
$X_1$ $Y_1$ $P_1$
 ...
$X_{N-1}$ $Y_{N-1}$ $P_{N-1}$

点の数$N$が与えられる。($1 \le N \le 400$)
超えてはならない点数$B$が与えられる。($1 \le B \le 4000000$)
整数座標上の$N$個の点の情報が$N$行で与えられる。
$X_i$,$Y_i$は$i$番目の座標($X_i$,$Y_i$)の情報。($-1000000000 \le X_i,Y_i \le 1000000000$)
$P_i$は$i$番目の座標の得点。($1 \le P_i \le 10000$)
$i \neq j $であれば$(X_i,Y_i) \neq (X_j,Y_j)$である

出力

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

サンプル

サンプル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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。