[XJTUPC 2024] 勘探队

Luogu

IDLGP10529

Time1000ms

Memory256MB

DifficultyP6

2024Special JudgeO2优化高校校赛

一支勘探队从 $(0,0)$ 出发，终点是 $(0,y)$，携带着从 $1$ 号到 $n$ 号设备，每个设备的重量为 $m_i$，且必须安放在横坐标为 $x_i$ 的任意位置上（纵坐标可以是任意实数）。必须按照顺序安放所有设备，在较小编号的设备被全部放置之前，即使横坐标位置满足，也不能放置。当勘探队身上的设备总重量为 $m$ 时，其移动一单位长度的代价是 $m+M$。问勘探队完成所有设备安装并到达终点的最小代价。同一个坐标位置可以放置多台设备。 ## Input 输入第一行三个正整数 $n$ ($1\le n \le 1\times 10^4$)，$M$ ($0< M \le 30$) 和 $y$ ($0<y\le 2\times 10^5$)，代表设备个数、移动的基本代价和最终终点的纵坐标。第二行给出 $n$ 个非负整数 $m_i$ ($0< m_i\le 30$)，表示第 $i$ 台设备的重量。两两之间用空格隔开。第三行给出 $n$ 个整数 $x_i$ ($|x_i|\le 1\times 10^4$)，表示第 $i$ 台机器坐标的要求。 ## Output 输出一行一个正实数代表最终代价。如果你的答案是 $a$，我们给出的标准答案是 $b$，你的答案正确当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$。 [samples] ## Note 走直线走到 $(12,5)$，距离 $13$，然后走直线走到 $(0,14)$，距离 $15$，总代价 $13\times (25+14)+15\times 25=882$。不存在一个比这个更优的解。

Samples

Input #1

1 25 14
14
12

Output #1

882.000000

API Response (JSON)

{
  "problem": {
    "name": "[XJTUPC 2024] 勘探队",
    "description": {
      "content": "一支勘探队从 $(0,0)$ 出发，终点是 $(0,y)$，携带着从 $1$ 号到 $n$ 号设备，每个设备的重量为 $m_i$，且必须安放在横坐标为 $x_i$ 的任意位置上（纵坐标可以是任意实数）。必须按照顺序安放所有设备，在较小编号的设备被全部放置之前，即使横坐标位置满足，也不能放置。 当勘探队身上的设备总重量为 $m$ 时，其移动一单位长度的代价是 $m+M$。问勘探队完成所有设备安装并",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10529"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一支勘探队从 $(0,0)$ 出发，终点是 $(0,y)$，携带着从 $1$ 号到 $n$ 号设备，每个设备的重量为 $m_i$，且必须安放在横坐标为 $x_i$ 的任意位置上（纵坐标可以是任意实数）。必须按照顺序安放所有设备，在较小编号的设备被全部放置之前，即使横坐标位置满足，也不能放置。\n\n当勘探队身上的设备总重量为 $m$ 时，其移动一单位长度的代价是 $m+M$。问勘探队完成所有设备安装并...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments