結果
問題 |
No.2370 He ate many cakes
|
ユーザー |
![]() |
提出日時 | 2023-10-17 19:18:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 1,206 bytes |
コンパイル時間 | 1,442 ms |
コンパイル使用メモリ | 128,380 KB |
最終ジャッジ日時 | 2025-02-17 08:14:00 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cstring> #include<cassert> #include<cmath> #include<ctime> #include<iomanip> #include<numeric> #include<stack> #include<queue> #include<map> #include<unordered_map> #include<set> #include<unordered_set> #include<bitset> #include<random> using namespace std; int N,K,A[30]; void solve() { cin >> N >> K; for(int i = 0;i < N;i++) cin >> A[i]; vector<long long> D,U; for(int i = 0;i < 1 << N/2;i++) { long long s = 0; for(int j = 0;j < N/2;j++) if(i >> j & 1) s += A[j]; D.push_back(s); } for(int i = 0;i < 1 << N-N/2;i++) { long long s = 0; for(int j = 0;j < N-N/2;j++) if(i >> j & 1) s += A[j+N/2]; U.push_back(s); } sort(D.begin(),D.end(),greater<long long>()); sort(U.begin(),U.end()); long long ok = -2e18,ng = 2e18; while(ng-ok > 1) { long long mid = (ok+ng)/2; long long cnt = 0; int id = 0; for(int i = 0;i < (int)D.size();i++) { while(id < (int)U.size() && D[i]+U[id] < mid) id++; cnt += (int)U.size()-id; } if(cnt >= K) ok = mid; else ng = mid; } cout << ok << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; //cin >> tt; while(tt--) solve(); }