#P5985. [PA 2019] Muzyka pop
[PA 2019] Muzyka pop
题目描述
给定 个整数 ,请找到 个非负整数 ,使得 的值最大,其中 为 在二进制下的 的个数。
你找到的这 个非负整数 需要满足 。
输入格式
第一行两个整数 。
第二行包含 个整数 。
输出格式
输出一行一个整数,即 的最大值。
提示
对于 的数据,,,。
解释:
,则答案为 。
给定 n 个整数 a1..n,请找到 n 个非负整数 b1..n,使得 a1×f(b1)+a2×f(b2)+...+an×f(bn) 的值最大,其中 f(x) 为 x 在二进制下的 1 的个数。
你找到的这 n 个非负整数 b1..n 需要满足 0≤b1<b2<...<bn≤m。
第一行两个整数 n,m。
第二行包含 n 个整数 a1,a2,...,an。
输出一行一个整数,即 a1×f(b1)+a2×f(b2)+...+an×f(bn) 的最大值。
对于 100% 的数据,1≤n≤200,n−1≤m≤1018,∣ai∣≤1014。
b1=3,b2=4,b3=5,则答案为 2×2+(−1)×1+3×2=9。