[CCC 2021 S3] Lunch Concert

Luogu
IDLGP9025
Time1000ms
Memory128MB
DifficultyP3
数学2021三分离散化CCC(加拿大)
有 $N$ 个人,第 $i$ 个人的速度为 $W_i$ **秒每米**,听力为 $D_i$,即能听见距离他不超过 $D_i$ 米处的音乐,初始在 $P_i$ 位置。 你要在 $c$ 位置处开音乐会,这个 $c$ 由你决定且为整数。这 $N$ 个人都会靠近你直到能听到你。你要最小化每个人移动的时间之和。 ## Input 第一行:$N$。 接下来的 $N$ 行,每行依次包含 $P_i,W_i,D_i$。 ## Output 一个整数:每个人移动的时间之和的最小值。(注意:答案可能超过 $2^{32}$) [samples] ## Note $$1\leq N\leq 200000,0\leq P_i\leq 10^9,1\leq W_i\leq 1000,0\leq D_i\leq 10^9$$ 译自 [CCC2021 S3](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/seniorEF.pdf)。 ###### 2023.8.10 新增一组 hack 数据。
Samples
Input #1
1
0 1000 0
Output #1
0
Input #2
2
10 4 3
20 4 2
Output #2
20
Input #3
3
6 8 3
1 4 1
14 5 2
Output #3
43
API Response (JSON)
{
  "problem": {
    "name": "[CCC 2021 S3] Lunch Concert",
    "description": {
      "content": "有 $N$ 个人,第 $i$ 个人的速度为 $W_i$ **秒每米**,听力为 $D_i$,即能听见距离他不超过 $D_i$ 米处的音乐,初始在 $P_i$ 位置。 你要在 $c$ 位置处开音乐会,这个 $c$ 由你决定且为整数。这 $N$ 个人都会靠近你直到能听到你。你要最小化每个人移动的时间之和。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9025"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $N$ 个人,第 $i$ 个人的速度为 $W_i$ **秒每米**,听力为 $D_i$,即能听见距离他不超过 $D_i$ 米处的音乐,初始在 $P_i$ 位置。\n\n你要在 $c$ 位置处开音乐会,这个 $c$ 由你决定且为整数。这 $N$ 个人都会靠近你直到能听到你。你要最小化每个人移动的时间之和。\n\n## Input\n\n第一行:$N$。\n\n接下来的 $N$ 行,每行依次包含 $P_i,W_i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments