题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1044
咳咳...终于A了...
居然没注意到正着找pos是n方会TLE...所以要倒着找pos；
二分还写错了，改了半天...
小心前缀和取模后相减变成负数！！！！！！！！！
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxn=,mod=;
int n,m,a[maxn],s[maxn][],f[maxn][],ans,mn,sum,l,r,pos[maxn];
bool pd(int x)
{
int s=,cnt=;
for(int i=;i<=n;i++)
{
if(s+a[i]>x)
{
cnt++;
s=;
}
s+=a[i];
}
return cnt<=m;//m!!
return ;
}
void solve1()
{
r=s[n][];
int mid=(l+r)>>;
while (l<=r)
{
if (pd(mid)) mn=mid,r=mid-;
else l=mid+;
mid=(l+r)>>;
}
}
void solve2()
{
for(int i=;i<=n;i++)
{
if(s[i][]<=mn)f[i][]=;
else break;
}
for (int i=;i<=n;i++)
{
if (s[i][]<=mn) continue;
for (int j=i-;j>=;j--)
if (s[i][]-s[j][]>mn) {pos[i]=j+;break;}
// for(int j=0;j<i;j++)
// if(s[i][0]-s[j][0]<=mn){pos[i]=j;break;}//TLE!!!(n方)
}
bool x=;
while(m--)
{
for(int i=;i<=n;i++)
s[i][x]=(s[i-][x]+f[i][x])%mod;//
x=!x;
for(int i=;i<=n;i++)
f[i][x]=(s[i-][!x]-s[max(pos[i]-,)][!x]+mod)%mod;//i-1! //pos[i]-1! //mod后小心负数！！！！！
(ans+=f[n][x])%=mod;
}
printf("%d %d",mn,ans);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&a[i]),s[i][]=s[i-][]+a[i],l=max(l,a[i]);
solve1();
solve2();
return ;
}