D. Michael and Charging Stations

Codeforces

IDCF853D

Time2000ms

Memory512MB

Difficulty—

binary searchdpgreedy

English · Original

Chinese · Translation

Formal · Original

Michael has just bought a new electric car for moving across city. Michael does not like to overwork, so each day he drives to only one of two his jobs. Michael's day starts from charging his electric car for getting to the work and back. He spends 1000 burles on charge if he goes to the first job, and 2000 burles if he goes to the second job. On a charging station he uses there is a loyalty program that involves bonus cards. Bonus card may have some non-negative amount of bonus burles. Each time customer is going to buy something for the price of _x_ burles, he is allowed to pay an amount of _y_ (0 ≤ _y_ ≤ _x_) burles that does not exceed the bonus card balance with bonus burles. In this case he pays _x_ - _y_ burles with cash, and the balance on the bonus card is decreased by _y_ bonus burles. If customer pays whole price with cash (i.e., _y_ = 0) then 10% of price is returned back to the bonus card. This means that bonus card balance increases by bonus burles. Initially the bonus card balance is equal to 0 bonus burles. Michael has planned next _n_ days and he knows how much does the charge cost on each of those days. Help Michael determine the minimum amount of burles in cash he has to spend with optimal use of bonus card. Assume that Michael is able to cover any part of the price with cash in any day. It is not necessary to spend all bonus burles at the end of the given period. ## Input The first line of input contains a single integer _n_ (1 ≤ _n_ ≤ 300 000), the number of days Michael has planned. Next line contains _n_ integers _a_1, _a_2, ..., _a__n_ (_a__i_ = 1000 or _a__i_ = 2000) with _a__i_ denoting the charging cost at the day _i_. ## Output Output the minimum amount of burles Michael has to spend. [samples] ## Note In the first sample case the most optimal way for Michael is to pay for the first two days spending 3000 burles and get 300 bonus burles as return. After that he is able to pay only 700 burles for the third days, covering the rest of the price with bonus burles. In the second sample case the most optimal way for Michael is to pay the whole price for the first five days, getting 1000 bonus burles as return and being able to use them on the last day without paying anything in cash.

Michael 刚买了一辆电动汽车用于在城市中通勤。Michael 不喜欢过度劳累，因此每天他只前往两个工作地点中的一个。 Michael 的一天从为电动汽车充电以往返工作地点开始。如果他去第一个工作地点，充电费用为 #cf_span[1000] 卢布；如果去第二个工作地点，则为 #cf_span[2000] 卢布。他使用的充电站有一个忠诚度计划，涉及积分卡。积分卡上可以有非负数量的积分卢布。每当客户购买价格为 #cf_span[x] 卢布的商品时，他可以选择使用积分卡支付不超过余额的 #cf_span[y] 卢布（#cf_span[0 ≤ y ≤ x]）。此时，他用现金支付 #cf_span[x - y] 卢布，积分卡余额减少 #cf_span[y] 积分卢布。如果客户完全用现金支付（即 #cf_span[y = 0]），则价格的 10% 将返还至积分卡。这意味着积分卡余额增加 #cf_span[0.1 × x] 积分卢布。初始时，积分卡余额为 0 积分卢布。 Michael 已规划了接下来的 #cf_span[n] 天，并知道每天的充电费用。请帮助 Michael 确定在最优使用积分卡的情况下，他最少需要花费多少现金。假设 Michael 在任何一天都可以用现金支付任意金额。在给定时间段结束时，不需要用完所有积分卢布。输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 300 000]），表示 Michael 规划的天数。下一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[ai = 1000] 或 #cf_span[ai = 2000]），其中 #cf_span[ai] 表示第 #cf_span[i] 天的充电费用。请输出 Michael 最少需要花费的现金卢布数。在第一个样例中，Michael 最优的方式是：前两天完全用现金支付，共花费 3000 卢布，并获得 300 积分卢布返还。之后，他只需为第三天支付 700 卢布现金，其余部分使用积分卢布支付。在第二个样例中，Michael 最优的方式是：前五天完全用现金支付，获得 1000 积分卢布返还，并在最后一天完全使用这些积分卢布，无需支付任何现金。 ## Input 输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 300 000]），表示 Michael 规划的天数。下一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[ai = 1000] 或 #cf_span[ai = 2000]），其中 #cf_span[ai] 表示第 #cf_span[i] 天的充电费用。 ## Output 输出 Michael 最少需要花费的现金卢布数。 [samples] ## Note 在第一个样例中，Michael 最优的方式是：前两天完全用现金支付，共花费 3000 卢布，并获得 300 积分卢布返还。之后，他只需为第三天支付 700 卢布现金，其余部分使用积分卢布支付。在第二个样例中，Michael 最优的方式是：前五天完全用现金支付，获得 1000 积分卢布返还，并在最后一天完全使用这些积分卢布，无需支付任何现金。

**Definitions:** - Let $ n \in \mathbb{N} $, $ 1 \leq n \leq 300{,}000 $, be the number of days. - Let $ a_i \in \{1000, 2000\} $ for $ i = 1, 2, \dots, n $, denote the cost of charging on day $ i $. - Let $ B \in \mathbb{R}_{\geq 0} $ denote the current bonus card balance (in bonus burles). - Initially, $ B = 0 $. **Payment Rule:** On day $ i $, with cost $ a_i $: - Michael may choose $ y_i \in [0, a_i] $, such that $ y_i \leq B $, to pay using bonus burles. - Then he pays $ a_i - y_i $ in cash. - If $ y_i = 0 $ (i.e., no bonus used), then $ 0.1 \cdot a_i $ bonus burles are added to the card: $$ B \leftarrow B + 0.1 \cdot a_i $$ - If $ y_i > 0 $, then: $$ B \leftarrow B - y_i $$ **Objective:** Minimize total cash spent over $ n $ days: $$ \sum_{i=1}^n (a_i - y_i) $$ **Constraints:** - $ 0 \leq y_i \leq \min(B, a_i) $ for all $ i $ - $ B \geq 0 $ always - $ B $ evolves as described above **Goal:** Find the minimum possible value of $ \sum_{i=1}^n (a_i - y_i) $ over all valid sequences $ y_1, y_2, \dots, y_n $.

Samples

Input #1

3
1000 2000 1000

Output #1

Input #2

6
2000 2000 2000 2000 2000 1000

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Michael and Charging Stations",
    "description": {
      "content": "Michael has just bought a new electric car for moving across city. Michael does not like to overwork, so each day he drives to only one of two his jobs. Michael's day starts from charging his electri",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF853D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Michael has just bought a new electric car for moving across city. Michael does not like to overwork, so each day he drives to only one of two his jobs.\n\nMichael's day starts from charging his electri...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Michael 刚买了一辆电动汽车用于在城市中通勤。Michael 不喜欢过度劳累，因此每天他只前往两个工作地点中的一个。\n\nMichael 的一天从为电动汽车充电以往返工作地点开始。如果他去第一个工作地点，充电费用为 #cf_span[1000] 卢布；如果去第二个工作地点，则为 #cf_span[2000] 卢布。\n\n他使用的充电站有一个忠诚度计划，涉及积分卡。积分卡上可以有非负数量的积分卢布...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions:**\n\n- Let $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 300{,}000 $, be the number of days.\n- Let $ a_i \\in \\{1000, 2000\\} $ for $ i = 1, 2, \\dots, n $, denote the cost of charging on day $ i $....",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments