If one can determine for a real value \(X\) whether

is the answer to this problem \(X\) or greater?

Then the answer to this problem is the minimum real number for which the answer to the decision problem is “true”, which can be found fast enough (as precisely as the solution is accepted) with a binary search. Therefore, let us fix the real value \(X\) and how to solve the decision problem.

The answer to the original problem is \(X\) or greater if and only if there exists a path from vertex \(1\) to vertex \(N\) such that the sum of beauty divided by sum of cost is \(X\) or greater; in other words, there exists a path (sequence of indices of edges) \((i_1, i_2, \ldots, i_l)\) from vertex \(1\) to vertex \(N\) such that

\[ \frac{\sum_{k = 1}^l b_{i_k}} {\sum_{k = 1}^l c_{i_k}} \geq X. \]

This inequality is equivalent to

\[ \sum_{k = 1}^l (b_{i_k} - c_{i_k}X) \geq 0. \]

By defining the weight of each edge as \(w_i \coloneqq b_i - c_iX\), one can see that the answer to the original problem is \(X\) or greater if and only if there exists a path from vertex \(1\) to vertex \(N\) such that the weight of the path (the sum of the weights of the edges on the path),

\[ \sum_{k=1}^l w_{i_k} = \sum_{k = 1}^l (b_{i_k} - c_{i_k}X), \]

is \(0\) or greater. Therefore, one can solve the decision problem by finding the maximum weight of a path from vertex \(1\) to vertex \(N\) and determine if the value is \(0\) or greater.

One can find the maximum possible weight of a path from vertex \(1\) to vertex \(N\) in the same manner as the shortest path problem. Especially, the graph given in this problem is a DAG (Directed Acyclic Graph) in which an edge always goes from a vertex with a smaller index to one with larger, so the sought value can be found with a Dynamic Programming (DP) where the DP table defined as

\(\mathrm{dp}[i] := \) (maximum possible weight of a path from vertex \(1\) to vertex \(i\))

is filled in ascending order of the vertex index \(i\), which can be completed in a total of \(O(N)\) time.