有n根木棍,第i根木棍的长度为Li,n根木棍依次连接到了一起,总共有n-1个连接处.现在允许你最多砍断m个连接处,砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小，求此长度以及满足此长度下的分割方案总数，并将方案结果mod 10007。

（2≤n≤50000, 0≤m≤min(n-1,1000)，1≤Li≤1000，内存限制为128MB）

输入: 第1行是两个整数n,m，分别表示木棍的数量和允许砍断连接处的数量。

第2行是n个正整数a1, a2, ..., an，其中ai表示第i跟木棍的长度。

输出: 一行两个空格间隔的整数，即将n根木棍分成多段后,满足总长度最大的一段长度最小,输出此长度以及满足此长度的所有分割方案总数mod 10007的结果。

输入样例1: 3 2 1 1 10

输出样例1: 10 2

输入样例2: 5 2 1 2 3 4 5

输出样例2: 6 1

用时/内存: 1000MS/128MB

#include <bits/stdc++.h>
using namespace std;

const int MOD = 10007;
int n, m, a[50005], ans1, ans2, now;
int sum1[50005], sum2[50005], lef[50005], f[50005];

bool check(int x) {
    int len = 0, num = 1;
    for (int i = 1; i <= n; i++) { 
        if (a[i] > x) return false; // 如果单根木棍超过 x，直接返回 false
        len += a[i]; 
        if (len > x) {
            num++; // 需要增加一段
            len = a[i]; // 当前段重新开始
        }
    }
    return num <= m; // 判断切割段数是否超出 m
}

int main() {
    cin >> n >> m;
    m++; // 允许的切割次数加1
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int l = 1, r = 50000000; // 二分搜索的范围
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans1 = mid; // 记录当前可行的最大值
            r = mid - 1; // 尝试更大的长度
        } else {
            l = mid + 1; // 尝试更小的长度
        }
    }
    
    cout << ans1 << " "; // 输出最大的一段长度

    // 计算分割方案数
    for (int i = 1; i <= n; i++) {
        sum1[i] = sum1[i - 1] + a[i];
        while (sum1[i] - sum1[now] > ans1)
            now++;
        lef[i] = now; // 记录第i根木棍的前一段的最左端点
    }
    for (int i = 1; i <= n; i++) {
        if (sum1[i] <= ans1)
            f[i] = 1; // 不分割的方案数
        sum2[i] = (sum2[i - 1] + f[i]) % MOD; // 计算前缀和
    }

    for (int j = 2; j <= m; j++) { // 前 i 根木棍分割为 j 段
        for (int i = 1; i <= n; i++) {
            if (lef[i] > 0)
                f[i] = (sum2[i - 1] - sum2[lef[i] - 1] + MOD) % MOD; // 使用前缀和更新方案数
            else
                f[i] = sum2[i - 1]; // 如果没有可分割的段
        }
        // 更新前缀和
        for (int i = 1; i <= n; i++) {
            sum2[i] = (sum2[i - 1] + f[i]) % MOD; // 更新前缀和
            ans2 = (ans2 + f[n]) % MOD;// 方案数即为最后一个位置的方案数
        }
    }

    
    cout << ans2 << endl; // 输出方案数

    return 0;
}