E. Bonuses and Teleports

Codeforces

IDCF10134E

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

On a number axis n teleports are located in the points ti and m bonuses are located in the points bj. Being in the same point with a teleport, one can instantly relocate to another point with the teleport. Being in the same point with a bonus, one can instantly get this bonus. You are in the point t1 and must collect all the bonuses, and then return back to the point t1. You can move along the number axis in any direction at the speed 1. How much time will it take to collect all the bonuses? The first line contans two integers n and m separated by a space (1 ≤ n, m ≤ 200000) — the number of teleports and the number of bonuses, correspondingly. The second line contains n integers ti separated by a space ( - 109 ≤ ti ≤ 109, ti ≤ ti + 1) — coordinates of the teleports in non-decreasing order. The third line contains m integers bj separated by a space ( - 109 ≤ bj ≤ 109, bj ≤ bj + 1) — coordinates of the bonuses in non-decreasing order. Output a single integer — the minimal time required to collect all the bonuses. ## Input The first line contans two integers n and m separated by a space (1 ≤ n, m ≤ 200000) — the number of teleports and the number of bonuses, correspondingly.The second line contains n integers ti separated by a space ( - 109 ≤ ti ≤ 109, ti ≤ ti + 1) — coordinates of the teleports in non-decreasing order.The third line contains m integers bj separated by a space ( - 109 ≤ bj ≤ 109, bj ≤ bj + 1) — coordinates of the bonuses in non-decreasing order. ## Output Output a single integer — the minimal time required to collect all the bonuses. [samples]

**Definitions** Let $ S $ be a string of length $ n $, where $ 1 \leq n \leq 10^5 $, consisting of lowercase English letters. Let $ X $ be a string of the same length as $ S $, also consisting of lowercase English letters. **Cost Function** The cost of $ S $ with respect to $ X $ is defined as: $$ \text{cost}(S, X) = \sum_{i=1}^{n} | \text{ord}(S_i) - \text{ord}(X_i) | $$ where $ \text{ord}(c) $ denotes the ASCII value of character $ c $. **Objective** Find the string $ X $ that minimizes $ \text{cost}(S, X) $. If multiple such $ X $ exist, choose the lexicographically smallest one.

API Response (JSON)

{
  "problem": {
    "name": "E. Bonuses and Teleports",
    "description": {
      "content": "On a number axis n teleports are located in the points ti and m bonuses are located in the points bj. Being in the same point with a teleport, one can instantly relocate to another point with the tele",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10134E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "On a number axis n teleports are located in the points ti and m bonuses are located in the points bj. Being in the same point with a teleport, one can instantly relocate to another point with the tele...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S $ be a string of length $ n $, where $ 1 \\leq n \\leq 10^5 $, consisting of lowercase English letters.  \nLet $ X $ be a string of the same length as $ S $, also consisting of ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments