Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

诡意行商 (roguetrader)

题目描述

坎诺特开了一家商店,商店里共 $n$ 个商品,第 $i$ 个商品卖 $a_i$ 块钱,其价值为 $c_i$。 小鱼人要去商店里买东西。它会按照最优的策略买东西,即如果它有 $x$ 块钱,它会在买的东西需要付不超过 $x$ 块钱的同时 价值和最大。

由于小鱼人很有钱,坎诺特打算坑一把小鱼人。坎诺特会选取一个区间 ,对这个区间里面的商品进行涨价。第 $i$ 个商 品涨价后的价格为 $a_i$。

坎诺特知道小鱼人有不超过 块钱且认为小鱼人的钱数在 $[1,V]$ 中均匀随机。因此坎诺特想知道有多少区间 满足给 内的商品涨价后,小鱼人购买商品价值和的期望不超过 $L$。 输入格式

第一行三个数 。接下来 $n$ 行,每行三个数 $a_i,b_i,c_i$,含义如题目所述。

4 4 2
1 2 1
2 4 2
1 3 2
3 5 3
3

大样例