309892: CF1753E. N Machines
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
N Machines
题意翻译
给定一个操作序列，每一个操作形如 $(+,a_i)$ 或 $(*,a_i)$ 。当前有一个变量 $x$，起始时 $x=1$，然后按操作序列的顺序进行操作。 当进行一次 $(+,a_i)$ 操作以后 $x$ 变为 $x+a_i$。 当进行一次 $(*,a_i)$ 操作以后 $x$ 变为 $x \cdot a_i$。 现在你手中有 $b$ 块钱，你可以花费 $p$ 块钱将一个加法操作移动到操作序列的任意位置，也可以花费 $m$ 块钱将一个乘法操作移到操作序列任意位置。 请问经过操作以后所能得到的 $x$ 的最大值。 保证初始操作序列所得结果不会超过 $2\times 10^9$。题目描述
You have been invited as a production process optimization specialist to some very large company. The company has $ n $ machines at its factory, standing one behind another in the production chain. Each machine can be described in one of the following two ways: $ (+,~a_i) $ or $ (*,~a_i) $ . If a workpiece with the value $ x $ is supplied to the machine of kind $ (+,~a_i) $ , then the output workpiece has value $ x + a_i $ . If a workpiece with the value $ x $ is supplied to the machine of kind $ (*,~a_i) $ , then the output workpiece has value $ x \cdot a_i $ . The whole production process is as follows. The workpiece with the value $ 1 $ is supplied to the first machine, then the workpiece obtained after the operation of the first machine is supplied to the second machine, then the workpiece obtained after the operation of the second machine is supplied to the third machine, and so on. The company is not doing very well, so now the value of the resulting product does not exceed $ 2 \cdot 10^9 $ . The directors of the company are not satisfied with the efficiency of the production process and have given you a budget of $ b $ coins to optimize it. To optimize production you can change the order of machines in the chain. Namely, by spending $ p $ coins, you can take any machine of kind $ (+,~a_i) $ and move it to any place in the chain without changing the order of other machines. Also, by spending $ m $ coins, you can take any machine of kind $ (*,~a_i) $ and move it to any place in the chain. What is the maximum value of the resulting product that can be achieved if the total cost of movements that are made should not exceed $ b $ coins?输入输出格式
输入格式
The first line contains four integers $ n $ , $ b $ , $ p $ and $ m $ ( $ 1 \le n \le 10^6 $ , $ 1 \le b, p, m \le 10^9 $ ) — the number of machine at the factory, your budget and costs of movements of both kinds of machines. Each of the following $ n $ lines contains description of a machine. The description begins with one of the following characters: "+" or "\*", that denotes the kind of the machine. Then an integer $ a_i $ follows ( $ 1 \le a_i \le 2 \cdot 10^9 $ ). It's guaranteed that the current value of the resulting product does not exceed $ 2 \cdot 10^9 $ .
输出格式
Print one integer — the maximum value of the resulting product that can be achieved if the total cost of movements that are made does not exceed $ b $ coins.
输入输出样例
输入样例 #1
3 2 1 3
* 2
+ 1
+ 1输出样例 #1
6输入样例 #2
4 2 2 2
* 2
+ 1
* 3
+ 2输出样例 #2
21输入样例 #3
8 2 1 1
* 2
+ 1
* 4
+ 1
+ 1
+ 1
* 5
+ 3输出样例 #3
240说明
In the first example our budget is too low to move machine $ (*,~2) $ , but we can move both machines $ (+,~1) $ to the beginning of the chain. So the final chain will be $ (+,~1) $ $ (+,~1) $ $ (*,~2) $ . If the workpiece with the value $ 1 $ is supplied to the first machine, its value will be changed in the following way: $ 1, 2, 3, 6 $ . In the second example we can move only one machine. Let's move machine $ (+,~2) $ to the beginning of the chain. The final chain will be $ (+,~2) $ $ (*,~2) $ $ (+,~1) $ $ (*,~3) $ . The value of the workpiece will be changed in the following way: $ 1, 3, 6, 7, 21 $ . In the third example we can place machine $ (*,~4) $ before the machine $ (*,~5) $ , and move machine $ (+,~3) $ to the beginning of the chain. The final chain will be $ (+,~3) $ $ (*,~2) $ $ (+,~1) $ $ (+,~1) $ $ (+,~1) $ $ (+,~1) $ $ (*,~4) $ $ (*,~5) $ . The value of the workpiece will be changed in the following way: $ 1, 4, 8, 9, 10, 11, 12, 48, 240 $ .Input
题意翻译
给定一个操作序列，每一个操作形如 $(+,a_i)$ 或 $(*,a_i)$ 。当前有一个变量 $x$，起始时 $x=1$，然后按操作序列的顺序进行操作。 当进行一次 $(+,a_i)$ 操作以后 $x$ 变为 $x+a_i$。 当进行一次 $(*,a_i)$ 操作以后 $x$ 变为 $x \cdot a_i$。 现在你手中有 $b$ 块钱，你可以花费 $p$ 块钱将一个加法操作移动到操作序列的任意位置，也可以花费 $m$ 块钱将一个乘法操作移到操作序列任意位置。 请问经过操作以后所能得到的 $x$ 的最大值。 保证初始操作序列所得结果不会超过 $2\times 10^9$。Output
**N Machines**
**题意翻译**：
给定一个操作序列，每个操作形如 $(+,a_i)$ 或 $(*,a_i)$ 。初始有一个变量 $x$，起始时 $x=1$，然后按操作序列的顺序进行操作。
当进行一次 $(+,a_i)$ 操作后，$x$ 变为 $x+a_i$。
当进行一次 $(*,a_i)$ 操作后，$x$ 变为 $x \cdot a_i$。
现在你手中有 $b$ 块钱，你可以花费 $p$ 块钱将一个加法操作移动到操作序列的任意位置，也可以花费 $m$ 块钱将一个乘法操作移到操作序列的任意位置。
问经过操作后所能得到的 $x$ 的最大值。
保证初始操作序列所得结果不会超过 $2\times 10^9$。
**题目描述**：
你被邀请作为生产过程优化专家参加一家非常大的公司。该公司工厂里有 $ n $ 台机器，依次排列在生产链中。每台机器可以用以下两种方式之一描述：$ (+,~a_i) $ 或 $ (*,~a_i) $。
如果一个工作件的价值为 $ x $ 被供应到类型为 $ (+,~a_i) $ 的机器，那么输出工作件的价值为 $ x + a_i $。
如果一个工作件的价值为 $ x $ 被供应到类型为 $ (*,~a_i) $ 的机器，那么输出工作件的价值为 $ x \cdot a_i $。
整个生产过程如下。价值为 $ 1 $ 的工作件被供应到第一台机器，然后第一台机器操作后得到的工作件被供应到第二台机器，依此类推。公司目前经营不善，因此最终产品的价值不超过 $ 2 \cdot 10^9 $。
公司董事会对生产效率不满意，并给你一个预算 $ b $ 来优化它。
为了优化生产，你可以改变链中机器的顺序。具体来说，花费 $ p $ 个硬币，你可以取出任何类型为 $ (+,~a_i) $ 的机器并将其移动到链中的任何位置，而不改变其他机器的顺序。同样，花费 $ m $ 个硬币，你可以取出任何类型为 $ (*,~a_i) $ 的机器并将其移动到链中的任何位置。
如果移动的总成本不超过 $ b $ 个硬币，问最终产品可以达到的最大价值是多少？
**输入输出格式**：
**输入格式**：
第一行包含四个整数 $ n $, $ b $, $ p $ 和 $ m $（$ 1 \le n \le 10^6 $, $ 1 \le b, p, m \le 10^9 $）——工厂中的机器数量、你的预算和两种类型机器的移动成本。
接下来的 $ n $ 行包含对机器的描述。描述以以下字符之一开始："+" 或 "\*"，表示机器的类型。然后是一个整数 $ a_i $（$ 1 \le a_i \le 2 \cdot 10^9 $）。
保证当前结果产品的价值不超过 $ 2 \cdot 10^9 $。
**输出格式**：
打印一个整数——如果移动的总成本不超过 $ b $ 个硬币，可以实现的最终产品的最大价值。
**输入输出样例**：
**输入样例 #1**：
```
3 2 1 3
* 2
+ 1
+ 1
```
**输出样例 #1**：
```
6
```
**输入样例 #2**：
```
4 2 2 2
* 2
+ 1
* 3
+ 2
```
**输出样例 #2**：
```
21
```
**输入样例 #3**：
```
8 2 1 1
* 2
+ 1
* 4
+ 1
+ 1
+ 1
* 5
+ 3
```
**输出样例 #3**：
```
240
```
**说明**：
在第一个示例中，我们的预算太低，无法移动 $ (*,~2) $ 机器，但我们可以将两个 $ (+,~1) $ 机器都移动到链的开始。所以最终的链将是 $ (+,~1) $ $ (+,~1) $ $ (*,~2) $。如果价值为 $ 1 $ 的工作件被供应到第一台机器，其价值将按以下方式改变：$ 1, 2, 3, 6 $。
在第二个示例中，我们只能移动一台机器。让我们将 $ (+,~2) $ 机器移动到链的开始。最终的链将是 $ (+,~2) $ $ (*,~2) $ $ (+,~1)**N Machines** **题意翻译**： 给定一个操作序列，每个操作形如 $(+,a_i)$ 或 $(*,a_i)$ 。初始有一个变量 $x$，起始时 $x=1$，然后按操作序列的顺序进行操作。 当进行一次 $(+,a_i)$ 操作后，$x$ 变为 $x+a_i$。 当进行一次 $(*,a_i)$ 操作后，$x$ 变为 $x \cdot a_i$。 现在你手中有 $b$ 块钱，你可以花费 $p$ 块钱将一个加法操作移动到操作序列的任意位置，也可以花费 $m$ 块钱将一个乘法操作移到操作序列的任意位置。 问经过操作后所能得到的 $x$ 的最大值。 保证初始操作序列所得结果不会超过 $2\times 10^9$。 **题目描述**： 你被邀请作为生产过程优化专家参加一家非常大的公司。该公司工厂里有 $ n $ 台机器，依次排列在生产链中。每台机器可以用以下两种方式之一描述：$ (+,~a_i) $ 或 $ (*,~a_i) $。 如果一个工作件的价值为 $ x $ 被供应到类型为 $ (+,~a_i) $ 的机器，那么输出工作件的价值为 $ x + a_i $。 如果一个工作件的价值为 $ x $ 被供应到类型为 $ (*,~a_i) $ 的机器，那么输出工作件的价值为 $ x \cdot a_i $。 整个生产过程如下。价值为 $ 1 $ 的工作件被供应到第一台机器，然后第一台机器操作后得到的工作件被供应到第二台机器，依此类推。公司目前经营不善，因此最终产品的价值不超过 $ 2 \cdot 10^9 $。 公司董事会对生产效率不满意，并给你一个预算 $ b $ 来优化它。 为了优化生产，你可以改变链中机器的顺序。具体来说，花费 $ p $ 个硬币，你可以取出任何类型为 $ (+,~a_i) $ 的机器并将其移动到链中的任何位置，而不改变其他机器的顺序。同样，花费 $ m $ 个硬币，你可以取出任何类型为 $ (*,~a_i) $ 的机器并将其移动到链中的任何位置。 如果移动的总成本不超过 $ b $ 个硬币，问最终产品可以达到的最大价值是多少？ **输入输出格式**： **输入格式**： 第一行包含四个整数 $ n $, $ b $, $ p $ 和 $ m $（$ 1 \le n \le 10^6 $, $ 1 \le b, p, m \le 10^9 $）——工厂中的机器数量、你的预算和两种类型机器的移动成本。 接下来的 $ n $ 行包含对机器的描述。描述以以下字符之一开始："+" 或 "\*"，表示机器的类型。然后是一个整数 $ a_i $（$ 1 \le a_i \le 2 \cdot 10^9 $）。 保证当前结果产品的价值不超过 $ 2 \cdot 10^9 $。 **输出格式**： 打印一个整数——如果移动的总成本不超过 $ b $ 个硬币，可以实现的最终产品的最大价值。 **输入输出样例**： **输入样例 #1**： ``` 3 2 1 3 * 2 + 1 + 1 ``` **输出样例 #1**： ``` 6 ``` **输入样例 #2**： ``` 4 2 2 2 * 2 + 1 * 3 + 2 ``` **输出样例 #2**： ``` 21 ``` **输入样例 #3**： ``` 8 2 1 1 * 2 + 1 * 4 + 1 + 1 + 1 * 5 + 3 ``` **输出样例 #3**： ``` 240 ``` **说明**： 在第一个示例中，我们的预算太低，无法移动 $ (*,~2) $ 机器，但我们可以将两个 $ (+,~1) $ 机器都移动到链的开始。所以最终的链将是 $ (+,~1) $ $ (+,~1) $ $ (*,~2) $。如果价值为 $ 1 $ 的工作件被供应到第一台机器，其价值将按以下方式改变：$ 1, 2, 3, 6 $。 在第二个示例中，我们只能移动一台机器。让我们将 $ (+,~2) $ 机器移动到链的开始。最终的链将是 $ (+,~2) $ $ (*,~2) $ $ (+,~1)
**题意翻译**：
给定一个操作序列，每个操作形如 $(+,a_i)$ 或 $(*,a_i)$ 。初始有一个变量 $x$，起始时 $x=1$，然后按操作序列的顺序进行操作。
当进行一次 $(+,a_i)$ 操作后，$x$ 变为 $x+a_i$。
当进行一次 $(*,a_i)$ 操作后，$x$ 变为 $x \cdot a_i$。
现在你手中有 $b$ 块钱，你可以花费 $p$ 块钱将一个加法操作移动到操作序列的任意位置，也可以花费 $m$ 块钱将一个乘法操作移到操作序列的任意位置。
问经过操作后所能得到的 $x$ 的最大值。
保证初始操作序列所得结果不会超过 $2\times 10^9$。
**题目描述**：
你被邀请作为生产过程优化专家参加一家非常大的公司。该公司工厂里有 $ n $ 台机器，依次排列在生产链中。每台机器可以用以下两种方式之一描述：$ (+,~a_i) $ 或 $ (*,~a_i) $。
如果一个工作件的价值为 $ x $ 被供应到类型为 $ (+,~a_i) $ 的机器，那么输出工作件的价值为 $ x + a_i $。
如果一个工作件的价值为 $ x $ 被供应到类型为 $ (*,~a_i) $ 的机器，那么输出工作件的价值为 $ x \cdot a_i $。
整个生产过程如下。价值为 $ 1 $ 的工作件被供应到第一台机器，然后第一台机器操作后得到的工作件被供应到第二台机器，依此类推。公司目前经营不善，因此最终产品的价值不超过 $ 2 \cdot 10^9 $。
公司董事会对生产效率不满意，并给你一个预算 $ b $ 来优化它。
为了优化生产，你可以改变链中机器的顺序。具体来说，花费 $ p $ 个硬币，你可以取出任何类型为 $ (+,~a_i) $ 的机器并将其移动到链中的任何位置，而不改变其他机器的顺序。同样，花费 $ m $ 个硬币，你可以取出任何类型为 $ (*,~a_i) $ 的机器并将其移动到链中的任何位置。
如果移动的总成本不超过 $ b $ 个硬币，问最终产品可以达到的最大价值是多少？
**输入输出格式**：
**输入格式**：
第一行包含四个整数 $ n $, $ b $, $ p $ 和 $ m $（$ 1 \le n \le 10^6 $, $ 1 \le b, p, m \le 10^9 $）——工厂中的机器数量、你的预算和两种类型机器的移动成本。
接下来的 $ n $ 行包含对机器的描述。描述以以下字符之一开始："+" 或 "\*"，表示机器的类型。然后是一个整数 $ a_i $（$ 1 \le a_i \le 2 \cdot 10^9 $）。
保证当前结果产品的价值不超过 $ 2 \cdot 10^9 $。
**输出格式**：
打印一个整数——如果移动的总成本不超过 $ b $ 个硬币，可以实现的最终产品的最大价值。
**输入输出样例**：
**输入样例 #1**：
```
3 2 1 3
* 2
+ 1
+ 1
```
**输出样例 #1**：
```
6
```
**输入样例 #2**：
```
4 2 2 2
* 2
+ 1
* 3
+ 2
```
**输出样例 #2**：
```
21
```
**输入样例 #3**：
```
8 2 1 1
* 2
+ 1
* 4
+ 1
+ 1
+ 1
* 5
+ 3
```
**输出样例 #3**：
```
240
```
**说明**：
在第一个示例中，我们的预算太低，无法移动 $ (*,~2) $ 机器，但我们可以将两个 $ (+,~1) $ 机器都移动到链的开始。所以最终的链将是 $ (+,~1) $ $ (+,~1) $ $ (*,~2) $。如果价值为 $ 1 $ 的工作件被供应到第一台机器，其价值将按以下方式改变：$ 1, 2, 3, 6 $。
在第二个示例中，我们只能移动一台机器。让我们将 $ (+,~2) $ 机器移动到链的开始。最终的链将是 $ (+,~2) $ $ (*,~2) $ $ (+,~1)**N Machines** **题意翻译**： 给定一个操作序列，每个操作形如 $(+,a_i)$ 或 $(*,a_i)$ 。初始有一个变量 $x$，起始时 $x=1$，然后按操作序列的顺序进行操作。 当进行一次 $(+,a_i)$ 操作后，$x$ 变为 $x+a_i$。 当进行一次 $(*,a_i)$ 操作后，$x$ 变为 $x \cdot a_i$。 现在你手中有 $b$ 块钱，你可以花费 $p$ 块钱将一个加法操作移动到操作序列的任意位置，也可以花费 $m$ 块钱将一个乘法操作移到操作序列的任意位置。 问经过操作后所能得到的 $x$ 的最大值。 保证初始操作序列所得结果不会超过 $2\times 10^9$。 **题目描述**： 你被邀请作为生产过程优化专家参加一家非常大的公司。该公司工厂里有 $ n $ 台机器，依次排列在生产链中。每台机器可以用以下两种方式之一描述：$ (+,~a_i) $ 或 $ (*,~a_i) $。 如果一个工作件的价值为 $ x $ 被供应到类型为 $ (+,~a_i) $ 的机器，那么输出工作件的价值为 $ x + a_i $。 如果一个工作件的价值为 $ x $ 被供应到类型为 $ (*,~a_i) $ 的机器，那么输出工作件的价值为 $ x \cdot a_i $。 整个生产过程如下。价值为 $ 1 $ 的工作件被供应到第一台机器，然后第一台机器操作后得到的工作件被供应到第二台机器，依此类推。公司目前经营不善，因此最终产品的价值不超过 $ 2 \cdot 10^9 $。 公司董事会对生产效率不满意，并给你一个预算 $ b $ 来优化它。 为了优化生产，你可以改变链中机器的顺序。具体来说，花费 $ p $ 个硬币，你可以取出任何类型为 $ (+,~a_i) $ 的机器并将其移动到链中的任何位置，而不改变其他机器的顺序。同样，花费 $ m $ 个硬币，你可以取出任何类型为 $ (*,~a_i) $ 的机器并将其移动到链中的任何位置。 如果移动的总成本不超过 $ b $ 个硬币，问最终产品可以达到的最大价值是多少？ **输入输出格式**： **输入格式**： 第一行包含四个整数 $ n $, $ b $, $ p $ 和 $ m $（$ 1 \le n \le 10^6 $, $ 1 \le b, p, m \le 10^9 $）——工厂中的机器数量、你的预算和两种类型机器的移动成本。 接下来的 $ n $ 行包含对机器的描述。描述以以下字符之一开始："+" 或 "\*"，表示机器的类型。然后是一个整数 $ a_i $（$ 1 \le a_i \le 2 \cdot 10^9 $）。 保证当前结果产品的价值不超过 $ 2 \cdot 10^9 $。 **输出格式**： 打印一个整数——如果移动的总成本不超过 $ b $ 个硬币，可以实现的最终产品的最大价值。 **输入输出样例**： **输入样例 #1**： ``` 3 2 1 3 * 2 + 1 + 1 ``` **输出样例 #1**： ``` 6 ``` **输入样例 #2**： ``` 4 2 2 2 * 2 + 1 * 3 + 2 ``` **输出样例 #2**： ``` 21 ``` **输入样例 #3**： ``` 8 2 1 1 * 2 + 1 * 4 + 1 + 1 + 1 * 5 + 3 ``` **输出样例 #3**： ``` 240 ``` **说明**： 在第一个示例中，我们的预算太低，无法移动 $ (*,~2) $ 机器，但我们可以将两个 $ (+,~1) $ 机器都移动到链的开始。所以最终的链将是 $ (+,~1) $ $ (+,~1) $ $ (*,~2) $。如果价值为 $ 1 $ 的工作件被供应到第一台机器，其价值将按以下方式改变：$ 1, 2, 3, 6 $。 在第二个示例中，我们只能移动一台机器。让我们将 $ (+,~2) $ 机器移动到链的开始。最终的链将是 $ (+,~2) $ $ (*,~2) $ $ (+,~1)