{"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,D_i$。\n\n## Output\n\n一个整数：每个人移动的时间之和的最小值。（注意：答案可能超过 $2^{32}$）\n\n[samples]\n\n## Note\n\n$$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$$\n\n译自 [CCC2021 S3](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/seniorEF.pdf)。\n\n###### 2023.8.10 新增一组 hack 数据。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9025","tags":["数学","2021","三分","离散化","CCC（加拿大）"],"sample_group":[["1\n0 1000 0\n","0"],["2\n10 4 3\n20 4 2\n","20"],["3\n6 8 3\n1 4 1\n14 5 2\n","43"]],"created_at":"2026-03-03 11:09:25"}}