Pro.ID22836 TitleCow Plumbing Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22836 AC0 Submit1 Ratio0.00% 时间&空间限制描述The cows want to move water from the pond to the barn, a distance of D (7 ≤ D ≤ 100,000). They have a set of P (1 ≤ P ≤ 350) pipes, each with positive integer length Li and positive integer capacity Ci (both numbers fit in 24 bits). The pipes can be connected in series into a run: the connected pipes have the capacity that is the least of all pipes' individual capacities. A run must reach precisely D units (i.e., the sum of the Li's for the pipes in a run must be D). Find the maximum amount of water that can be moved from the pond to the barn in one single run of pipe. 输入* Line 1: One line with two integers: D and P * Lines 2..N+1: Each line contains two integers describing a pipe: Li and Ci 输出Description The cows want to move water from the pond to the barn, a distance of D (7 ≤ D ≤ 100,000). They have a set of P (1 ≤ P ≤ 350) pipes, each with positive integer length Li and positive integer capacity Ci (both numbers fit in 24 bits). The pipes can be connected in series into a run: the connected pipes have the capacity that is the least of all pipes' individual capacities. A run must reach precisely D units (i.e., the sum of the Li's for the pipes in a run must be D). Find the maximum amount of water that can be moved from the pond to the barn in one single run of pipe. Input * Line 1: One line with two integers: D and P * Lines 2..N+1: Each line contains two integers describing a pipe: Li and Ci Output One line with a single integer that is the maximum possible legal flow. Sample Input 7 6 Sample Output 5 Source 样例输入7 6 样例输出5 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-6 00:49 , Processed in 0.043354 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
