Farmer John is distributing haybales across the farm!

Farmer John's farm has \(N\) \((1\le N\le 2\cdot 10^5)\) barns, located at integer
points \(x_1,\dots, x_N\) \((0 \le x_i \le 10^6)\) on the number line. Farmer John's
plan is to first have \(N\) shipments of haybales delivered to some integer point
\(y\) \((0 \le y \le 10^6)\) and then distribute one shipment to each barn.

Unfortunately, Farmer John's distribution service is very wasteful. In
particular, for some \(a_i\) and \(b_i\) \((1\le a_i, b_i\le 10^6)\), \(a_i\) haybales
are wasted per unit of distance left each shipment is transported, and \(b_i\)
haybales are wasted per unit of distance right each shipment is transported.
Formally, for a shipment being transported from point \(y\) to a barn at point
\(x\), the number of haybales wasted is given by

$$ \begin{cases} a_i\cdot (y-x) & \text{if } y \ge x \\ b_i\cdot (x-y) & \text{if } x > y \end{cases}. $$

Given \(Q\) \((1\le Q\le 2\cdot 10^5)\) independent queries each consisting of
possible values of \((a_i,b_i)\), please help Farmer John determine the fewest
amount of haybales that will be wasted if he chooses \(y\) optimally.

Problem credits: Benjamin Qi

SCORING

• Input 2: \(N,Q\le 10\)
• Input 3: \(N,Q\le 500\)
• Inputs 4-6: \(N,Q\le 5000\)
• Inputs 7-16: No additional constraints.

Problem credits: Benjamin Qi

The first line contains \(N\).

The next line contains \(x_1\dots x_N\).

The next line contains \(Q\).

The next \(Q\) lines each contain two integers \(a_i\) and \(b_i\).

Output \(Q\) lines, the \(i\)th line containing the answer for the \(i\)th query.

riseoj 작성

출처 올림피아드 > USACO > 2023-2024 > December > Gold