結果
問題 | No.817 Coin donation |
ユーザー |
![]() |
提出日時 | 2019-04-19 21:52:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 1,067 bytes |
コンパイル時間 | 1,960 ms |
コンパイル使用メモリ | 199,020 KB |
最終ジャッジ日時 | 2025-01-07 02:41:31 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 14 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:14:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 14 | scanf("%d%d", &N, &K); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:16:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 16 | for (auto& e: AB) scanf("%lld%lld", &e.first, &e.second); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using pll = std::pair<long long, long long>; std::vector<pll> AB; int N, K; // 引数より小さい物<kならtrue bool lower_fewer(long long); bool exist(long long); int main() { scanf("%d%d", &N, &K); AB.resize(N); for (auto& e: AB) scanf("%lld%lld", &e.first, &e.second); std::sort(AB.begin(), AB.end(), [](const auto& a, const auto& b) { return a.second < b.second; } ); long long left{1}, right{1LL << 30}; while (left + 1 < right) { long long mid{(left + right) / 2}; if (lower_fewer(mid)) left = mid; else right = mid; } if (exist(left)) printf("%lld\n", left); else printf("%lld\n", std::lower_bound(AB.begin(), AB.end(), pll(left, 0))->first); return 0; } bool lower_fewer(long long num) { long long sum{}; for (auto& e: AB) { if (num <= e.first) continue; if (e.second < num) sum += e.second + 1 - e.first; else sum += num - e.first; } return sum < K; } bool exist(long long candidate) { for (auto& e: AB) if (e.first <= candidate && candidate <= e.second) return true; return false; }