A. Chores

Codeforces

IDCF873A

Time2000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Luba has to do _n_ chores today. _i_\-th chore takes _a__i_ units of time to complete. It is guaranteed that for every the condition _a__i_ ≥ _a__i_ - 1 is met, so the sequence is sorted. Also Luba can work really hard on some chores. She can choose not more than _k_ any chores and do each of them in _x_ units of time instead of _a__i_ (). Luba is very responsible, so she has to do all _n_ chores, and now she wants to know the minimum time she needs to do everything. Luba cannot do two chores simultaneously. ## Input The first line contains three integers _n_, _k_, _x_ (1 ≤ _k_ ≤ _n_ ≤ 100, 1 ≤ _x_ ≤ 99) — the number of chores Luba has to do, the number of chores she can do in _x_ units of time, and the number _x_ itself. The second line contains _n_ integer numbers _a__i_ (2 ≤ _a__i_ ≤ 100) — the time Luba has to spend to do _i_\-th chore. It is guaranteed that , and for each _a__i_ ≥ _a__i_ - 1. ## Output Print one number — minimum time Luba needs to do all _n_ chores. [samples] ## Note In the first example the best option would be to do the third and the fourth chore, spending _x_ = 2 time on each instead of _a_3 and _a_4, respectively. Then the answer is 3 + 6 + 2 + 2 = 13. In the second example Luba can choose any two chores to spend _x_ time on them instead of _a__i_. So the answer is 100·3 + 2·1 = 302.

Luba 今天需要完成 #cf_span[n] 项家务。第 #cf_span[i] 项家务需要 #cf_span[ai] 单位时间完成。保证对于每个 $i$，条件 $a_i \geq a_{i-1}$ 成立，因此序列是有序的。此外，Luba 可以非常努力地完成某些家务。她可以选择至多 #cf_span[k] 项家务，将每项的完成时间从 #cf_span[ai] 改为 #cf_span[x]（$1 \leq x \leq 99$）。 Luba 非常负责任，她必须完成所有 #cf_span[n] 项家务，现在她想知道完成所有家务所需的最少时间。Luba 不能同时进行两项家务。第一行包含三个整数 #cf_span[n, k, x (1 ≤ k ≤ n ≤ 100, 1 ≤ x ≤ 99]) —— Luba 需要完成的家务数量、她可以以 #cf_span[x] 单位时间完成的家务数量，以及数值 #cf_span[x] 本身。第二行包含 #cf_span[n] 个整数 #cf_span[ai (2 ≤ ai ≤ 100)] —— Luba 完成第 #cf_span[i] 项家务所需的时间。保证 $a_1 \geq 2$，且对每个 $i$ 都有 $a_i \geq a_{i-1}$。请输出一个数 —— Luba 完成所有 #cf_span[n] 项家务所需的最少时间。在第一个例子中，最佳方案是完成第三项和第四项家务，每项花费 #cf_span[x = 2] 的时间，而不是 #cf_span[a3] 和 #cf_span[a4]。此时答案为 #cf_span[3 + 6 + 2 + 2 = 13]。在第二个例子中，Luba 可以任选两项家务，每项花费 #cf_span[x] 的时间代替 #cf_span[ai]。因此答案为 #cf_span[100·3 + 2·1 = 302]。 ## Input 第一行包含三个整数 #cf_span[n, k, x (1 ≤ k ≤ n ≤ 100, 1 ≤ x ≤ 99]) —— Luba 需要完成的家务数量、她可以以 #cf_span[x] 单位时间完成的家务数量，以及数值 #cf_span[x] 本身。第二行包含 #cf_span[n] 个整数 #cf_span[ai (2 ≤ ai ≤ 100)] —— Luba 完成第 #cf_span[i] 项家务所需的时间。保证 $a_1 \geq 2$，且对每个 $i$ 都有 $a_i \geq a_{i-1}$。 ## Output 请输出一个数 —— Luba 完成所有 #cf_span[n] 项家务所需的最少时间。 [samples] ## Note 在第一个例子中，最佳方案是完成第三项和第四项家务，每项花费 #cf_span[x = 2] 的时间，而不是 #cf_span[a3] 和 #cf_span[a4]。此时答案为 #cf_span[3 + 6 + 2 + 2 = 13]。在第二个例子中，Luba 可以任选两项家务，每项花费 #cf_span[x] 的时间代替 #cf_span[ai]。因此答案为 #cf_span[100·3 + 2·1 = 302]。

**Definitions** Let $ n, k, x \in \mathbb{Z}^+ $ be given integers with $ 1 \leq k \leq n \leq 100 $, $ 1 \leq x \leq 99 $. Let $ A = (a_1, a_2, \dots, a_n) $ be a non-decreasing sequence of integers with $ 2 \leq a_i \leq 100 $ for all $ i $, i.e., $ a_i \geq a_{i-1} $ for $ i = 2, \dots, n $. **Constraints** 1. $ 1 \leq k \leq n \leq 100 $ 2. $ 1 \leq x \leq 99 $ 3. $ 2 \leq a_1 \leq a_2 \leq \dots \leq a_n \leq 100 $ **Objective** Minimize the total time to complete all $ n $ chores, where at most $ k $ chores can be completed in $ x $ time units instead of their original time $ a_i $. The minimal total time is: $$ \min_{S \subseteq \{1, \dots, n\},\ |S| \leq k} \left( \sum_{i=1}^n \begin{cases} x & \text{if } i \in S \\ a_i & \text{if } i \notin S \end{cases} \right) $$ Equivalently: $$ \sum_{i=1}^n a_i - \sum_{i \in S} (a_i - x) $$ where $ S $ is a subset of at most $ k $ indices maximizing $ \sum_{i \in S} (a_i - x) $. Since $ A $ is non-decreasing, the optimal $ S $ consists of the $ \min(k, n) $ largest $ a_i $'s for which $ a_i > x $.

Samples

Input #1

4 2 2
3 6 7 10

Output #1

Input #2

5 2 1
100 100 100 100 100

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Chores",
    "description": {
      "content": "Luba has to do _n_ chores today. _i_\\-th chore takes _a__i_ units of time to complete. It is guaranteed that for every the condition _a__i_ ≥ _a__i_ - 1 is met, so the sequence is sorted. Also Luba c",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF873A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Luba has to do _n_ chores today. _i_\\-th chore takes _a__i_ units of time to complete. It is guaranteed that for every the condition _a__i_ ≥ _a__i_ - 1 is met, so the sequence is sorted.\n\nAlso Luba c...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Luba 今天需要完成 #cf_span[n] 项家务。第 #cf_span[i] 项家务需要 #cf_span[ai] 单位时间完成。保证对于每个 $i$，条件 $a_i \\geq a_{i-1}$ 成立，因此序列是有序的。\n\n此外，Luba 可以非常努力地完成某些家务。她可以选择至多 #cf_span[k] 项家务，将每项的完成时间从 #cf_span[ai] 改为 #cf_span[x]（$...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k, x \\in \\mathbb{Z}^+ $ be given integers with $ 1 \\leq k \\leq n \\leq 100 $, $ 1 \\leq x \\leq 99 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a non-decreasing sequence of integ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments