結果
問題 |
No.2370 He ate many cakes
|
ユーザー |
![]() |
提出日時 | 2024-06-26 12:54:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,421 bytes |
コンパイル時間 | 739 ms |
コンパイル使用メモリ | 73,864 KB |
最終ジャッジ日時 | 2025-02-22 00:37:29 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 TLE * 2 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:37:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 37 | scanf("%d%d", &n, &k); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:38:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 38 | for (int i = 0; i < n; i++) scanf("%d", as + i); | ~~~~~^~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 2370.cc: No.2370 He ate many cakes - yukicoder */ #include<cstdio> #include<set> #include<unordered_set> #include<algorithm> #include<utility> using namespace std; /* constant */ const int MAX_N = 30; const int NBITS = 1 << MAX_N; const long long LINF = 1LL << 62; /* typedef */ using ll = long long; using pli = pair<ll,int>; using spli = set<pli>; using usi = unordered_set<int>; /* global variables */ int as[MAX_N]; /* subroutines */ /* main */ int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", as + i); sort(as, as + n); int bits0 = 0, m = 0; ll sum0 = 0; for (int i = 0; i < n; i++) { if (as[i] >= 0) { bits0 |= (1 << i); sum0 += as[i]; } else m++; } spli q; q.insert({sum0, bits0}); usi used; used.insert(bits0); int c = 0; ll sumk = 0; while (c < k && ! q.empty()) { auto sit = q.end(); sit--; auto [s, bits] = *sit; q.erase(sit); if (++c >= k) { sumk = s; break; } for (int i = 0, bi = 1; i < n; i++, bi <<= 1) if (used.find(bits ^ bi) == used.end()) { ll sum1 = s + ((bits & bi) ? -as[i] : as[i]); int bits1 = bits ^ bi; used.insert(bits1); if (q.size() < k - c) q.insert({sum1, bits1}); else if (q.begin()->first < sum1) { q.erase(q.begin()); q.insert({sum1, bits1}); } } } printf("%lld\n", sumk); return 0; }