C. Ordering Pizza

Codeforces

IDCF867C

Time2000ms

Memory256MB

Difficulty—

greedyimplementationsortingsternary search

English · Original

Chinese · Translation

Formal · Original

It's another Start\[c\]up finals, and that means there is pizza to order for the onsite contestants. There are only 2 types of pizza (obviously not, but let's just pretend for the sake of the problem), and all pizzas contain exactly _S_ slices. It is known that the _i_\-th contestant will eat _s__i_ slices of pizza, and gain _a__i_ happiness for each slice of type 1 pizza they eat, and _b__i_ happiness for each slice of type 2 pizza they eat. We can order any number of type 1 and type 2 pizzas, but we want to buy the minimum possible number of pizzas for all of the contestants to be able to eat their required number of slices. Given that restriction, what is the maximum possible total happiness that can be achieved? ## Input The first line of input will contain integers _N_ and _S_ (1 ≤ _N_ ≤ 105, 1 ≤ _S_ ≤ 105), the number of contestants and the number of slices per pizza, respectively. _N_ lines follow. The _i_\-th such line contains integers _s__i_, _a__i_, and _b__i_ (1 ≤ _s__i_ ≤ 105, 1 ≤ _a__i_ ≤ 105, 1 ≤ _b__i_ ≤ 105), the number of slices the _i_\-th contestant will eat, the happiness they will gain from each type 1 slice they eat, and the happiness they will gain from each type 2 slice they eat, respectively. ## Output Print the maximum total happiness that can be achieved. [samples] ## Note In the first example, you only need to buy one pizza. If you buy a type 1 pizza, the total happiness will be 3·5 + 4·6 + 5·9 = 84, and if you buy a type 2 pizza, the total happiness will be 3·7 + 4·7 + 5·5 = 74.

这是另一次 Start[c]up 决赛，意味着需要为现场参赛者订购披萨。只有两种类型的披萨（显然不是，但为了问题 sake，我们就这样假设），且所有披萨都恰好包含 #cf_span[S] 片。已知第 #cf_span[i] 位参赛者将吃掉 #cf_span[si] 片披萨，每吃一片第一类披萨可获得 #cf_span[ai] 点快乐值，每吃一片第二类披萨可获得 #cf_span[bi] 点快乐值。我们可以订购任意数量的第一类和第二类披萨，但要求购买的披萨总数尽可能少，以确保所有参赛者都能吃到他们所需的片数。在这一限制下，能实现的最大总快乐值是多少？输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[S] #cf_span[(1 ≤ N ≤ 10^5, 1 ≤ S ≤ 10^5)]，分别表示参赛者人数和每张披萨的片数。接下来有 #cf_span[N] 行。第 #cf_span[i] 行包含三个整数 #cf_span[si], #cf_span[ai], 和 #cf_span[bi] #cf_span[(1 ≤ si ≤ 10^5, 1 ≤ ai ≤ 10^5, 1 ≤ bi ≤ 10^5)]，分别表示第 #cf_span[i] 位参赛者将吃的片数、每片第一类披萨带来的快乐值、每片第二类披萨带来的快乐值。请输出能实现的最大总快乐值。在第一个例子中，你只需要买一张披萨。如果买一张第一类披萨，总快乐值为 #cf_span[3·5 + 4·6 + 5·9 = 84]；如果买一张第二类披萨，总快乐值为 #cf_span[3·7 + 4·7 + 5·5 = 74]。 ## Input 输入的第一行包含两个整数 #cf_span[N] 和 #cf_span[S] #cf_span[(1 ≤ N ≤ 10^5, 1 ≤ S ≤ 10^5)]，分别表示参赛者人数和每张披萨的片数。接下来有 #cf_span[N] 行。第 #cf_span[i] 行包含三个整数 #cf_span[si], #cf_span[ai], 和 #cf_span[bi] #cf_span[(1 ≤ si ≤ 10^5, 1 ≤ ai ≤ 10^5, 1 ≤ bi ≤ 10^5)]，分别表示第 #cf_span[i] 位参赛者将吃的片数、每片第一类披萨带来的快乐值、每片第二类披萨带来的快乐值。 ## Output 请输出能实现的最大总快乐值。 [samples] ## Note 在第一个例子中，你只需要买一张披萨。如果买一张第一类披萨，总快乐值为 #cf_span[3·5 + 4·6 + 5·9 = 84]；如果买一张第二类披萨，总快乐值为 #cf_span[3·7 + 4·7 + 5·5 = 74]。

**Definitions** Let $ N, S \in \mathbb{Z}^+ $: number of contestants, slices per pizza. For each contestant $ i \in \{1, \dots, N\} $: - $ s_i \in \mathbb{Z}^+ $: slices consumed, - $ a_i \in \mathbb{Z}^+ $: happiness per slice of type 1 pizza, - $ b_i \in \mathbb{Z}^+ $: happiness per slice of type 2 pizza. Let $ T = \sum_{i=1}^N s_i $: total slices required. Let $ p_1, p_2 \in \mathbb{Z}_{\geq 0} $: number of type 1 and type 2 pizzas ordered, respectively. Constraint: $ p_1 \cdot S + p_2 \cdot S = T \Rightarrow p_1 + p_2 = \lceil T / S \rceil $. Let $ x_i \in [0, s_i] \cap \mathbb{Z} $: number of slices of type 1 pizza consumed by contestant $ i $, then $ s_i - x_i $: slices of type 2 pizza consumed by contestant $ i $. **Constraints** 1. $ \sum_{i=1}^N x_i = p_1 \cdot S $ 2. $ \sum_{i=1}^N (s_i - x_i) = p_2 \cdot S $ 3. $ p_1 + p_2 = \lceil T / S \rceil $ 4. $ 0 \leq x_i \leq s_i $ for all $ i $ **Objective** Maximize total happiness: $$ \max \sum_{i=1}^N \left( x_i a_i + (s_i - x_i) b_i \right) = \sum_{i=1}^N s_i b_i + \sum_{i=1}^N x_i (a_i - b_i) $$

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Ordering Pizza",
    "description": {
      "content": "It's another Start\\[c\\]up finals, and that means there is pizza to order for the onsite contestants. There are only 2 types of pizza (obviously not, but let's just pretend for the sake of the problem)",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF867C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "It's another Start\\[c\\]up finals, and that means there is pizza to order for the onsite contestants. There are only 2 types of pizza (obviously not, but let's just pretend for the sake of the problem)...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "这是另一次 Start[c]up 决赛，意味着需要为现场参赛者订购披萨。只有两种类型的披萨（显然不是，但为了问题 sake，我们就这样假设），且所有披萨都恰好包含 #cf_span[S] 片。\n\n已知第 #cf_span[i] 位参赛者将吃掉 #cf_span[si] 片披萨，每吃一片第一类披萨可获得 #cf_span[ai] 点快乐值，每吃一片第二类披萨可获得 #cf_span[bi] 点快乐值...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, S \\in \\mathbb{Z}^+ $: number of contestants, slices per pizza.  \nFor each contestant $ i \\in \\{1, \\dots, N\\} $:  \n- $ s_i \\in \\mathbb{Z}^+ $: slices consumed,  \n- $ a_i \\in ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments