Farmer John's pasture can be regarded as an \(N\times M\) (\(2\le N\le 10^9\),
\(2\le M\le 2\cdot 10^5\)) 2D grid of square "cells" (picture a huge chessboard).
The cell at the \(x\)-th row from the top and \(y\)-th column from the right is
denoted by \((x,y)\) for each \(x\in [1,N], y\in [1,M]\). Furthermore, for each
\(y\in [1,M]\), the \(y\)-th column is associated with the cost \(c_y\)
(\(1\le c_y\le 10^9\)).

Bessie starts at the cell \((1,1)\). If she is currently located at the cell
\((x,y)\), then she may perform one of the following actions:

• If \(y, Bessie may move to the next column (increasing \(y\) by one) for a cost of \(x^2\).
• If \(x, Bessie may move to the next row (increasing \(x\) by one) for a cost of \(c_y\).

Given \(Q\) (\(1\le Q\le 2\cdot 10^5\)) independent queries each of the form
\((x_i,y_i)\) (\(x_i\in [1,N], y_i\in [1,M]\)), compute the minimum possible total
cost for Bessie to move from \((1,1)\) to \((x_i,y_i)\).

Problem credits: Benjamin Qi

SCORING

• Test cases 1-3 satisfy \(N,M\le 2000\).
• Test cases 4-8 satisfy \(c_2>c_3>\cdots>c_M\).
• Test cases 9-15 satisfy \(N\le 2\cdot 10^5\).
• Test cases 16-20 satisfy no additional constraints.

Problem credits: Benjamin Qi

The first line contains \(N\) and \(M\).

The second line contains \(M\) space-separated integers \(c_1,c_2,\ldots,c_M\).

The third line contains \(Q\).

The last \(Q\) lines each contain two space-separated integers \(x_i\) and \(y_i\).

\(Q\) lines, containing the answers for each query.

Note that the large size of integers involved in this problem may require the
use of 64-bit integer data types (e.g., a "long long" in C/C++).

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > January > Platinum