페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5784

Minimum Cost Paths 1초 512MB

문제

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.

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


입력

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.


출력

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++).


예제1

입력
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
출력
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|
  *--*--*--*--*

출처

USACO 2021 January Platinum

역링크 공식 문제집만