#PU1350. USACO 2023 December Contest, Silver — Problem 1. Bovine Acrobatics
USACO 2023 December Contest, Silver — Problem 1. Bovine Acrobatics
USACO 2023 December Contest, Silver — Problem 1. Bovine Acrobatics
题目描述
Farmer John has decided to make his cows do some acrobatics! First, FJ weighs his cows and finds that they have () distinct weights. In particular, for each , of his cows have a weight of (). His most popular stunt involves the cows forming balanced towers . A tower is a sequence of cows where each cow is stacked on top of the next. A tower is balanced if every cow with a cow directly above it has weight at least () greater than the weight of the cow directly above it. Any cow can be part of at most one balanced tower. If FJ wants to create at most () balanced towers of cows, at most how many cows can be part of some tower?
输入格式
The first line contains three space-separated integers, , , and . The next lines contain two space-separated integers, and . It is guaranteed that all are distinct.
输出格式
(见题面原文)
数据范围
In inputs 3-5, and the total number of cows does not exceed . In inputs 6-11, the total number of cows does not exceed . Inputs 12-17 have no additional constraints. Problem credits: Eric Hsu
样例
样例 1
3 5 2
9 4
7 6
5 5
14
FJ can create four balanced towers with cows of weights 5, 7, and 9, and one balanced tower with
cows of weights 5 and 7.
样例 2
3 5 3
5 5
7 6
9 4
9
FJ 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.