問題一覧 > 通常問題

No.2370 He ate many cakes

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 44
作問者 : meruuu61779999 / テスター : Moss_Local
お気に入りにしたユーザー ProblemId : 9821 / 自分の提出
問題文最終更新日: 2023-07-02 23:26:31
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

There are $N$ cakes. The deliciousness of each cake is $A_i$.
Hashimoto-kun has decided to choose any number of cakes, between $0$ and $N$ inclusive, from the $N$ cakes and eat them.
The sum of the deliciousness of the eaten cakes is called his "happiness".
There are $2^N$ ways in total for Hashimoto-kun to choose the cakes. Compute the "happiness" for all of these ways and arrange the values in descending order, then output the $K$-th largest value of "happiness".

Input

$N\ K$
$A_1\ A_2\ \dots\ A_n$

  • All inputs are integers.
  • $1 \leq N \leq 30$
  • $-10^9 \leq A_i \leq 10^9$
  • $1 \leq K \leq min(2^N,3 \times 10^5)$

Output

Output the answer.

Sample

Sample 1
Input
3 3
1 2 4
Output
5

Arranging the happiness values in descending order gives $(7,6,5,4,3,2,1,0)$. The $3$-rd value is $5$, so output $5$.

Sample 2
Input
4 12
5 10 17 -30
Output
-13

The deliciousness of a cake can also be negative.

Sample 3
Input
2 3
52 52
Output
52

Arranging the happiness values in descending order gives $(104,52,52,0)$. The same value may appear multiple times as a happiness value.

Sample 4
Input
30 114628 
-883998379 -262426887 800367560 54764647 357134302 -469610314 -195910116 -299288300 497120222 -220346258 665395688 -991188757 595751965 -816604952 -452538161 426555901 151762142 117710615 666589834 719459526 -558091631 45363939 34336882 69352512 669913093 949490131 -191526596 -424517738 -179498703 825646919
Output
5958092367

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。