TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3603
  • 题目
  • P3603服药
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    你最近老是犯傻,有脑残的趋势,药铺何老板给你开了K天的药,希望能治好你的顽疾。
    一共有n颗药,编号1到n,你需要按1到n的顺序用K天服完这些药。服药后会产生有益大脑的药效,开始时药效为0,当你吃掉第i颗药,药效会增加Ai,当你晚上睡觉的时候,药效会减半。也就是说,如果昨晚睡觉前的药效是23,那么今天早上醒来时就剩11了(舍去掉小数位)。你在每天早晨吃药,每次可以吃任意多颗药,但何老板希望这K天中,药效最小的那一天(白天)的药效尽可能大,请你求出这个药效值。
    例如,一共有5颗药,何老板要求你用5天吃完,编号1到5的药效分别是10,40,13,22,7,则最佳方案如下图所示:

    5天内最小药效为24,这是所有方案中最大的。

    输入格式

    第一行,两个整数N和K。
    接下来有N行,每行一个整数,其中第i行的数Ai表示第i颗药的药效。

    输出格式

    一行,一个整数,表示K天内药效最小那天的最大值。

    样例输入

    样例输入1:
    5 5
    10 
    40 
    13 
    22 
    7

    样例输入2:
    5 10
    14
    17
    28
    26
    24

    样例输出

    样例输出1:
    24

    样例输出2:
    8

    提示

    对于30%的数据: 1≤N,K≤100 1≤Ai≤100
    对于100%的数据:1≤N,K≤50000 1≤Ai≤1000000


    来源  改编自[Usaco2010]Chocolate Eating