[JOIST 2024] 滑雪 2 / Ski 2

Luogu

IDLGP10432

Time2000ms

Memory1024MB

DifficultyP6

2024JOISC/JOIST（日本）

JOI 先生管理着 IOI 高原上一家著名的滑雪度假村，他决定为滑雪度假村开业 15 周年庆祝活动而在相邻的 KOI 高原上建造一家新的滑雪度假村。 KOI 高原有 $N$ 个点，编号从 $1$ 到 $N$。目前，第 $i$ 个点（$1 \leq i \leq N$）的海拔高度为 $H_i$ 米，并且高原上的每个点都没有连接起来的滑道。此外，每个点都配备了一个未使用的连接设施。 JOI 先生的目标是在高原上的一个点上建造 KOI 酒店，然后建造一些滑道连接高原上的每个点，以便人们可以从任何一个点滑雪到酒店。具体来说，JOI 先生将按照以下步骤建造滑雪度假村： 1. 进行以下筑堤工作任意次数（可能为零）：选择一个点 $i$，将点 $i$ 的海拔高度增加 1 米。此工作的成本为每次操作 $K$。 2. 从 $N$ 个点中选择一个点，并在那里建造 KOI 酒店。 3. 进行以下扩展工作任意次数（可能为零）：选择一个点 $i$，在点 $i$ 建造一个连接设施。此工作的成本为每次操作 $C_i$。 4. 对于除了 KOI 酒店所在点之外的剩余 $N - 1$ 个点，执行以下构建：设 $i$ 为该点的编号。选择另一个海拔严格较低的点 $j$，并使用点 $j$ 的一个未使用的连接设施，从点 $i$ 向点 $j$ 构建单向滑道。注意，如果没有海拔严格较低且有未使用连接设施的点 $j$，则无法实现目标。滑雪度假村的建造成本是进行堤岸工作和扩展工作的成本之和。编写一个程序，给定 KOI 高原上每个点的信息和每次筑堤工作的成本 $K$，找到建造滑雪度假村的最小成本。 ## Input 从标准输入中读取以下数据： - $N$ $K$ - $H_1$ $C_1$ - $H_2$ $C_2$ - ... - $H_N$ $C_N$ ## Output 输出一行，构建滑雪度假村的最小成本。 [samples] ## Note #### 样例解释 1 例如，可以按以下方式建造滑雪度假村： 1. 在点 $1$ 进行两次筑堤工作，在点 $5$ 进行一次。这些筑堤工作的总成本为 $2 \times (2 + 1) = 6$。每个点的海拔高度变为 $2, 1, 0, 2, 2$ 米。 2. 在点 $3$ 建造 KOI 酒店。 3. 在点 $2$ 进行两次扩展工作。这些扩展工作的总成本为 $1 \times 2 = 2$。结果，从点 $1$ 开始，每个点的连接设施数量变为 $1, 3, 1, 1, 1$。 4. 构建 $4$ 条滑道：一条从点 $1$ 到点 $2$，一条从点 $2$ 到点 $3$，一条从点 $4$ 到点 $2$，一条从点 $5$ 到点 $2$。因此，构建滑雪度假村的成本为 $6 + 2 = 8$。由于无法以不超过 $7$ 的成本建造滑雪度假村，因此输出 $8$。此样例输入满足子任务 $3,4,5,6$ 的约束条件。 #### 样例解释 2 这个样例输入与示例输入 1 的唯一区别在于 $K$ 的值。这个样例输入满足子任务 $1, 3, 4, 5, 6$ 的约束条件。 #### 样例解释 3 此示例输入满足子任务 $2, 3, 4, 5, 6$ 的约束条件。 ### 约束条件 - $1 \leq N \leq 300$ - $1 \leq K \leq 10^9$ - $0 \leq H_i \leq 10^9$（$1 \leq i \leq N$） - $1 \leq C_i \leq 10^9$（$1 \leq i \leq N$） - 给定的值均为整数。 ### 子任务 - (5 分) $K \geq 100,000$，$H_i \leq 300$，$C_i \leq 100$（$1 \leq i \leq N$） - (12 分) $H_1 \leq H_i$，$C_1 \leq C_i$，$H_i \leq 300$（$1 \leq i \leq N$） - (9 分) $N \leq 10$，$H_i \leq 10$（$1 \leq i \leq N$） - (33 分) $N \leq 40$，$H_i \leq 40$（$1 \leq i \leq N$） - (27 分) $H_i \leq 300$（$1 \leq i \leq N$） - (14 分) 无额外约束。

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[JOIST 2024] 滑雪 2 / Ski 2",
    "description": {
      "content": "JOI 先生管理着 IOI 高原上一家著名的滑雪度假村，他决定为滑雪度假村开业 15 周年庆祝活动而在相邻的 KOI 高原上建造一家新的滑雪度假村。 KOI 高原有 $N$ 个点，编号从 $1$ 到 $N$。目前，第 $i$ 个点（$1 \\leq i \\leq N$）的海拔高度为 $H_i$ 米，并且高原上的每个点都没有连接起来的滑道。此外，每个点都配备了一个未使用的连接设施。 JOI 先生的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10432"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "JOI 先生管理着 IOI 高原上一家著名的滑雪度假村，他决定为滑雪度假村开业 15 周年庆祝活动而在相邻的 KOI 高原上建造一家新的滑雪度假村。\n\nKOI 高原有 $N$ 个点，编号从 $1$ 到 $N$。目前，第 $i$ 个点（$1 \\leq i \\leq N$）的海拔高度为 $H_i$ 米，并且高原上的每个点都没有连接起来的滑道。此外，每个点都配备了一个未使用的连接设施。\n\nJOI 先生的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments