I tried converting all int to long long but still i failed 3 test cases. Also I’m not getting the share-able link in the online coding blocks IDE.
//Painters partition
#include
#include
using namespace std;
bool checkpainter(long long arr[], long long n, long long k, long long mid){
long long count=1;
long long max=0;
for(int i=0;i<n;i++){
if(max+arr[i]<=mid){
max+=arr[i];
}else{
max=arr[i];
count++;
}
}
if(count==k){
return true;
}else{
return false;
}
}
int main(){
long long k,n;
cin>>k>>n;
long long arr[n];
long long end=0;
long long start=0;
for(int i=0;i<n;i++){
cin>>arr[i];
end+=arr[i];
start=max(start,arr[i]);
}
long long ans=end;
while(start<=end){
long long mid=(start+end)/2;
if(checkpainter(arr,n,k,mid)){
ans=min(ans,mid);
end=mid-1;
}else{
start=mid+1;
}
}
cout<<ans<<endl;
return 0;
}