[C++] syntaxhighlighter_viewsource syntaxhighlighter_copycode
#include<iostream>
#include<cstdio>
#define LL long long
#define mod 10007
using namespace std;
LL n,m,maxn;
LL A[50005],B[50005],C[50005],F[50005][2],Sum[50005][2];
LL R(){
LL sum=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9')sum=sum*10+ch-'0',ch=getchar();
return sum;
}
bool Love(LL x){
LL sum=0,t=0;
for(int i=1;i<=n;i++){
if(sum+A>x){
t++;
sum=A;
}
else sum+=A;
}
return t<=m;
}
int main(){
LL mid,l=0,r=0,ans=0;
cin>>n>>m;
for(int i=1;i<=n;i++)A=R(),B=B[i-1]+A,l=max(l,A);
r=B[n];
while(l<=r){
mid=(l+r)/2;
if(Love(mid))maxn=mid,r=mid-1;
else l=mid+1;
}
for(int i=1;i<=n;i++){
C=lower_bound(B+1,B+1+i,B-maxn)-B;
C--;
}
for(int i=1;i<=n;i++){
if(B<=maxn)Sum[0]=i;
else Sum[0]=Sum[i-1][0];
}
for(int j=1;j<=m;j++){
for(int i=j+1;i<=n;i++){
F[j&1]=((Sum[i-1][(j-1)&1]-Sum[C][(j-1)&1])%mod+mod)%mod;
Sum[j&1]=(Sum[i-1][j&1]+F[j&1])%mod;
}
ans=(ans+F[n][j&1])%mod;
}
cout<<maxn<<" "<<ans;
}