Average should be in double not int or long long.

Any length is ok as long as the average is maximum.

Try a test case that all number is 0.

It is a DAG so we can use top sort + DP to get shortest path.

Binary search for the average, minus average on every edge.

If the shortest path is <= 0, it means we can have an even lower average. If the shortest path is > 0, it means this average is too high. Note, we don't need to find a path that is exactly 0 cost. Binary search will help us narrow down.

1 might not be the only source, so we need to push all in degree 0 to queue first.

(a+b)/(c+d) > m => a+b > (c+d)*m => a-m*c + b-m*d > 0

Binary search for m.

Just follow what theory says

k should be 0 indexed for the theory, so [1, n^2] becomes [0, n^2-1]. Because cnt(x) could return 0, we need k to start from 0, otherwise 1 will be skipped.

There is a trick to get O(n) for cnt(x). Start from bottom left and count towards upper right, if mid > i*j, move j, otherwise move i.

k should be 0 indexed.

Sort both array and use two pointers method for cnt(x). Start from 0 of first array and start from n-1 of second array.