QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
[0]

# 2029. Minimum Cost Paths

Statistics

Farmer John's pasture can be regarded as an N×M (2N109, 2M2105) 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 (1cy109).

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 (1Q2105) 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).

INPUT FORMAT (input arrives from the terminal / stdin):

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 (print output to the terminal / stdout):

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

SAMPLE 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 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|
  *--*--*--*--*

SCORING:

  • Test cases 1-3 satisfy N,M2000.
  • Test cases 4-8 satisfy c2>c3>>cM.
  • Test cases 9-15 satisfy N2105.
  • Test cases 16-20 satisfy no additional constraints.

Problem credits: Benjamin Qi