Problem Statement | |||||||||||||
There are several boards arranged side by side in a straight line. Boards go in order and you can't change the order of boards. The length of the i-th board in the line is boardLength[i] inches. There are also several painters. The i-th painter can paint a one inch length of board in 1/painterSpeed[i] seconds. You can assign jobs to some of painters (not necessarily to all of them). Each painter can be assigned at most a single block of one or more consecutive boards. All the painters start at the same time and work simultaneously. Return the minimal number of seconds needed to paint all the boards. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
- | Painters do not have to be assigned to boards in any particular order. For example, painter 2 can be assigned to boards 1 to 3, while painter 1 is assigned to boards 4 to 5, etc. | ||||||||||||
- | The returned value must be accurate to within a relative or absolute value of 1E-9. | ||||||||||||
Constraints | |||||||||||||
- | boardLength will contain between 1 and 50 elements, inclusive. | ||||||||||||
- | Each element of boardLength will be between 1 and 10000, inclusive. | ||||||||||||
- | painterSpeed will contain between 1 and 15 elements, inclusive. | ||||||||||||
- | Each element of painterSpeed will be between 1 and 10000, inclusive. | ||||||||||||
Examples | |||||||||||||
0) | |||||||||||||
| |||||||||||||
1) | |||||||||||||
| |||||||||||||
2) | |||||||||||||
| |||||||||||||
3) | |||||||||||||
|