← 返回题目列表

AtCoder · dwango2015_prelims_4

D. 出租车

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

問題文

某星球,编程大赛《来自Dwango的挑战》预赛正在进行,通过预赛的选手被邀请前往决赛场地。

这颗星星有一个长度 L 环线 1 环路上有一本书。 有 N 个城市。在城市里 1 从 N 之前的数字是城市 它们从 1 开始按顺时针升序分配。

决赛是 1 将在多个城市举办,每个场馆都会进行现场直播。

对于每个城市和每个场馆,确定居住在该城市的决赛入围者人数以及进入场馆的决赛入围者人数。

进入会场的决赛选手总数与决赛选手总数完全匹配。

根据城市的不同,居住在该城市的决赛选手人数可能与进入场地的决赛选手人数不匹配,在这种情况下,可能需要通过出租车在城市之间运送决赛选手。

出租车在环线上行驶,入围者 1 每个人的成本等于行进的距离。

编写一个程序来找出可能的最小移动总成本。


入力

输入是按以下格式从标准输入给出的。

N L
a_1 b_1 c_1
a_2 b_2 c_2
:
a_N b_N c_N
  • 1 线显示城市数量。 N (2 ≦ N ≦ 100,000) 和圆线的长度 L (N ≦ L ≦ 10,000,000) 用空格分隔。
  • 2 从行 N 行提供有关每个城市的信息。其中 i (1 ≦ i ≦ N) 在线 写在方格 3 整数 a_i (0 ≦ a_i ≦ L - 1), b_i (0 ≦ b_i ≦ 100,000), c_i (0 ≦ c_i ≦ 100,000) 用空格分隔。这是一座城市 i 是环路上的一个城市。 从 1 顺时针方向 a_i 再往前走,城市 i 的决赛入围者人数为 b_i 人们,c_i = 0 奈良市 i 没有场地;c_i > 0 奈良市 i 包含决赛入围者 c_i 表示邀请某人。
  • a_1 = 0 和所有整数 对于 i (2 ≦ i ≦ N) 反对 a_i > a_{i-1} 成立。
  • b_1 + ... + b_N = c_1 + ... + c_N 。
  • b_1 + ... + b_N ≧ 1 。

部分点

这个问题有部分要点。 如果您正确回答所有

  • N ≦ 5,000 和 即使增加或减少 b_1 + ... + b_N ≦ 5,000 的数据集 如果您正确回答 1 , 您将获得15 积分。 如果您正确回答所有
  • N ≦ 5,000 的数据集 如果您正确回答 2 ,您将收到 30 积分。 如果您正确回答所有
  • 没有附加约束的数据集 如果您正确回答所有 3 ,您将得到以上内容 2 加上更多 获得 55 分,总体 100 积分。 如果您正确回答所有

出力

总移动成本的最小可能值为 在 1 行输出。还在输出末尾添加换行符。


入力例1

7 30
0 3 6
1 2 2
4 5 4
19 0 1
20 4 4
21 1 0
27 3 1

出力例1

12

考虑以下动作。

  • 都市 3 决赛入围者 1 人就是城 逆时针乘坐出租车前往 1 。搬家成本为 乘出租车顺时针前往 4 × 1 = 4 。
  • 都市 6 决赛入围者 1 人就是城 逆时针乘坐出租车前往 4 。搬家成本为 乘出租车顺时针前往 2 × 1 = 2 。
  • 都市 7 决赛入围者 2 人就是城 逆时针乘坐出租车前往 1 。搬家成本为 2 据人士称 3 × 2 = 6 。

由于此次搬迁,搬迁后的任何城市,如果有场地,可以进入场地的人数等于该城市的入围选手人数,并且任何入围选手都可以进入场地。

总移动成本为 4 + 2 + 6 = 12 并且该值是最小值。


入力例2

6 25
0 10 1
3 0 1
9 0 2
12 0 3
13 0 2
21 0 1

出力例2

85