D. Winter Is Coming

Codeforces

IDCF747D

Time1000ms

Memory256MB

Difficulty—

dpgreedysortings

English · Original

Chinese · Translation

Formal · Original

The winter in Berland lasts _n_ days. For each day we know the forecast for the average air temperature that day. Vasya has a new set of winter tires which allows him to drive safely no more than _k_ days at any average air temperature. After _k_ days of using it (regardless of the temperature of these days) the set of winter tires wears down and cannot be used more. It is not necessary that these _k_ days form a continuous segment of days. Before the first winter day Vasya still uses **summer tires**. It is possible to drive safely on summer tires any number of days when the average air temperature is **non-negative**. It is impossible to drive on summer tires at days when the average air temperature is negative. Vasya can change summer tires to winter tires and vice versa at the beginning of any day. Find the minimum number of times Vasya needs to change summer tires to winter tires and vice versa to drive safely during the winter. At the end of the winter the car can be with any set of tires. ## Input The first line contains two positive integers _n_ and _k_ (1 ≤ _n_ ≤ 2·105, 0 ≤ _k_ ≤ _n_) — the number of winter days and the number of days winter tires can be used. It is allowed to drive on winter tires at any temperature, but no more than _k_ days in total. The second line contains a sequence of _n_ integers _t_1, _t_2, ..., _t__n_ ( - 20 ≤ _t__i_ ≤ 20) — the average air temperature in the _i_\-th winter day. ## Output Print the minimum number of times Vasya has to change summer tires to winter tires and vice versa to drive safely during all winter. If it is impossible, print _\-1_. [samples] ## Note In the first example before the first winter day Vasya should change summer tires to winter tires, use it for three days, and then change winter tires to summer tires because he can drive safely with the winter tires for just three days. Thus, the total number of tires' changes equals two. In the second example before the first winter day Vasya should change summer tires to winter tires, and then after the first winter day change winter tires to summer tires. After the second day it is necessary to change summer tires to winter tires again, and after the third day it is necessary to change winter tires to summer tires. Thus, the total number of tires' changes equals four.

Berland 的冬天持续 #cf_span[n] 天。对于每一天，我们知道当天的平均气温预报。 Vasya 有一套新的冬季轮胎，允许他在任意平均气温下安全驾驶，但总共最多只能使用 #cf_span[k] 天。使用满 #cf_span[k] 天后（无论这些天的气温如何），冬季轮胎就会磨损，不能再使用。这 #cf_span[k] 天不需要是连续的。在第一个冬天到来之前，Vasya 仍然使用 *夏季轮胎*。当平均气温为 *非负* 时，可以无限天数安全使用夏季轮胎；当平均气温为负时，无法使用夏季轮胎。 Vasya 可以在任意一天开始时更换夏季轮胎和冬季轮胎。求 Vasya 在整个冬天中为安全驾驶所需更换夏季轮胎与冬季轮胎的最少次数。冬天结束时，汽车可以使用任意一套轮胎。第一行包含两个正整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 2·105], #cf_span[0 ≤ k ≤ n]）——冬天的天数和冬季轮胎可使用的天数。允许在任意温度下使用冬季轮胎，但总使用天数不超过 #cf_span[k] 天。第二行包含一个长度为 #cf_span[n] 的整数序列 #cf_span[t1, t2, ..., tn]（#cf_span[ - 20 ≤ ti ≤ 20]）——第 #cf_span[i] 天的平均气温。请输出 Vasya 在整个冬天中为安全驾驶所需更换夏季轮胎与冬季轮胎的最少次数。如果不可能实现，请输出 _-1_。在第一个例子中，在第一个冬天到来之前，Vasya 应将夏季轮胎更换为冬季轮胎，使用三天，然后将冬季轮胎换回夏季轮胎，因为冬季轮胎最多只能使用三天。因此，轮胎更换总次数为两次。在第二个例子中，在第一个冬天到来之前，Vasya 应将夏季轮胎更换为冬季轮胎，然后在第一个冬天结束后将冬季轮胎换回夏季轮胎。在第二天结束后，必须再次将夏季轮胎更换为冬季轮胎，第三天结束后，必须将冬季轮胎换回夏季轮胎。因此，轮胎更换总次数为四次。 ## Input 第一行包含两个正整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 2·105], #cf_span[0 ≤ k ≤ n]）——冬天的天数和冬季轮胎可使用的天数。允许在任意温度下使用冬季轮胎，但总使用天数不超过 #cf_span[k] 天。第二行包含一个长度为 #cf_span[n] 的整数序列 #cf_span[t1, t2, ..., tn]（#cf_span[ - 20 ≤ ti ≤ 20]）——第 #cf_span[i] 天的平均气温。 ## Output 请输出 Vasya 在整个冬天中为安全驾驶所需更换夏季轮胎与冬季轮胎的最少次数。如果不可能实现，请输出 _-1_。 [samples] ## Note 在第一个例子中，在第一个冬天到来之前，Vasya 应将夏季轮胎更换为冬季轮胎，使用三天，然后将冬季轮胎换回夏季轮胎，因为冬季轮胎最多只能使用三天。因此，轮胎更换总次数为两次。在第二个例子中，在第一个冬天到来之前，Vasya 应将夏季轮胎更换为冬季轮胎，然后在第一个冬天结束后将冬季轮胎换回夏季轮胎。在第二天结束后，必须再次将夏季轮胎更换为冬季轮胎，第三天结束后，必须将冬季轮胎换回夏季轮胎。因此，轮胎更换总次数为四次。

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 1 \leq n \leq 2 \cdot 10^5 $, $ 0 \leq k \leq n $. Let $ T = (t_1, t_2, \dots, t_n) $ be a sequence of integers where $ -20 \leq t_i \leq 20 $, representing daily average temperatures. Let $ S $ denote summer tires, $ W $ denote winter tires. - Summer tires can be used only on days with $ t_i \geq 0 $. - Winter tires can be used on any day, but at most $ k $ days total. A *change* is a transition between $ S $ and $ W $ at the start of a day. Initial state: summer tires before day 1. **Constraints** 1. For each day $ i \in \{1, \dots, n\} $: - If $ t_i < 0 $, then winter tires **must** be used. - If $ t_i \geq 0 $, either tire type may be used. 2. Total number of days winter tires are used $ \leq k $. 3. If $ k < \#\{i \mid t_i < 0\} $, then it is impossible. **Objective** Minimize the number of tire changes (transitions between $ S $ and $ W $) over the $ n $ days, such that all days are safely driven and the winter tire usage constraint is satisfied. If impossible, output $ -1 $.

Samples

Input #1

4 3
-5 20 -3 0

Output #1

Input #2

4 2
-5 20 -3 0

Output #2

Input #3

10 6
2 -5 1 3 0 0 -4 -3 1 0

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Winter Is Coming",
    "description": {
      "content": "The winter in Berland lasts _n_ days. For each day we know the forecast for the average air temperature that day. Vasya has a new set of winter tires which allows him to drive safely no more than _k_",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF747D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The winter in Berland lasts _n_ days. For each day we know the forecast for the average air temperature that day.\n\nVasya has a new set of winter tires which allows him to drive safely no more than _k_...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Berland 的冬天持续 #cf_span[n] 天。对于每一天，我们知道当天的平均气温预报。\n\nVasya 有一套新的冬季轮胎，允许他在任意平均气温下安全驾驶，但总共最多只能使用 #cf_span[k] 天。使用满 #cf_span[k] 天后（无论这些天的气温如何），冬季轮胎就会磨损，不能再使用。这 #cf_span[k] 天不需要是连续的。\n\n在第一个冬天到来之前，Vasya 仍然使用 *...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 2 \\cdot 10^5 $, $ 0 \\leq k \\leq n $.  \nLet $ T = (t_1, t_2, \\dots, t_n) $ be a sequence of integers where $ -20 \\leq t_i \\leq 20 $, r...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments