← 返回题目列表

AtCoder · iroha2019_day4_f

F. 没有路径的路径

中文机器翻译题面 查看原题

配点 : 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

解説

strong>比赛结束后,将在此处添加该问题的个人解释链接。 </strong> 解説