Minimum Cost Paths

题目描述

农夫约翰的牧场可以看作一个 $N\times M$（$2\le N\le 10^9$，$2\le M\le 2\cdot 10^5$）的二维方格网格（可以想象成一个巨大的棋盘）。从上往下数第 $x$ 行、从右往左数第 $y$ 列的格子记为 $(x,y)$，其中 $x\in [1,N], y\in [1,M]$。此外，对于每个 $y\in [1,M]$，第 $y$ 列对应一个代价 $c_y$（$1\le c_y\le 10^9$）。

贝茜从格子 $(1,1)$ 出发。若她当前位于格子 $(x,y)$，则可以执行以下操作之一： 如果 $y<M$，贝茜可以移动到下一列（$y$ 增加 1），代价为 $x^2$。 如果 $x<N$，贝茜可以移动到下一行（$x$ 增加 1），代价为 $c_y$。

给定 $Q$（$1\le Q\le 2\cdot 10^5$）个相互独立的询问，每个询问形如 $(x_i,y_i)$（$x_i\in [1,N], y_i\in [1,M]$），计算贝茜从 $(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

0
1
2
3
4
1
5
11
19
29
2
9
20
35
54
3
13
29
49
69

提示

以网格形式输出的结果： 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）： 测试点 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

标签: USACO|2021|Platinum

来源

USACO|2021|Platinum