Description：

将 $n$ 个木棍分成 $m+1$ 段，使得长度最大的一段长度最小，输出最大长度和方案数。

$1\le n \le 50000$ $1\le m \le 1000$

Solution：

第一问二分即可，第二问 $f[i][j]$ 表示前 $i$ 个分 $j$ 段每段都不超过 $maxl$ 的方案数，不难想到转移为 $\begin{align}f[i][j]=\sum_{\sum_{p=k+1}^i l[p]\le maxl} f[k][j-1]\end{align}$ 但转移是 $N^2 M$ 的，对于求和式绝大部分情况是前缀和优化，发现能优化的地方只有 $k$ 与状态中的 $i$ 和 $j$ 无关，于是肯定是前缀和 $k$ ，发现对于固定的 $i$ ， $k$ 能取到的最靠前的点是一定的，于是将这个位置预处理出来，每次直接加前缀和就可以做到 $O(NM)$ 了，但是这样空间复杂度很不优美，于是将 $dp$ 数组和前缀和数组 $j$ 维滚动一下即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 10007

int n,m;

#define MAXN 50010

#define MAXM 1010

int l[MAXN];

int sum[MAXN];

int ans1 = 0,ans2 = 0;

inline bool check(int k)

{

    register int d = 1,total = 0;

    for(register int i = 1;i <= n;++i)

    {

        if(l[i] > k)return false;

        if(total + l[i] > k)

        {

            ++d;

            if(d > m)return false;

            total = l[i];

        }

        else total += l[i];

    }

    return (d <= m);

}

inline void work1()

{

    register int l = 1,r = sum[n],mid;

    while(l < r)

    {

        mid = ((l + r) >> 1);

        if(check(mid))r = mid;

        else l = mid + 1;

    }

    printf("%d ",(ans1 = l));

    return;

}

int st[MAXN];

int f[2][MAXN];

int s[2][MAXN];

void work2()

{

    register int cur = 0;

    for(register int i = 1;i <= n;++i)

    {

        st[i] = i - 1;

        for(;sum[i] - sum[st[i] - 1] <= ans1 && st[i] >= 1;--st[i]);

    }

    ans2 = 0;

    for(register int i = 1;i <= n;++i)s[cur][i] = s[cur][i - 1] + (sum[i] <= ans1);

    for(register int j = 2;j <= m;++j)

    {

        cur ^= 1;

        for(register int i = 1;i <= n;++i)

        {

        	f[cur][i] = s[cur ^ 1][i - 1];

        	if(st[i] >= 1)f[cur][i] = (f[cur][i] - s[cur ^ 1][st[i] - 1] + MOD) % MOD;

            s[cur][i] = (s[cur][i - 1] + f[cur][i]) % MOD;

        }

        ans2 = (ans2 + f[cur][n]) % MOD;

    }

    printf("%d\n",ans2);

    return;

}

inline int read()

{

    register int res = 0;

    register char c = getchar();

    while(!isdigit(c))c = getchar();

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res;

}

int main()

{

    n = read();m = read();

    ++m;

    for(register int i = 1;i <= n;++i)

    {

        l[i] = read();

        sum[i] = sum[i - 1] + l[i];

    }

    work1();

    work2();

    return 0;

}