레이팅 미적용농부 존은 소들에게 곡예를 시키기로 했다! 먼저 농부 존이 소들의 무게를 재어 보니 서로 다른 무게가 \(N\) (\(1\le N\le 2\cdot 10^5\))가지 있었다. 구체적으로, 각 \(i\in [1,N]\)에 대해 무게가 \(w_i\)인 소가 \(a_i\)마리 있다 (\(1\le a_i\le 10^9, 1\le w_i\le 10^9\)).
가장 인기 있는 묘기는 소들이 균형 잡힌 탑을 만드는 것이다. 탑은 각 소가 다음 소 위에 올라선 소들의 수열이다. 어떤 탑에서, 바로 위에 소가 있는 모든 소의 무게가 바로 위 소의 무게보다 최소 \(K\) (\(1\le K\le 10^9\))만큼 더 크다면 그 탑은 균형 잡힌 탑이다. 각 소는 최대 하나의 균형 잡힌 탑에만 속할 수 있다.
농부 존이 최대 \(M\) (\(1 \le M \le 10^9\))개의 균형 잡힌 탑을 만들려고 할 때, 최대 몇 마리의 소가 어떤 탑에 속할 수 있는가?
문제 제공: Eric Hsu
채점 방식
- 입력 3-5에서는 \(M \leq 5000\)이고 소의 총 마릿수가 \(5000\)을 넘지 않는다.
- 입력 6-11에서는 소의 총 마릿수가 \(2\cdot 10^5\)를 넘지 않는다.
- 입력 12-17은 추가 제약 조건이 없다.
문제 제공: Eric Hsu
첫째 줄에 공백으로 구분된 세 정수 \(N\), \(M\), \(K\)가 주어진다.
다음 \(N\)개의 줄에 공백으로 구분된 두 정수 \(w_{i}\)와 \(a_i\)가 주어진다. 모든 \(w_i\)는 서로 다름이 보장된다.
농부 존이 소들이 탑을 최적으로 만들도록 도울 때, 균형 잡힌 탑에 속하는 소의 최대 마릿수를 출력한다.
3 5 2
9 4
7 6
5 514FJ can create four balanced towers with cows of weights 5, 7, and 9, and one balanced tower with
cows of weights 5 and 7.
3 5 3
5 5
7 6
9 49FJ can create four balanced towers with cows of weights 5 and 9, and one balanced tower with a cow
of weight 7. Alternatively, he can create four balanced towers with cows of weights 5 and
9, and one balanced tower with a cow of weight 5.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > December > Silver