Minimum Cost Paths
Farmer John's pasture can be regarded as an N×M (2≤N≤109, 2≤M≤2⋅105) 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∈[1,N],y∈[1,M]. Furthermore, for each y∈[1,M], the y-th column is associated with the cost cy (1≤cy≤109).
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<M, Bessie may move to the next column (increasing y by one) for a cost of x2.
- If x<N, Bessie may move to the next row (increasing x by one) for a cost of cy.
Given Q (1≤Q≤2⋅105) independent queries each of the form (xi,yi) (xi∈[1,N],yi∈[1,M]), compute the minimum possible total cost for Bessie to move from (1,1) to (xi,yi).
The output in grid format:
1 2 3 4 *--*--*--*--* 1 | 0| 1| 2| 3| *--*--*--*--* 2 | 1| 5| 9|13| *--*--*--*--* 3 | 2|11|20|29| *--*--*--*--* 4 | 3|19|35|49| *--*--*--*--* 5 | 4|29|54|69| *--*--*--*--*
SCORING:
- Test cases 1-3 satisfy N,M≤2000.
- Test cases 4-8 satisfy c2>c3>⋯>cM.
- Test cases 9-15 satisfy N≤2⋅105.
- Test cases 16-20 satisfy no additional constraints.
Problem credits: Benjamin Qi
Source: USA Computing Olympiad.
Input Format
The first line contains N and M.
The second line contains M space-separated integers c1,c2,…,cM.
The third line contains Q.
The last Q lines each contain two space-separated integers xi and yi.
Output Format
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++).