CF1111C.Creative Snap
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Thanos wants to destroy the avengers base, but he needs to destroy the avengers along with their base.
Let we represent their base with an array, where each position can be occupied by many avengers, but one avenger can occupy only one position. Length of their base is a perfect power of 2 . Thanos wants to destroy the base using minimum power. He starts with the whole base and in one step he can do either of following:
- if the current length is at least 2 , divide the base into 2 equal halves and destroy them separately, or
- burn the current base. If it contains no avenger in it, it takes A amount of power, otherwise it takes his B⋅na⋅l amount of power, where na is the number of avengers and l is the length of the current base.
Output the minimum power needed by Thanos to destroy the avengers' base.
输入格式
The first line contains four integers n , k , A and B ( 1≤n≤30 , 1≤k≤105 , 1≤A,B≤104 ), where 2n is the length of the base, k is the number of avengers and A and B are the constants explained in the question.
The second line contains k integers a1,a2,a3,…,ak ( 1≤ai≤2n ), where ai represents the position of avenger in the base.
输出格式
Output one integer — the minimum power needed to destroy the avengers base.
输入输出样例
输入#1
2 2 1 2 1 3
输出#1
6
输入#2
3 2 1 2 1 7
输出#2
8
说明/提示
Consider the first example.
One option for Thanos is to burn the whole base 1−4 with power 2⋅2⋅4=16 .
Otherwise he can divide the base into two parts 1−2 and 3−4 .
For base 1−2 , he can either burn it with power 2⋅1⋅2=4 or divide it into 2 parts 1−1 and 2−2 .
For base 1−1 , he can burn it with power 2⋅1⋅1=2 . For 2−2 , he can destroy it with power 1 , as there are no avengers. So, the total power for destroying 1−2 is 2+1=3 , which is less than 4 .
Similarly, he needs 3 power to destroy 3−4 . The total minimum power needed is 6 .