8110: USACO 2021 January Contest, Platinum Problem 2. Minimum Cost Paths
[Creator : ]
Description
Farmer John's pasture can be regarded as an $N×M\ (2≤N≤10^9,\ 2≤M≤2⋅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∈[1,N],y∈[1,M]. Furthermore, for each y∈[1,M], the y-th column is associated with the cost $c_y\ (1≤c_y≤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<M, Bessie may move to the next column (increasing y by one) for a cost of $x^2$.
- If x<N, Bessie may move to the next row (increasing x by one) for a cost of $c_y$.
Input
The first line contains N and M.
The second line contains M space-separated integers $c_1,c_2,…,c_M$.
The third line contains Q.
The last Q lines each contain two space-separated integers $x_i$ and $y_i$.
The third line contains Q.
The last Q lines each contain two space-separated integers $x_i$ and $y_i$.
Output
Q lines, containing the answers for each query.
Sample 1 Input
5 4
1 100 100 20
20
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
3 4
4 4
5 4
Sample 1 Output
0
1
2
3
4
1
5
11
19
29
2
9
20
35
54
3
13
29
49
69
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|
*--*--*--*--*