Throughput P87774
Elon Musk is optimizing an assembly line in one of his factories and he needs your help to find an assignment of humanoid robots to stations that maximizes throughput (number of work units processed per hour).
There are a total of r identical humanoid robots
to be distributed among n workstations (numbered 1 to n) of the assembly line.
At each station i, robots collect work units from the output storage of station i−1,
perform some station-specific operation (such as welding, painting...),
and then place the processed work units on the output storage of station i,
to be collected by robots from station i+1.
Each robot at station i can process pi work units per hour.
Assume that robots at station 1 collect work units from a warehouse with unlimited supply,
and that the output of station n can be consumed at an arbitrarily high rate.
Can you find the maximum throughput that can be achieved by distributing the r robots among the n stations optimally?
Input
Each case starts with r and n. Follow the n integers p1, …, pn, all between 1 and 109. You can assume 1 ≤ n ≤ 105 and n ≤ r ≤ 109.
Output
For every case, print the maximum possible throughput of the assembly line.
Public test cases
Input
4 2 10 10 3 3 4 1 12 17 2 42 69 1000000000 4 500000000 42 1000000000 23
Output
20 1 420 14861537791
Information
- Author
- Felix Miravé
- Language
- English
- Official solutions
- C++
- User solutions
- C++