F. Ordering T-Shirts

Codeforces

IDCF859F

Time2000ms

Memory256MB

Difficulty—

greedy

English · Original

Chinese · Translation

Formal · Original

It's another Start\[c\]up, and that means there are T-shirts to order. In order to make sure T-shirts are shipped as soon as possible, we've decided that this year we're going to order all of the necessary T-shirts before the actual competition. The top _C_ contestants are going to be awarded T-shirts, but we obviously don't know which contestants that will be. The plan is to get the T-Shirt sizes of all contestants before the actual competition, and then order enough T-shirts so that no matter who is in the top _C_ we'll have T-shirts available in order to award them. In order to get the T-shirt sizes of the contestants, we will send out a survey. The survey will allow contestants to either specify a single desired T-shirt size, or two adjacent T-shirt sizes. If a contestant specifies two sizes, it means that they can be awarded either size. As you can probably tell, this plan could require ordering a lot of unnecessary T-shirts. We'd like your help to determine the minimum number of T-shirts we'll need to order to ensure that we'll be able to award T-shirts no matter the outcome of the competition. ## Input Input will begin with two integers _N_ and _C_ (1 ≤ _N_ ≤ 2·105, 1 ≤ _C_), the number of T-shirt sizes and number of T-shirts to be awarded, respectively. Following this is a line with 2·_N_ - 1 integers, _s_1 through _s_2·_N_ - 1 (0 ≤ _s__i_ ≤ 108). For odd _i_, _s__i_ indicates the number of contestants desiring T-shirt size ((_i_ + 1) / 2). For even _i_, _s__i_ indicates the number of contestants okay receiving either of T-shirt sizes (_i_ / 2) and (_i_ / 2 + 1). _C_ will not exceed the total number of contestants. ## Output Print the minimum number of T-shirts we need to buy. [samples] ## Note In the first example, we can buy 100 of each size.

这是另一次 Start[c]up，意味着我们需要订购 T 恤。为了确保 T 恤能尽快发货，我们决定今年在比赛实际开始前就订购所有必需的 T 恤。前 #cf_span[C] 名参赛者将获得 T 恤，但我们显然不知道最终哪些参赛者会进入前 #cf_span[C]。我们的计划是在比赛前收集所有参赛者的 T 恤尺码，然后订购足够数量的 T 恤，以便无论谁进入前 #cf_span[C]，我们都能提供合适的 T 恤。为了获取参赛者的 T 恤尺码，我们将发放一份调查问卷。问卷允许参赛者指定一个期望的 T 恤尺码，或两个相邻的 T 恤尺码。如果参赛者指定了两个尺码，则意味着他们可以接受其中任意一个。正如你可能猜到的，这个计划可能会导致订购大量不必要的 T 恤。我们希望你能帮助我们确定，为确保无论比赛结果如何都能发放 T 恤，最少需要订购多少件 T 恤。输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[C]（#cf_span[1 ≤ N ≤ 2·105]，#cf_span[1 ≤ C]），分别表示 T 恤尺码的种类数和需要颁发的 T 恤数量。接下来一行包含 #cf_span[2·N - 1] 个整数 #cf_span[s1] 到 #cf_span[s2·N - 1]（#cf_span[0 ≤ si ≤ 108]）。对于奇数 #cf_span[i]，#cf_span[si] 表示希望获得 T 恤尺码 #cf_span[((i + 1) / 2)] 的参赛者人数；对于偶数 #cf_span[i]，#cf_span[si] 表示愿意接受 T 恤尺码 #cf_span[(i / 2)] 和 #cf_span[(i / 2 + 1)] 中任意一个的参赛者人数。#cf_span[C] 不会超过参赛者总人数。请输出我们需要购买的最少 T 恤数量。在第一个示例中，我们可以每种尺码各购买 #cf_span[100] 件。 ## Input 输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[C]（#cf_span[1 ≤ N ≤ 2·105]，#cf_span[1 ≤ C]），分别表示 T 恤尺码的种类数和需要颁发的 T 恤数量。接下来一行包含 #cf_span[2·N - 1] 个整数 #cf_span[s1] 到 #cf_span[s2·N - 1]（#cf_span[0 ≤ si ≤ 108]）。对于奇数 #cf_span[i]，#cf_span[si] 表示希望获得 T 恤尺码 #cf_span[((i + 1) / 2)] 的参赛者人数；对于偶数 #cf_span[i]，#cf_span[si] 表示愿意接受 T 恤尺码 #cf_span[(i / 2)] 和 #cf_span[(i / 2 + 1)] 中任意一个的参赛者人数。#cf_span[C] 不会超过参赛者总人数。 ## Output 请输出我们需要购买的最少 T 恤数量。 [samples] ## Note 在第一个示例中，我们可以每种尺码各购买 #cf_span[100] 件。

**Definitions** Let $ N, C \in \mathbb{Z}^+ $: number of T-shirt sizes and number of T-shirts to award. Let $ s_1, s_2, \dots, s_{2N-1} \in \mathbb{Z}_{\geq 0} $: survey responses, where: - For odd $ i $, $ s_i $ is the number of contestants requesting size $ \frac{i+1}{2} $ (exact size). - For even $ i $, $ s_i $ is the number of contestants accepting sizes $ \frac{i}{2} $ and $ \frac{i}{2} + 1 $ (adjacent pair). Let $ A = \{a_1, a_2, \dots, a_N\} $ be the number of T-shirts ordered for each size $ 1 $ to $ N $. **Constraints** 1. $ 1 \leq N \leq 2 \cdot 10^5 $, $ 1 \leq C \leq \sum_{i=1}^{2N-1} s_i $ 2. For each odd $ i = 2k-1 $, $ a_k \geq s_i $ must be satisfied in some feasible assignment. 3. For each even $ i = 2k $, the $ s_i $ contestants must be assignable to sizes $ k $ or $ k+1 $, i.e., the total capacity for sizes $ k $ and $ k+1 $ must cover these demands along with exact requests. 4. $ \sum_{j=1}^N a_j \geq C $, and we must be able to assign exactly $ C $ T-shirts to $ C $ contestants respecting their constraints. **Objective** Minimize $ \sum_{j=1}^N a_j $, subject to the constraint that for **any** subset of $ C $ contestants (chosen from all respondents), there exists a valid assignment of T-shirts such that each selected contestant receives a size they accept.

Samples

Input #1

2 200
100 250 100

Output #1

Input #2

4 160
88 69 62 29 58 52 44

Output #2

API Response (JSON)

{
  "problem": {
    "name": "F. Ordering T-Shirts",
    "description": {
      "content": "It's another Start\\[c\\]up, and that means there are T-shirts to order. In order to make sure T-shirts are shipped as soon as possible, we've decided that this year we're going to order all of the nece",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF859F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "It's another Start\\[c\\]up, and that means there are T-shirts to order. In order to make sure T-shirts are shipped as soon as possible, we've decided that this year we're going to order all of the nece...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "这是另一次 Start[c]up，意味着我们需要订购 T 恤。为了确保 T 恤能尽快发货，我们决定今年在比赛实际开始前就订购所有必需的 T 恤。前 #cf_span[C] 名参赛者将获得 T 恤，但我们显然不知道最终哪些参赛者会进入前 #cf_span[C]。我们的计划是在比赛前收集所有参赛者的 T 恤尺码，然后订购足够数量的 T 恤，以便无论谁进入前 #cf_span[C]，我们都能提供合适的 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, C \\in \\mathbb{Z}^+ $: number of T-shirt sizes and number of T-shirts to award.  \nLet $ s_1, s_2, \\dots, s_{2N-1} \\in \\mathbb{Z}_{\\geq 0} $: survey responses, where:  \n- For ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments