P3112 [USACO14DEC]后卫马克Guard Mark

    • 280通过
    • 737提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 模拟 贪心 USACO 2014 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB


  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示


    FJ将飞盘抛向身高为H(1 <= H <= 1,000,000,000)的Mark,但是Mark被N(2 <= N <= 20)头牛包围。牛们可以叠成一个牛塔,如果叠好后的高度大于或者等于Mark的高度,那牛们将抢到飞盘。



    Farmer John and his herd are playing frisbee. Bessie throws thefrisbee down the field, but it's going straight to Mark the field handon the other team! Mark has height H (1 <= H <= 1,000,000,000), butthere are N cows on Bessie's team gathered around Mark (2 <= N <= 20).They can only catch the frisbee if they can stack up to be at least ashigh as Mark. Each of the N cows has a height, weight, and strength.A cow's strength indicates the maximum amount of total weight of thecows that can be stacked above her.

    Given these constraints, Bessie wants to know if it is possible forher team to build a tall enough stack to catch the frisbee, and if so,what is the maximum safety factor of such a stack. The safety factorof a stack is the amount of weight that can be added to the top of thestack without exceeding any cow's strength.



    INPUT: (file guard.in)

    The first line of input contains N and H.

    The next N lines of input each describe a cow, giving its height,weight, and strength. All are positive integers at most 1 billion.


    OUTPUT: (file guard.out)

    If Bessie's team can build a stack tall enough to catch the frisbee, please output the maximum achievable safety factor for such a stack.

    Otherwise output "Mark is too tall" (without the quotes).


    输入样例#1: 复制
    4 10 
    9 4 1 
    3 3 5 
    5 5 10 
    4 4 5 
    输出样例#1: 复制