对于第一个询问显然二分，对于第二个询问 dp 求解。

暴力代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5,M=1e3+5;
const int mod=1e4+7;
int n,m,a[N],sum[N];
int f[N][M];
bool check(int mid){
	int sum=0,cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]>mid)return 0;
		if(a[i]+sum<=mid)sum=sum+a[i];
		else{
			sum=a[i];
			cnt++;
		}
	}
	cnt++;
	return cnt<=m;
}
int main(){
	scanf("%d%d",&n,&m);
	m++;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	int l=0,r=sum[n],ans;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	printf("%d ",ans);
	for(int i=1;i<=n;i++){
		if(sum[i]<=ans){
			f[i][1]=1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=2;j<=m;j++){
			for(int k=0;k<i;k++){
				if(sum[i]-sum[k]<=ans){
					f[i][j]=(f[i][j]+f[k][j-1])%mod;
				}
			}
		}
	}
	int res=0;
	for(int i=0;i<=m;i++){
		res=res+f[n][i];
	}
	printf("%d",res);
	return 0;
}

AC 代码 1，没加预处理 $now$。

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5,M=1e3+5;
const int mod=1e4+7;
int n,m,a[N],sum[N];
int f[N][2],g[N][2];
bool check(int mid){
	int sum=0,cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]>mid)return 0;
		if(a[i]+sum<=mid)sum=sum+a[i];
		else{
			sum=a[i];
			cnt++;
		}
	}
	cnt++;
	return cnt<=m;
}
int main(){
	scanf("%d%d",&n,&m);
	m++;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	int l=0,r=sum[n],ans;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	printf("%d ",ans);
	for(int i=1;i<=n;i++){
		if(sum[i]<=ans){
			f[i][1]=1;
		}
	}
	for(int i=1;i<=n;i++){
		g[i][1]=(g[i-1][1]+f[i][1])%mod;
	}
	int now,res=f[n][1];
	for(int j=2;j<=m;j++){
		now=0;
		for(int i=1;i<=n;i++){
			while(sum[i]-sum[now]>ans){
				now++;
			}
			f[i][j&1]=(g[i-1][j-1&1]-g[now-1][j-1&1]+mod)%mod;
			g[i][j&1]=(g[i-1][j&1]+f[i][j&1])%mod;
		}
		res=(res+f[n][j&1])%mod;
	}
	printf("%d",res);
	return 0;
}

AC 代码 2，加了预处理 $now$。

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5,M=1e3+5;
const int mod=1e4+7;
int n,m,a[N],sum[N];
int f[N][2],g[N][2],ed[N];
bool check(int mid){
	int sum=0,cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]>mid)return 0;
		if(a[i]+sum<=mid)sum=sum+a[i];
		else{
			sum=a[i];
			cnt++;
		}
	}
	cnt++;
	return cnt<=m;
}
int main(){
	scanf("%d%d",&n,&m);
	m++;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	int l=0,r=sum[n],ans;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	printf("%d ",ans);
	for(int i=1;i<=n;i++){
		if(sum[i]<=ans){
			f[i][1]=1;
		}
		g[i][1]=(g[i-1][1]+f[i][1])%mod;
	}
	int j=0;
	for(int i=1;i<=n;i++){
		for(;j<i;j++){
			if(sum[i]-sum[j]<=ans){
				ed[i]=j;
				break;
			}
		}
	}
	int res=f[n][1];
	for(int j=2;j<=m;j++){
		for(int i=1;i<=n;i++){
			f[i][j&1]=(g[i-1][j-1&1]-g[ed[i]-1][j-1&1]+mod)%mod;
			g[i][j&1]=(g[i-1][j&1]+f[i][j&1])%mod;
		}
		res=(res+f[n][j&1])%mod;
	}
	printf("%d",res);
	return 0;
}