問題一覧 > 通常問題

No.2370 He ate many cakes

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 44
作問者 : meruuu61779999meruuu61779999 / テスター : Moss_LocalMoss_Local
1 ProblemId : 9821 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。