#PU839. USACO 2018 US Open Contest, Gold — Problem 3. Talent Show

    ID: 1597 传统题 文件IO:talent 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:open18来源:usaco.orgscoring:equal_test_cases枚举双指针

USACO 2018 US Open Contest, Gold — Problem 3. Talent Show

USACO 2018 US Open Contest, Gold — Problem 3. Talent Show

题目描述

Farmer John is bringing his NN cows, conveniently numbered 1…N1 \ldots N, to the county fair, to compete in the annual bovine talent show! His iith cow has a weight wiw_i and talent level tit_i, both integers. Upon arrival, Farmer John is quite surprised by the new rules for this year's talent show: (i) A group of cows of total weight at least WW must be entered into the show (in order to ensure strong teams of cows are competing, not just strong individuals), and (ii) The group with the largest ratio of total talent to total weight shall win. FJ observes that all of his cows together have weight at least WW, so he should be able to enter a team satisfying (i). Help him determine the optimal ratio of talent to weight he can achieve for any such team.

输入格式

The first line of input contains NN (1≤N≤2501 \leq N \leq 250) and WW (1≤W≤10001 \leq W \leq 1000). The next NN lines each describe a cow using two integers wiw_i (1≤wi≤1061 \leq w_i \leq 10^6) and tit_i (1≤ti≤1031 \leq t_i \leq 10^3).

输出格式

Please determine the largest possible ratio of total talent over total weight Farmer John can achieve using a group of cows of total weight at least WW. If your answer is AA, please print out the floor of 1000A1000A in order to keep the

数据范围

(见题面原文)

样例

样例 1

3 15
20 21
10 11
30 31
1066
In this example, the best talent-to-weight ratio overall would be to use just
the single cow with talent 11 and weight 10, but since we need at least  15
units of weight, the optimal solution ends up being to use this cow plus the cow
with talent 21 and weight 20.  This gives a talent-to-weight ratio of
(11+21)/(10+20) = 32/30 = 1.0666666..., which when multiplied by 1000 and
floored gives 1066.
Problem credits: Brian Dean