[COCI 2023/2024 #3] Vrsar

Luogu

IDLGP10224

Time1000ms

Memory512MB

DifficultyP4

2023COCI（克罗地亚）

Vrsar 是一个由 $n$ 座小山丘组成的海滨小镇。惊人地，从海岸看去，$n$ 座山丘排成一列，第 $i$ 座山丘到海岸的距离为 $x_i$ 米。在每座山丘顶上各有一个溜冰场。所有溜冰场每天同时开放，但它们的关闭时间是不同的。第 $i$ 座溜冰场开放 $t_i$ 分钟。 Iva 和 Mia 已经来到了 Vrsar，他们将在这里停留 $m$ 天。Iva 和 Mia 热爱溜冰，他们希望在 Vrsar 停留的每一天都以溜冰度过。在第 $i$ 天的开始，他们距离海岸 $a_i$ 米。当滑雪场开放的同时，他们开始他们的溜冰之旅。他们需要走去滑雪场，走路的速度为每分钟 $1$ 米。他们的身体非常好，因此他们不需要额外时间来爬山。一旦他们到达山顶的滑雪场，他们可以滑任意长的时间，直到滑雪场关闭。然而，下山并不像上山一样容易，因为下雨，山路非常湿滑，他们需要消耗 $s_i$ 的时间走下第 $i$ 座山。从一座山上下来后，他们可以前往另一座山。 Iva 和 Mia 想知道每天他们最长可以滑多久的雪。每天他们可以访问任意多座滑雪场。因为他们想用尽可能多的时间滑雪，用尽可能少的时间计算，所以他们向你寻求帮助。帮助他们解决这个问题。请注意：如果 Iva 和 Mia 早晨出发的位置就有一座山，他们在山脚。 ## Input 第一行包含两个整数 $n,m$（$1 \le n,m \le 10^5$），表示山的数量和天数。接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,t_i,s_i$（$0 \le x_i,t_i,s_i \le 10^9$），分别表示第 $i$ 座山到海岸的距离、滑雪场的关闭时间和下山所需的时间。第三行包含 $m$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示 Iva 和 Mia 第 $i$ 天出发时到海岸的距离。 ## Output 输出一行 $m$ 个整数，第 $i$ 个整数表示第 $i$ 天 Iva 和 Mia 可以滑雪的最长时间。 [samples] ## Background **译自 [COCI 2023/2024 Contest #3](https://hsin.hr/coci/archive/2023_2024) T2「[Vrsar](https://hsin.hr/coci/archive/2023_2024/contest3_tasks.pdf)」** ## Note ### 样例解释 1 ![](https://cdn.luogu.com.cn/upload/image_hosting/swsv3bec.png) Iva 和 Mia 在位置 $1$ 出发，走 $2$ 分钟到位置 $3$ 的山，并滑雪 $5$ 分钟。接着花费 $0$ 分钟时间下山，继续走 $3$ 分钟时间到位置 $6$ 山上的滑雪场，滑雪 $1$ 分钟。他们一共滑雪 $6$ 分钟。 ### 子任务 | Subtask | Points | Constraints | | :--: | :--: | :--: | | 1 | 8 | $n,m \le 10$ | | 2 | 17 | $m=1,a_1=0$ | | 3 | 19 | $n,m \le 1000$ | | 4 | 26 | 无特殊限制。|

Samples

Input #1

Output #1

Input #2

Output #2

5 8

Input #3

1 3
3 3 3
0 1 2

Output #3

0 1 2

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2023/2024 #3] Vrsar",
    "description": {
      "content": "Vrsar 是一个由 $n$ 座小山丘组成的海滨小镇。惊人地，从海岸看去，$n$ 座山丘排成一列，第 $i$ 座山丘到海岸的距离为 $x_i$ 米。在每座山丘顶上各有一个溜冰场。所有溜冰场每天同时开放，但它们的关闭时间是不同的。第 $i$ 座溜冰场开放 $t_i$ 分钟。 Iva 和 Mia 已经来到了 Vrsar，他们将在这里停留 $m$ 天。Iva 和 Mia 热爱溜冰，他们希望在 Vrsa",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10224"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vrsar 是一个由 $n$ 座小山丘组成的海滨小镇。惊人地，从海岸看去，$n$ 座山丘排成一列，第 $i$ 座山丘到海岸的距离为 $x_i$ 米。在每座山丘顶上各有一个溜冰场。所有溜冰场每天同时开放，但它们的关闭时间是不同的。第 $i$ 座溜冰场开放 $t_i$ 分钟。\n\nIva 和 Mia 已经来到了 Vrsar，他们将在这里停留 $m$ 天。Iva 和 Mia 热爱溜冰，他们希望在 Vrsa...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments