USACO

USACO 2021 January Contest, Platinum

Problem 2. Minimum Cost Paths

Contest has ended.

Log in to allow submissions in analysis mode

Farmer John 的牧草地可以看作是一个

$N\times M$ （

$2\le N\le 10^9$ ,

$2\le M\le 2\cdot 10^5$ ）的正方形方格组成的二维方阵（想象一个巨大的棋盘）。对于

$x\in [1,N], y\in [1,M]$ ，从上往下第

$x$ 行、从左往右第

$y$ 列的方格记为

$(x,y)$ 。此外，对于每一个

$y\in [1,M]$ ，第

$y$ 列拥有一个代价

$c_y$ （

$1\le c_y\le 10^9$ ）。

Bessie 从方格 $(1,1)$ 出发。如果她现在位于方格 $(x,y)$ ，则她可以执行以下操作之一：

如果 $y<M$ ，Bessie 可以以 $x^2$ 的代价移动到下一列（ $y$ 增加一）。
如果 $x<N$ ，Bessie 可以以 $c_y$ 的代价移动到下一行（ $x$ 增加一）。

给定 $Q$ （ $1\le Q\le 2\cdot 10^5$ ）个独立的询问，每个询问给定 $(x_i,y_i)$ （ $x_i\in [1,N], y_i\in [1,M]$ ），计算 Bessie 从 $(1,1)$ 移动到 $(x_i,y_i)$ 的最小总代价。

输入格式（从终端/标准输入读入）：

输入的第一行包含

$N$ 和

$M$ 。

第二行包含 $M$ 个空格分隔的整数 $c_1,c_2,\ldots,c_M$ 。

第三行包含 $Q$ 。

最后 $Q$ 行每行包含两个空格分隔的整数 $x_i$ 和 $y_i$ 。

输出格式（输出至终端/标准输出）：

输出

$Q$ 行，为每个询问的答案。

注意本题计算中所使用的整数大小可能需要使用 64 位整数型（例如，C/C++ 中的 long long）。

输入样例：

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

输出样例：

输出以方阵形式表示如下：

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

测试点性质：

测试点 1-3 满足 $N,M\le 2000$ 。
测试点 4-8 满足 $c_2>c_3>\cdots>c_M$ 。
测试点 9-15 满足 $N\le 2\cdot 10^5$ 。
测试点 16-20 没有额外限制。

供题：Benjamin Qi

Contest has ended. No further submissions allowed.