[NOI2007]货币兑换Cash

Time Limit:5000MS  Memory Limit:65536K
Total Submit:84 Accepted:36
Case Time Limit:1000MS

Description

Input

第一行两个正整数N、S，分别表示小Y 能预知的天数以及初始时拥有的钱数。
接下来N 行，第K 行三个实数AK、BK、RateK，意义如题目中所述

Output

只有一个实数MaxProfit，表示第N 天的操作结束时能够获得的最大的金钱
数目。答案保留3 位小数。

Sample Input

3 100
1 1 1
1 2 2
2 2 3

Sample Output

225.000

Hint

测试数据设计使得精度误差不会超过10-7。
对于40%的测试数据，满足N ≤ 10；
对于60%的测试数据，满足N ≤ 1 000；
对于100%的测试数据，满足N ≤ 100 000；

Source

我又使用随机化算法强行AC了这道题目囧。。。。
WA+TLE N次。。。累成SB囧。。。
首先转化成维护凸壳大家都知道。。
我的办法基本上就是维护一个链表的数组。。
然后根据算法导论说的可以在Sqrt（N）的时间内在这个数组里面找一个元素。。
所以插入跟维护都可以做到Sqrt（N）。。。
然后硬做。。
就A掉了囧。。。
Code：
http://www.ideone.com/8hGL1