結果
問題 |
No.2370 He ate many cakes
|
ユーザー |
![]() |
提出日時 | 2024-06-26 13:17:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 1,390 bytes |
コンパイル時間 | 749 ms |
コンパイル使用メモリ | 74,200 KB |
最終ジャッジ日時 | 2025-02-22 00:37:33 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
コンパイルメッセージ
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<queue> #include<algorithm> #include<utility> #include<functional> using namespace std; /* constant */ const int MAX_N = 30; const int MAX_M = MAX_N / 2; const int MBITS = 1 << MAX_M; /* typedef */ using ll = long long; using pli = pair<ll,int>; /* global variables */ int as[MAX_N]; ll s0[MBITS], s1[MBITS]; /* subroutines */ /* main */ int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", as + i); int m0 = (n + 1) / 2, m1 = n - m0; int mbits0 = 1 << m0, mbits1 = 1 << m1; s0[0] = 0; for (int bits = 1, msb = 1, msi = 0; bits < mbits0; bits++) { if ((msb << 1) <= bits) msb <<= 1, msi++; s0[bits] = s0[bits ^ msb] + as[msi]; } sort(s0, s0 + mbits0, greater<ll>()); s1[0] = 0; for (int bits = 1, msb = 1, msi = 0; bits < mbits1; bits++) { if ((msb << 1) <= bits) msb <<= 1, msi++; s1[bits] = s1[bits ^ msb] + as[m0 + msi]; } sort(s1, s1 + mbits1, greater<ll>()); priority_queue<pli> q; for (int i = 0; i < mbits0; i++) q.push({s0[i] + s1[0], 0}); int c = 0; ll sk = 0; while (c < k) { auto [s, u] = q.top(); q.pop(); if (++c >= k) { sk = s; break; } if (u + 1 < mbits1) q.push({s - s1[u] + s1[u + 1], u + 1}); } printf("%lld\n", sk); return 0; }