C. Party Lemonade

Codeforces

IDCF913C

Time1000ms

Memory256MB

Difficulty—

bitmasksdpgreedy

English · Original

Chinese · Translation

Formal · Original

A New Year party is not a New Year party without lemonade! As usual, you are expecting a lot of guests, and buying lemonade has already become a pleasant necessity. Your favorite store sells lemonade in bottles of _n_ different volumes at different costs. A single bottle of type _i_ has volume 2_i_ - 1 liters and costs _c__i_ roubles. The number of bottles of each type in the store can be considered infinite. You want to buy at least _L_ liters of lemonade. How many roubles do you have to spend? ## Input The first line contains two integers _n_ and _L_ (1 ≤ _n_ ≤ 30; 1 ≤ _L_ ≤ 109) — the number of types of bottles in the store and the required amount of lemonade in liters, respectively. The second line contains _n_ integers _c_1, _c_2, ..., _c__n_ (1 ≤ _c__i_ ≤ 109) — the costs of bottles of different types. ## Output Output a single integer — the smallest number of roubles you have to pay in order to buy at least _L_ liters of lemonade. [samples] ## Note In the first example you should buy one 8-liter bottle for 90 roubles and two 2-liter bottles for 30 roubles each. In total you'll get 12 liters of lemonade for just 150 roubles. In the second example, even though you need only 3 liters, it's cheaper to buy a single 8-liter bottle for 10 roubles. In the third example it's best to buy three 1-liter bottles for 10 roubles each, getting three liters for 30 roubles.

没有柠檬水的跨年派对还算什么跨年派对！和往常一样，你预计会有很多客人，购买柠檬水已经成为一种愉快的必需品。你最喜欢的商店出售不同容量和价格的柠檬水瓶，共有 #cf_span[n] 种类型。每种类型 #cf_span[i] 的瓶子容量为 #cf_span[2i - 1] 升，价格为 #cf_span[ci] 卢布。每种类型的瓶子库存都可以视为无限。你希望购买至少 #cf_span[L] 升柠檬水。你需要花费多少卢布？第一行包含两个整数 #cf_span[n] 和 #cf_span[L]（#cf_span[1 ≤ n ≤ 30]；#cf_span[1 ≤ L ≤ 10^9]）— 分别表示商店中瓶子的类型数和所需的柠檬水总量（升）。第二行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[1 ≤ ci ≤ 10^9]）— 表示每种类型瓶子的价格。请输出一个整数 —— 为了购买至少 #cf_span[L] 升柠檬水所需的最少卢布数。在第一个例子中，你应该购买一个 8 升的瓶子（90 卢布）和两个 2 升的瓶子（每个 30 卢布），总共获得 12 升柠檬水，花费 150 卢布。在第二个例子中，尽管你只需要 3 升，但购买一个 8 升的瓶子（10 卢布）更便宜。在第三个例子中，最好购买三个 1 升的瓶子（每个 10 卢布），总共获得 3 升，花费 30 卢布。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[L]（#cf_span[1 ≤ n ≤ 30]；#cf_span[1 ≤ L ≤ 10^9]）— 分别表示商店中瓶子的类型数和所需的柠檬水总量（升）。第二行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[1 ≤ ci ≤ 10^9]）— 表示每种类型瓶子的价格。 ## Output 请输出一个整数 —— 为了购买至少 #cf_span[L] 升柠檬水所需的最少卢布数。 [samples] ## Note 在第一个例子中，你应该购买一个 8 升的瓶子（90 卢布）和两个 2 升的瓶子（每个 30 卢布），总共获得 12 升柠檬水，花费 150 卢布。在第二个例子中，尽管你只需要 3 升，但购买一个 8 升的瓶子（10 卢布）更便宜。在第三个例子中，最好购买三个 1 升的瓶子（每个 10 卢布），总共获得 3 升，花费 30 卢布。

**Definitions:** - Let $ n \in \mathbb{N} $, $ L \in \mathbb{N} $. - For $ i \in \{1, 2, \dots, n\} $, define bottle type $ i $ with volume $ v_i = 2^{i-1} $ liters and cost $ c_i \in \mathbb{N} $. **Given:** - $ 1 \leq n \leq 30 $ - $ 1 \leq L \leq 10^9 $ - $ 1 \leq c_i \leq 10^9 $ **Objective:** Minimize total cost $ \sum_{i=1}^n x_i c_i $, subject to: - $ x_i \in \mathbb{Z}_{\geq 0} $ for all $ i \in \{1, 2, \dots, n\} $ - $ \sum_{i=1}^n x_i \cdot 2^{i-1} \geq L $ **Optimization Problem:** $$ \min_{x_1, x_2, \dots, x_n \in \mathbb{Z}_{\geq 0}} \sum_{i=1}^n x_i c_i \quad \text{subject to} \quad \sum_{i=1}^n x_i \cdot 2^{i-1} \geq L $$

Samples

Input #1

4 12
20 30 70 90

Output #1

Input #2

4 3
10000 1000 100 10

Output #2

Input #3

4 3
10 100 1000 10000

Output #3

Input #4

5 787787787
123456789 234567890 345678901 456789012 987654321

Output #4

44981600785557577

API Response (JSON)

{
  "problem": {
    "name": "C. Party Lemonade",
    "description": {
      "content": "A New Year party is not a New Year party without lemonade! As usual, you are expecting a lot of guests, and buying lemonade has already become a pleasant necessity. Your favorite store sells lemonade",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF913C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A New Year party is not a New Year party without lemonade! As usual, you are expecting a lot of guests, and buying lemonade has already become a pleasant necessity.\n\nYour favorite store sells lemonade...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "没有柠檬水的跨年派对还算什么跨年派对！和往常一样，你预计会有很多客人，购买柠檬水已经成为一种愉快的必需品。\n\n你最喜欢的商店出售不同容量和价格的柠檬水瓶，共有 #cf_span[n] 种类型。每种类型 #cf_span[i] 的瓶子容量为 #cf_span[2i - 1] 升，价格为 #cf_span[ci] 卢布。每种类型的瓶子库存都可以视为无限。\n\n你希望购买至少 #cf_span[L] 升柠...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions:**\n- Let $ n \\in \\mathbb{N} $, $ L \\in \\mathbb{N} $.\n- For $ i \\in \\{1, 2, \\dots, n\\} $, define bottle type $ i $ with volume $ v_i = 2^{i-1} $ liters and cost $ c_i \\in \\mathbb{N} $.\n\n*...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments