結果

問題 No.817 Coin donation
ユーザー MarcusAureliusAntoninusMarcusAureliusAntoninus
提出日時 2019-04-19 21:52:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 39 ms / 2,000 ms
コード長 1,067 bytes
コンパイル時間 2,238 ms
コンパイル使用メモリ 207,704 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 18:39:27
合計ジャッジ時間 3,151 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 6 ms
6,940 KB
testcase_07 AC 8 ms
6,940 KB
testcase_08 AC 27 ms
6,940 KB
testcase_09 AC 9 ms
6,940 KB
testcase_10 AC 38 ms
6,944 KB
testcase_11 AC 39 ms
6,944 KB
testcase_12 AC 38 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0