Please correct my code, it cant pass through the 3rd and 4th testcase

#include
#include
using namespace std;
int check(int a[],int n,int k,int t,int mid){
int sum=0,painter=1;
for(int i=0;i<n;i++){
sum+=a[i];
if(sum>mid){
sum=a[i];
painter++;
}
}
return painter;
}
int main() {
int n,k,t;
cin>>n>>k>>t;
int a[n],sum=0,mini=INT_MIN;
for(int i=0;i<n;i++){
cin>>a[i];
mini=max(mini,a[i]);
sum+=a[i];
}
int s=mini,e=sum,mid,ans=-1;
while(s<=e){
mid=(s+e)/2;
if(k>=check(a,n,k,t,mid)){
ans=mid;
e=mid-1;
}
else s=mid+1;
}
int z= (ans*t) % 10000003;
cout<<z<<endl;
return 0;
}