結果
問題 |
No.2370 He ate many cakes
|
ユーザー |
![]() |
提出日時 | 2023-07-14 10:01:59 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 1,172 bytes |
コンパイル時間 | 1,669 ms |
コンパイル使用メモリ | 110,808 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 18:55:43 |
合計ジャッジ時間 | 2,372 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
#include <algorithm> #include <iostream> #include <vector> using namespace std; using lint = long long; vector<lint> gen(const vector<int> &vec) { vector<lint> ret; ret.reserve(1 << vec.size()); auto rec = [&](auto &&self, int now, lint sum) -> void { if (now == (int)vec.size()) { ret.push_back(sum); return; } self(self, now + 1, sum); self(self, now + 1, sum + vec.at(now)); }; rec(rec, 0, 0); return ret; } int main() { int N, K; cin >> N >> K; vector<int> A(N); for (auto &x : A) cin >> x; const int L = N / 2; auto left = gen(vector<int>(A.begin(), A.begin() + L)); sort(left.rbegin(), left.rend()); auto right = gen(vector<int>(A.begin() + L, A.end())); sort(right.begin(), right.end()); lint ok = -1e9 * 30, ng = 1e9 * 30 + 10; while (ng > ok + 1) { const lint c = (ok + ng) / 2; int cntr = 0; for (lint v : left) { cntr += right.cend() - lower_bound(right.cbegin(), right.cend(), c - v); if (cntr >= K) break; } (cntr >= K ? ok : ng) = c; } cout << ok << '\n'; }