【czy系列赛】czy的后宫6

2014年7月19日1,2750

czy的后宫6

题目描述

众所周知的是丧尸czy有很多妹子(虽然很多但是质量不容乐观QAQ),今天czy把n个妹子排成一行来检阅。但是czy的妹子的质量实在……所以czy看不下去了。检阅了第i个妹子会增加czy a[i]的肾虚值,他打算在检阅过程中最多休息m次(一开始检阅算0次休息,就是说czy最多可以检阅m+1次),每次休息过后czy又会龙精虎猛的继续检阅。问怎样分配才能使得czy在检阅过程中的最大肾虚值最小。

当然这么简单的问题czy早就会做啦……他原来还想算算满足肾虚值最小的条件下有几种方案,但是他太虚了,所以这个问题也交给你啦。你只要输出方案数mod 32123的值即可。

输入格式

第一行输入两个正整数n、m,表示czy的妹子数、最多的休息次数

接下来2到n+1行每行输入一个数a[i],意义见上

输出格式

第一行输出一个数s,表示最小的肾虚值

第二行输出一个数t,表示方案数

样例输入

4 2

3

4

5

2

样例输出

7

3

样例解释

最小的肾虚值为7

分法有3种:34|5|2,34|52,3|4|52

‘|’表示休息

数据范围

有30%的数据,1<=n<=20

另30%的数据,1<=n<=200

另30%的数据,1<=n<=5000,1<=m<=min(n-1,1000),1<=a[i]<=1000

另10%的数据,1<=n<=20000,1<=m<=1000,a[i]只有1、2

保证80%数据随机生成,在计算过程中不会爆int

题解

改编自木棍

第一问二分即可,第二问写出60分的dp然后用个队列优化转移即可