#P16246. [IIOT2022]Discount Optimisation折扣优化

[IIOT2022]Discount Optimisation折扣优化

题目描述

超市出售 NN 件互不相同的商品,编号为 0,1,…,N−10,1,\ldots,N-1。

商品 ii 具有:

  • 原价 PiP_i;
  • 折扣价 SiS_i;
  • 一个优惠码 RiR_i。

Tommaso 选择购买某个非空商品子集。结算时,对于每件被购买的商品 ii:

  • 当且仅当购物车中至少有一件商品 jj 满足 Rj=iR_j=i 时,商品 ii 按折扣价 SiS_i 结算;
  • 否则,商品 ii 按原价 PiP_i 结算。

同一种商品不能购买多件;多个相同优惠码不会产生额外折扣。商品也可以给自身提供优惠码,即 Ri=iR_i=i。

设所选商品的原价总和为 PtotP_{\mathrm{tot}},实际支付金额为 PdiscountP_{\mathrm{discount}},折扣百分比为

$$100\left(1-\frac{P_{\mathrm{discount}}}{P_{\mathrm{tot}}}\right).$$

求可以获得的最大折扣百分比。

输入格式

第一行一个整数 NN。

接下来 NN 行,第 ii 行包含三个整数 Pi,Si,RiP_i,S_i,R_i。

输出格式

输出一个浮点数,表示最大折扣百分比。

当输出与标准答案的绝对误差不超过 10−610^{-6} 时视为正确。

数据范围

  • 1≤N≤1000001\le N\le 100000;
  • 0≤Si<Pi≤100000\le S_i<P_i\le10000;
  • 0≤Ri<N0\le R_i<N。

子任务

子任务 分值 限制
1 0 样例
2 10 对所有 ii,Ri=iR_i=i
3 15 N≤20N\le20
4 20 N≤1000N\le1000
5 对所有 ii,Ri≤iR_i\le i
6 25 R0=N−1R_0=N-1,且对所有 i>0i>0,Ri=i−1R_i=i-1
7 10 无额外限制

样例 1

输入1
6
100 90 1
10 9 2
90 20 5
100 80 2
40 30 3
100 10 3

输出1
80.000000000

购买商品 1,2,51,2,5 时,原价总和为 200200,实际支付 P1+S2+S5=40P_1+S_2+S_5=40,折扣为 80%80\%。

样例 2

输入2
5
100 70 1
10 3 2
11 3 3
12 3 1
10 9 4

输出2
72.727272727