[河南省队2012]珍贵的项链

Grade Open Time Friday, 19 September 2014, 10:06 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:06 am
Allow late Yes Close Time Friday, 26 September 2014, 10:06 am
Input file dividenecklace.in Output file dividenecklace.out

2.珍贵的项链

  (dividenecklace.pas/c/cpp)

【问题描述】

         有一个电影的主人公(假设叫The Best Killer)走在路上,突然冥王(同样也是财富之神)Hades出现在他面前,给他了一个长为N的环形项链,这个项链由一条金丝把各种稀有之物串接起来,可以理解为,项链串接了从1N个物品,每个物品拥有一个价值整数Wi,每一个物品占用一个单位,让从中选取K段宝物(不能重叠,但可以每段可以挨着),使得总价值超过Limit,如果超过Limit那么Hades就把他的宝座让给TBK,否则TBK就要和Hades一起去地下了,这时候,正在看电影的你立刻暂停了播放,预算TBK是否要被带走.

【输入】

三个整数N表示项链上有N个物品,第二个整数K表示分成K,第三个整数Limit含义见题目描述

第二行N个整数表示该物品的价值Wi

【输出】

第一行一个字符串,要么是”Go To the Hell”表示无法找到选取方式使得总价值超过Limit,要么是 New Pluto was born表示超过了Limit

如果第一行输出了” New Pluto was born”那么下一行输出TBK能取到的最大的价值.

【输入输出样例1

dividenecklace.in

dividenecklace.out

10 3 1

1 3 -5 4 -5 4 -5 3 1 -2

New Pluto was born

14

【数据范围】

10%数据N<=10        K<=10

40%数据N<=103          K<=10

50%数据N<=104          K<=10

100%数据N<=106       K<=10

其中有40%的数据K=1

100%数据所有数字均不超过263