Time Limit: 9 sec / Memory Limit: 1024 MB
配点 : 800 点
ストーリー
僕たちは敵の湧いてくる方角へと駆けた。敵を倒しながら獣道を行くと、酷く損傷して、辛うじて汽車のように見えるものがあった。
僕は急に、「行かねば」という焦燥感と、「行っていいのか」という不安との板挟みになった。
でも前へ、 それでも前へ。
問題文
N 両からなる汽車があります。 それぞれの車両には 3 つの部品があり、車両 k が出すことのできる速度はそれぞれの部品 A,B,C の持つパワー A_k,B_k,C_k の和で表されます。
どの部品も、0 以上 F 以下のパワーを持ちます。
汽車の各車両の出すことのできる速度が降順になっていないと、進む途中で汽車が崩壊してしまいます。
あなたといろはちゃんはなるべく少ない部品を改造して、汽車が崩壊しないようにしたいと思っています。改造しても、0 以上 F 以下のパワーを持った部品しか作ることはできません。
すべての i<j に対して、(車両 i が出すことのできる速度) \geq (車両 j が出すことのできる速度) となるように、改造する部品の個数の最小値を求めてください。
制約
- 入力はすべて整数
- 1 \leq N \leq 2\times10^5
- 1 \leq F \leq 10^{10}
- 0 \leq A_k, B_k, C_k \leq F
(制約の上限が間違っていたため修正しました 修正日時 : 2019/05/03 19:06)
部分点
- N \leq 3000 を満たすテストケースすべてに正解した場合、300 点が与えられる。
入力
入力は以下の形式で標準入力から与えられます。
N F A_1 B_1 C_1 A_2 B_2 C_2 : A_N B_N C_N
出力
改造する部品の個数の最小値を出力してください。
入力例 1
3 100 80 100 60 30 50 70 90 10 80
出力例 1
1
例えば、車両 2 の部品 B のパワーを 85 に変えると、各車両の合計が 240, 185, 180 になり汽車が連結のまま進めるようになります。
入力例 2
4 100 30 10 40 10 50 90 20 60 50 30 50 80
出力例 2
2
例えば、車両 1 の部品 B のパワーを 90 にして、車両 4 の部品 C のパワーを 10 に変えると、各車両の合計が 170, 150, 130, 90 になり汽車が連結のまま進めるようになります。
入力例 3
4 100 0 0 0 0 0 100 100 100 0 100 100 100
出力例 3
4
全車両の出すことができる速度を同じにするのが最適な場合もあります。
入力例 4
10 100 100 37 49 100 37 49 100 37 49 100 37 49 100 37 49 100 37 49 100 37 49 100 37 49 100 37 49 100 37 49
出力例 4
0
入力例 5
5 10000000000 1701355307 429870732 6220675835 286943432 6531822025 3789827719 2265045229 9897189805 5070400071 8975758188 6810134144 5515765460 7476103030 3953670242 7426723712
出力例 5
4