#include
#include
#define ll long long
using namespace std;
bool possible(ll int a[],ll int n,ll int k,ll int t,ll int mid){
ll int time = 0;
ll int painter_used=1;
for(ll int i=0;i<n;i++){
if(time + a[i]>mid){
painter_used++;
time=a[i];
if(painter_used>k)
return false;
}
else
time+=a[i];
}
return true;
}
int main() {
ll int n,k,t,e=0;
cin>>n>>k>>t;
ll int a[100005];
for(ll int i=0;i<n;i++){
cin>>a[i];
e += a[i];
}
ll int s=a[n-1],ans=INT_MAX;
while(s<=e){
ll int mid = (s+e)/2;
if(possible(a,n,k,t,mid)){
ans=min(ans,mid);
e=mid-1;
}
else
s=mid+1;
}
ans = ans*t;
ans=ans%10000003;
cout<<ans<<endl;
return 0;
}
Some one please point out my mistake and help me to correct it.