You are given an empty water tank with a capacity of \(C\) liters.

Into this tank, the water flows \(x[i]\) liters for \(t[i]\) seconds. (\(i = 0\) to \(n - 1\))

You can set the value of output pipe to any maximum output rate \(R\) (not negative value, but do not have to be an integer) in liters per second.

Determine the most little output rate limit \(R\) such that the amount of water in the tank will never exceed \(C\) liters.

Explanation

When it comes to "Find the maximum of the minimum," we can use Binary Search.

The returning value can be double, so we apply binary search until the difference between the left and the right value becomes less than the acceptable error.

Code

constdouble EPS =1e-9;const Inf =1e9;doubleminOutputRate(vector<int> t, vector<int> x,int C){int n =(int)t.size();double left =-EPS, right = Inf, mid;while(right - left > EPS){
mid =(right + left)/2;double rem =0.0;bool ok =true;for(int i =0; i < n; i++){
rem +=(x[i]- mid)* t[i];
rem =max(rem,(double)0);if(rem > C){
ok =false;break;}}if(ok)
right = mid;else
left = mid;}return right;}