No.2370 He ate many cakes
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 44
作問者 : meruuu61779999 / テスター : Moss_Local
タグ : / 解いたユーザー数 44
作問者 : meruuu61779999 / テスター : Moss_Local
問題文最終更新日: 2023-07-02 23:26:31
問題文
ケーキが $N$ 個あります。それぞれのおいしさは $A_i$ です。
はしもとくんは $N$ 個のケーキの中から $0$ 個以上 $N$ 個以下の任意の個数のケーキを選んで食べることにしました。
食べたケーキのおいしさの総和を「嬉しさ」とします。
はしもとくんのケーキの選び方は全部で $2^N$ 通りあります。これらすべてについて「嬉しさ」を求めて大きいものから順に並べたとき、「嬉しさ」の大きい方から $K$ 番目の値を出力してください。
入力
$N\ K$ $A_1\ A_2\ \dots\ A_n$
- 入力はすべて整数
- $1 \leq N \leq 30$
- $-10^9 \leq A_i \leq 10^9$
- $1 \leq K \leq min(2^N,3 \times 10^5)$
出力
答えを出力してください。
サンプル
サンプル1
入力
3 3 1 2 4
出力
5
嬉しさを大きいものから順に並べると、$(7,6,5,4,3,2,1,0)$ になります。 $3$ 番目の値は $5$ なので、 $5$ を出力します。
サンプル2
入力
4 12 5 10 17 -30
出力
-13
ケーキのおいしさは負の値も取ります。
サンプル3
入力
2 3 52 52
出力
52
嬉しさを大きいものから順に並べると、$(104,52,52,0)$ になります。嬉しさとして同じ値が複数回現れることもあります。
サンプル4
入力
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
出力
5958092367
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。