F. Doomsday

Codeforces

IDCF10018F

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Doomsday comes in t units of time. In anticipation of such a significant event n people prepared m vaults in which, as they think, it will be possible to survive. But each vault can accommodate only k people and each person can pass only one unit of distance per one unit of time. Fortunately, all people and vaults are now on the straight line, so there is no confusion and calculations should be simple. You are given the positions of the people and the vaults on the line. You are to find the maximal number of people who can hide in vaults and think they will survive. The first line contains four integers n, m, k and t (1 ≤ n, m, k ≤ 200000, 1 ≤ t ≤ 109) separated by spaces — the number of people, the number of vaults, the capacity of one vault and the time left to the Doomsday. The second line contains n integers separated by spaces — the coordinates of the people on the line. The third line contains m integers separated by spaces — the coordinates of the vaults on the line. All the coordinates are between - 109 and 109, inclusively. Output one integer — the maximal number of people who can hide in vaults and think they will survive. ## Input The first line contains four integers n, m, k and t (1 ≤ n, m, k ≤ 200000, 1 ≤ t ≤ 109) separated by spaces — the number of people, the number of vaults, the capacity of one vault and the time left to the Doomsday.The second line contains n integers separated by spaces — the coordinates of the people on the line.The third line contains m integers separated by spaces — the coordinates of the vaults on the line.All the coordinates are between - 109 and 109, inclusively. ## Output Output one integer — the maximal number of people who can hide in vaults and think they will survive. [samples]

**Definitions** Let $ n, m, k, t \in \mathbb{Z}^+ $ denote the number of people, number of vaults, capacity per vault, and time until Doomsday, respectively. Let $ P = \{p_1, p_2, \dots, p_n\} \subseteq \mathbb{Z} $ be the set of positions of people. Let $ V = \{v_1, v_2, \dots, v_m\} \subseteq \mathbb{Z} $ be the set of positions of vaults. **Constraints** 1. $ 1 \leq n, m, k \leq 200000 $ 2. $ 1 \leq t \leq 10^9 $ 3. $ |p_i|, |v_j| \leq 10^9 $ for all $ i \in \{1,\dots,n\}, j \in \{1,\dots,m\} $ **Objective** Find the maximum number of people that can reach a vault within time $ t $, such that no vault exceeds capacity $ k $. A person at position $ p_i $ can reach a vault at position $ v_j $ if and only if $ |p_i - v_j| \leq t $. Each vault $ v_j $ can accommodate at most $ k $ people. Maximize the total number of assigned people under these constraints.

API Response (JSON)

{
  "problem": {
    "name": "F. Doomsday",
    "description": {
      "content": "Doomsday comes in t units of time. In anticipation of such a significant event n people prepared m vaults in which, as they think, it will be possible to survive. But each vault can accommodate only k",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10018F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Doomsday comes in t units of time. In anticipation of such a significant event n people prepared m vaults in which, as they think, it will be possible to survive. But each vault can accommodate only k...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m, k, t \\in \\mathbb{Z}^+ $ denote the number of people, number of vaults, capacity per vault, and time until Doomsday, respectively.  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} \\su...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments