結果
問題 |
No.2370 He ate many cakes
|
ユーザー |
|
提出日時 | 2023-07-04 10:29:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 1,263 bytes |
コンパイル時間 | 4,067 ms |
コンパイル使用メモリ | 255,956 KB |
最終ジャッジ日時 | 2025-02-15 05:58:31 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
// #define _GLIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; #define rep(i,n) for (ll i = 0; i < (n); ++i) using vl = vector<ll>; using vvl = vector<vl>; using P = pair<ll,ll>; #define pb push_back #define int long long #define double long double #define INF (ll) 3e18 // Ctrl + Shift + B コンパイル // Ctrl + C 中断 // ./m 実行 signed main(){ int n, k; cin >> n >> k; vl a(n); rep(i,n) cin >> a[i]; vl b = {0}; vl c = {0}; rep(i, n/2){ vl newb = b; for(auto x : b) newb.push_back(x+a[i]); b = newb; } for(int i = n/2; i<n; i++){ vl newc = c; for(auto x : c) newc.push_back(x+a[i]); c = newc; } sort(b.begin(), b.end()); sort(c.begin(), c.end()); // for(auto x : b) cout << x << " "; cout << endl; // for(auto x : c) cout << x << " "; cout << endl; int ok = -INF; int ng = INF; while(ng - ok != 1){ int mid = (ok + ng) / 2; // mid以上がk個以上あるか int count = 0; for(auto x : b){ int y = mid - x; count += c.end() - lower_bound(c.begin(),c.end(),y); } // cout << mid << " " << count << endl; if (count >= k) ok = mid; else ng = mid; } cout << ok << endl; }