#PU1093. USACO 2021 January Contest, Platinum — Problem 2. Minimum Cost Paths

    ID: 1483 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan21来源:usaco.orgscoring:equal_test_cases动态规划

USACO 2021 January Contest, Platinum — Problem 2. Minimum Cost Paths

USACO 2021 January Contest, Platinum — Problem 2. Minimum Cost Paths

题目描述

Farmer John's pasture can be regarded as an N×MN\times M (2≤N≤1092\le N\le 10^9, 2≤M≤2⋅1052\le M\le 2\cdot 10^5) 2D grid of square "cells" (picture a huge chessboard). The cell at the xx-th row from the top and yy-th column from the right is denoted by (x,y)(x,y) for each x∈[1,N],y∈[1,M]x\in [1,N], y\in [1,M]. Furthermore, for each y∈[1,M]y\in [1,M], the yy-th column is associated with the cost cyc_y (1≤cy≤1091\le c_y\le 10^9). Bessie starts at the cell (1,1)(1,1). If she is currently located at the cell (x,y)(x,y), then she may perform one of the following actions: If y<My<M, Bessie may move to the next column (increasing yy by one) for a cost of x2x^2. If x<Nx<N, Bessie may move to the next row (increasing xx by one) for a cost of cyc_y. Given QQ (1≤Q≤2⋅1051\le Q\le 2\cdot 10^5) independent queries each of the form (xi,yi)(x_i,y_i) (xi∈[1,N],yi∈[1,M]x_i\in [1,N], y_i\in [1,M]), compute the minimum possible total cost for Bessie to move from (1,1)(1,1) to (xi,yi)(x_i,y_i).

输入格式

The first line contains NN and MM. The second line contains MM space-separated integers c1,c2,…,cMc_1,c_2,\ldots,c_M. The third line contains QQ. The last QQ lines each contain two space-separated integers xix_i and yiy_i.

输出格式

QQ lines, containing the answers for each query.

数据范围

Test cases 1-3 satisfy N,M≤2000N,M\le 2000. Test cases 4-8 satisfy c2>c3>⋯>cMc_2>c_3>\cdots>c_M. Test cases 9-15 satisfy N≤2⋅105N\le 2\cdot 10^5. Test cases 16-20 satisfy no additional constraints. Problem credits: Benjamin Qi

样例

样例 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|
  *--*--*--*--*

提示

use of 64-bit integer data types (e.g., a "long long" in C/C++).