E. Water Taps

Codeforces

IDCF954E

Time2000ms

Memory256MB

Difficulty—

binary searchgreedysortings

English · Original

Chinese · Translation

Formal · Original

Consider a system of _n_ water taps all pouring water into the same container. The _i_\-th water tap can be set to deliver any amount of water from 0 to _a__i_ ml per second (this amount may be a real number). The water delivered by _i_\-th tap has temperature _t__i_. If for every you set _i_\-th tap to deliver exactly _x__i_ ml of water per second, then the resulting temperature of water will be (if , then to avoid division by zero we state that the resulting water temperature is 0). You have to set all the water taps in such a way that the resulting temperature is exactly _T_. What is the maximum amount of water you may get per second if its temperature has to be _T_? ## Input The first line contains two integers _n_ and _T_ (1 ≤ _n_ ≤ 200000, 1 ≤ _T_ ≤ 106) — the number of water taps and the desired temperature of water, respectively. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 106) where _a__i_ is the maximum amount of water _i_\-th tap can deliver per second. The third line contains _n_ integers _t_1, _t_2, ..., _t__n_ (1 ≤ _t__i_ ≤ 106) — the temperature of water each tap delivers. ## Output Print the maximum possible amount of water with temperature exactly _T_ you can get per second (if it is impossible to obtain water with such temperature, then the answer is considered to be 0). Your answer is considered correct if its absolute or relative error doesn't exceed 10 - 6. [samples]

考虑一个由 #cf_span[n] 个水龙头组成的系统，所有水龙头均向同一个容器注水。第 #cf_span[i] 个水龙头可以设置为每秒输送从 #cf_span[0] 到 #cf_span[ai] 毫升的任意水量（该数值可以是实数）。第 #cf_span[i] 个水龙头输送的水的温度为 #cf_span[ti]。若对每个 #cf_span[i]，你将第 #cf_span[i] 个水龙头设置为每秒输送恰好 #cf_span[xi] 毫升水，则所得水的温度为 $\frac{\sum_{i=1}^{n} x_i \cdot t_i}{\sum_{i=1}^{n} x_i}$（若 $\sum_{i=1}^{n} x_i = 0$，为避免除零，我们规定所得水的温度为 #cf_span[0]）。你需要设置所有水龙头，使得最终水温恰好为 #cf_span[T]。在水温必须为 #cf_span[T] 的前提下，你能获得的最大水量是多少（以每秒毫升计）？第一行包含两个整数 #cf_span[n] 和 #cf_span[T]（#cf_span[1 ≤ n ≤ 200000]，#cf_span[1 ≤ T ≤ 106]）——水龙头的数量和期望的水温。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 106]），其中 #cf_span[ai] 表示第 #cf_span[i] 个水龙头每秒能输送的最大水量。第三行包含 #cf_span[n] 个整数 #cf_span[t1], #cf_span[t2], ..., #cf_span[tn]（#cf_span[1 ≤ ti ≤ 106]）——每个水龙头输送水的温度。请输出在温度恰好为 #cf_span[T] 时，你能获得的最大水量（每秒毫升数）（若无法获得该温度的水，则答案视为 #cf_span[0]）。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[T]（#cf_span[1 ≤ n ≤ 200000]，#cf_span[1 ≤ T ≤ 106]）——水龙头的数量和期望的水温。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an]（#cf_span[1 ≤ ai ≤ 106]），其中 #cf_span[ai] 表示第 #cf_span[i] 个水龙头每秒能输送的最大水量。第三行包含 #cf_span[n] 个整数 #cf_span[t1], #cf_span[t2], ..., #cf_span[tn]（#cf_span[1 ≤ ti ≤ 106]）——每个水龙头输送水的温度。 ## Output 请输出在温度恰好为 #cf_span[T] 时，你能获得的最大水量（每秒毫升数）（若无法获得该温度的水，则答案视为 #cf_span[0]）。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 6]，则被视为正确。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $, $ T \in \mathbb{R} $. Let $ \mathbf{a} = (a_1, \dots, a_n) \in \mathbb{R}^n_{\geq 0} $ be the maximum flow rates of the taps. Let $ \mathbf{t} = (t_1, \dots, t_n) \in \mathbb{R}^n $ be the temperatures of the taps. Let $ \mathbf{x} = (x_1, \dots, x_n) \in \mathbb{R}^n_{\geq 0} $ be the actual flow rates, with $ 0 \leq x_i \leq a_i $ for all $ i $. **Constraints** 1. $ \sum_{i=1}^n x_i t_i = T \cdot \sum_{i=1}^n x_i $ 2. $ 0 \leq x_i \leq a_i $ for all $ i \in \{1, \dots, n\} $ 3. If $ \sum_{i=1}^n x_i = 0 $, then the temperature is defined as 0. **Objective** Maximize $ S = \sum_{i=1}^n x_i $, subject to the above constraints. If no such $ \mathbf{x} $ exists satisfying the temperature constraint with $ S > 0 $, then $ S = 0 $.

Samples

Input #1

2 100
3 10
50 150

Output #1

6.000000000000000

Input #2

3 9
5 5 30
6 6 10

Output #2

40.000000000000000

Input #3

2 12
1 3
10 15

Output #3

1.666666666666667

API Response (JSON)

{
  "problem": {
    "name": "E. Water Taps",
    "description": {
      "content": "Consider a system of _n_ water taps all pouring water into the same container. The _i_\\-th water tap can be set to deliver any amount of water from 0 to _a__i_ ml per second (this amount may be a real",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF954E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider a system of _n_ water taps all pouring water into the same container. The _i_\\-th water tap can be set to deliver any amount of water from 0 to _a__i_ ml per second (this amount may be a real...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "考虑一个由 #cf_span[n] 个水龙头组成的系统，所有水龙头均向同一个容器注水。第 #cf_span[i] 个水龙头可以设置为每秒输送从 #cf_span[0] 到 #cf_span[ai] 毫升的任意水量（该数值可以是实数）。第 #cf_span[i] 个水龙头输送的水的温度为 #cf_span[ti]。\n\n若对每个 #cf_span[i]，你将第 #cf_span[i] 个水龙头设置为每...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ T \\in \\mathbb{R} $.  \nLet $ \\mathbf{a} = (a_1, \\dots, a_n) \\in \\mathbb{R}^n_{\\geq 0} $ be the maximum flow rates of the taps.  \nLet $ \\mathbf{t} = (t_1,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments