赛时没想到贪心，爆炸了

最大值最小很容易想到二分，用贪心check

然后用dp统计方案数

f[i][j]为前i个树枝分成j份的方案数

$f[i][j] = \sum{f[k][j-1]}$

k需要满足s[i]-s[k]>=ans且k<i

然后我们发现f[i][j]就是在求f[][j-1]中一段的和，可以前缀和优化

然后我们需要优化空间，可以滚动数组把一维压掉

code

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

const int N = 5e4 + 10;

const int M = 1e3 + 10;

int n, m, p, a[N], s[N], f[2][N], g[2][N];

void read(){
	cin >> n >> m >> p; m++;
	for(int i = 1;i <= n; i++) cin >> a[i];
	for(int i = 1;i <= n; i++) s[i] = s[i-1] + a[i];
}

bool check(int x){
	int cnt = 0, sum = 0;
	for(int i = 1;i <= n; i++){
		sum += a[i];
		if(a[i] > x) return 0;
		if(sum > x){
			sum = a[i];
			cnt++;
		}
	}
	if(sum) cnt++;
	return cnt <= m;
}

int w[N];

void compute(){
	int l = 0, r = s[n], ans;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(check(mid)){
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << ans << ' ';
	f[0][0] = 1;
	for(int i = 0;i <= n; i++) g[0][i] = 1;
	int num = 0;
	for(int i = 1;i <= n; i++) w[i] = lower_bound(s,s+1+n,s[i]-ans)-s;
	for(int i = 1;i <= m; i++){
		fill(f[i&1],f[i&1]+m+1,0);
		fill(g[i&1],g[i&1]+m+1,0);
		for(int j = 1;j <= n; j++){
			f[i&1][j] = (g[(i-1)&1][j-1] - g[(i-1)&1][w[j]-1] + p) % p;
			g[i&1][j] = (g[i&1][j-1] + f[i&1][j]) % p;
			if(j == n) num = (f[i&1][j] + num) % p;
		}
	}
	cout << num;
}

int main(){
//	freopen("ex.in","r",stdin);
	read();
	compute();
	return 0;
}