#include
using namespace std;
bool validconfig(int books[],int n,int m,int ans)
{
int students=1;
int current_pages=0;
for(int i=0;i<n;i++)
{
if(current_pages+books[i]>ans)
{
current_pages=books[i];
students++;
if(students>m)
{
return false;
}
}
else
{
current_pages+=books[i];
}
}
return true;
}
int binarysearchbooks(int books[],int n,int m)
{
int total_pages=0;
int s=0,e=0;
for(int i=0;i<n;i++)
{
total_pages+=books[i];
s=max(s,books[i]);
}
e=total_pages;
int final_ans=0;
while(s<=e)
{
int mid=(s+e)/2;
if(validconfig(books,n,m,mid))
{
final_ans=mid;
e=mid-1;
}
else
{
s=mid+1;
}
}
return final_ans;
}
int main() {
int t;
cin>>t;
while(t>0)
{
int n,m;
cin>>n>>m;
int books[100];
for(int i=0;i<n;i++)
{
cin>>books[i];
}
cout<<binarysearchbooks(books,n,m)<<endl;
}
return 0;
}
gives
timelimit error
