/ Vijos / 题库 /

陶陶的背包

陶陶的背包

背景

陶陶很喜欢做白日梦。

描述

有一天,陶陶梦见他来到了一个遍地黄金的地方。不过奇怪的是这些黄金都排成了一条直线。

正当陶陶欢喜且纳闷的时候,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

来源

原创题。

信息

ID
1678
难度
9
分类
数据结构 | 线段树 点击显示
标签
递交数
1567
已通过
14
通过率
1%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

第一届Curimit模拟赛