結果
問題 |
No.2370 He ate many cakes
|
ユーザー |
![]() |
提出日時 | 2024-06-26 10:25:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,288 bytes |
コンパイル時間 | 867 ms |
コンパイル使用メモリ | 71,992 KB |
最終ジャッジ日時 | 2025-02-22 00:37:06 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 12 TLE * 4 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:36:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 36 | scanf("%d%d", &n, &k); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:37:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 37 | 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; /* 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); int nbits = 1 << n, bits0 = 0; ll sum0 = 0; for (int i = 0; i < n; i++) if (as[i] >= 0) { bits0 |= (1 << i); sum0 += as[i]; } 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; q.insert({sum1, bits1}); used.insert(bits1); } while (q.size() > k - c) q.erase(q.begin()); } printf("%lld\n", sumk); return 0; }