[COCI 2023/2024 #5] Rolete

Luogu

IDLGP10260

Time2000ms

Memory512MB

DifficultyP5

二分2023三分COCI（克罗地亚）决策单调性

一个周六的下午，Luka 从午睡中醒来，想起今天有 COCI！在比赛前，他只需要做一件事情：拉起窗帘。卢卡的房间里有 $n$ 个窗帘，其中第 $i$ 个窗帘距离窗户顶部下降了 $a_i$ 厘米。他可以通过两种方式拉起窗帘： - 他可以手动开始拉起任意一个窗帘。使用这种方法，他每拉起 $1$ 厘米需要 $t$ 秒钟。 - 他可以按下一个按钮，同时以相同的速度将所有窗帘同步拉起。按下按钮时，窗帘的上升速度定义如下：如果所有窗帘都在上升，每个窗帘都会在 $s$ 秒内上升 $1$ 厘米。如果 $r$ 个窗帘已经完全升起，这会减慢系统的速度。那么剩余的窗帘每上升 $1$ 厘米需要 $s + k \cdot r$ 秒钟。 COCI 即将开始，Luka 希望尽快拉起他的窗帘。与此同时，他的兄弟 Marin 走进房间，问了他 $q$ 个问题：**为了使窗帘下降的最大高度不超过 $h$ 厘米，你需要的最短时间是多少**？Marin 对于每个问题都考虑窗帘的初始状态。他们意识到在 COCI 之前没有足够的时间来考虑这个问题。幸运的是，这个问题也出现在这里！帮助他们解决它！注意：Luka 总是将窗帘拉起一个整数值的厘米。 ## Input 第一行四个整数 $n,t,s,k\ (1\le n,t,s\le 10^5,0\le k\le 10^5)$，分别表示窗帘个数，手动拉窗帘所需的时间，按下按钮拉窗帘所需的时间和同步上升的减慢因子。第二行包含 $n$ 个整数 $a_i\ (0\le a_i\le 10^5)$，表示初始窗帘的状态。第三行包含一个整数 $q\ (1\le q\le 10^5)$，表示问题个数。第四行包含 $q$ 个整数 $h_i\ (0\le h_i\le 10^5)$，表示最大窗帘高度。 ## Output 输出一行 $q$ 个整数，第 $i$ 个表示使得窗帘下降的最大高度不超过 $h_i$ 厘米所需的最短用时。 [samples] ## Background **译自 [COCI 2023/2024 Contest #5](https://hsin.hr/coci/archive/2023_2024) T4「[Rolete](https://hsin.hr/coci/archive/2023_2024/contest5_tasks.pdf)」** ## Note ### 样例解释 1 为了使所有窗帘的下降高度最多为 $2$ 厘米，卢卡需要手动将第三个窗帘拉起 $2$ 厘米。最快的方法是手动拉起它，这将花费他 $4$ 秒钟。如果所有窗帘都需要完全拉起，卢卡可以先手动将第三个窗帘拉起 $2$ 厘米。然后，他可以按下按钮，让所有窗帘同时上升 $2$ 厘米。总共需要的时间为 $4 + 10 = 14$ 秒。类似地，如果窗帘的下降高度最多为 $1$ 厘米，卢卡会先手动将第三个窗帘拉起 $2$ 厘米，然后将所有窗帘一起上升 $1$ 厘米。拉起的总时间将为 $9$ 秒。 ### 子任务 | Subtask | Points | Constraints | | :--: | :--: | :--: | | 1 | 16 | $n,q,a_i,h_i\le 100$ | | 2 | 26 | $k=0$ | | 3 | 32 | $q=1$ | | 4 | 36 | 无额外限制 |

Samples

Input #1

Output #1

4 14 9

Input #2

Output #2

0 3 10

Input #3

Output #3

9 18 47

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2023/2024 #5] Rolete",
    "description": {
      "content": "一个周六的下午，Luka 从午睡中醒来，想起今天有 COCI！在比赛前，他只需要做一件事情：拉起窗帘。 卢卡的房间里有 $n$ 个窗帘，其中第 $i$ 个窗帘距离窗户顶部下降了 $a_i$ 厘米。他可以通过两种方式拉起窗帘： - 他可以手动开始拉起任意一个窗帘。使用这种方法，他每拉起 $1$ 厘米需要 $t$ 秒钟。 - 他可以按下一个按钮，同时以相同的速度将所有窗帘同步拉起。 按下按钮时，",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10260"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一个周六的下午，Luka 从午睡中醒来，想起今天有 COCI！在比赛前，他只需要做一件事情：拉起窗帘。\n\n卢卡的房间里有 $n$ 个窗帘，其中第 $i$ 个窗帘距离窗户顶部下降了 $a_i$ 厘米。他可以通过两种方式拉起窗帘：\n\n- 他可以手动开始拉起任意一个窗帘。使用这种方法，他每拉起 $1$ 厘米需要 $t$ 秒钟。\n- 他可以按下一个按钮，同时以相同的速度将所有窗帘同步拉起。\n\n按下按钮时，...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments