陶陶的背包
测试数据来自 system/1678
背景
陶陶很喜欢做白日梦。
描述
有一天,陶陶梦见他来到了一个遍地黄金的地方。不过奇怪的是这些黄金都排成了一条直线。
正当陶陶欢喜且纳闷的时候,curimit出现了!curimit说:"你想不想取走这些黄金?"陶陶说:"嗯~~。" curimit说:"你只要回答我Q个问题,如果你都回答对了,那么这些黄金都归你。首先,我告诉你第i块黄金的体积v[i]和价值e[i]。然后,我问你Q个问题,每个问题都是询问:如果你有一个大小为V的背包,并且只允许你带走编号从l到r的黄金,那么你最多能带走多少价值的黄金。"陶陶听后立刻晕了过去,醒来之后陶陶第一个想到的就是你,他想要你帮他来回答这Q个问题,并且答应你事成之后,与你0:0平分掉这些黄金(因为在做白日梦)。
注:黄金是可以分割的,即你可以取走一块黄金的3/5,这样的话,3/5块黄金的体积和价值都是原来的3/5。
格式
输入格式
输入文件的第一行为两个整数n,Q分别表示一共有n块黄金,一共有Q次询问。
第二行有n个整数,第i个整数表示第i块黄金的价值大小。
第三行有n个整数,第i个整数表示第i块黄金的体积大小。
第四行开始到第n+3行,第i+3行有三个数,l,r,V,表示询问如果只允许取走编号从l到r的黄金,且你的背包大小为V,你最多能带走多少价值的黄金。
输出格式
输出文件仅包含一行,Q个实数表示Q次询问的答案,每个实数保留2位有效数字,相邻两个数之间用空格隔开,行末回车。
样例1
样例输入1
3 2
2 3 4
4 5 6
1 2 9
2 3 8
样例输出1
5.00 5.20
限制
2秒
提示
【样例解释】
第一次询问:取走编号1和编号2的两块黄金,总体积9,总价值5.00
第二次询问:取走编号3的黄金和编号为2的黄金的2/5,总体积8,总价值5.20
【提醒】
由于精度误差,0.00499999999999可能会四舍五入成0.00,而正确答案应该是0.01。
【约定】
对于30%的数据, n≤1000 Q≤1000
对于50%的数据, n≤50000 Q≤10000
对于100%的数据,n≤100000 Q≤100000
来源
原创题。