I am applying the same logic as used in BOOK ALLOCATION problem for this problem too, as it is much similar to the former but on submission, no case is passed giving the wrong answer.
can someone help?
code
#include<bits/stdc++.h>
#define MOD 10000003
typedef unsigned long long int ll;
using namespace std;
bool isValid(ll a[],ll n,ll m,ll ans)
{
int painters=1,current_boards=0;
for(int i=0;i<n;i++)
{
if(current_boards+a[i]>ans)
{
current_boards=a[i];painters++;
if(painters>m)return false;
}
else{current_boards+=a[i];}
}
return true;
}
int painter_allocation(ll a[],ll n,ll m)
{
int s=a[n-1],e=0;
for(ll i=0;i<n;i++)e+=a[i];
int ans=0;
while(s<=e)
{
ll mid=(s+e)/2;
if(isValid(a,n,m,mid))
{
e=mid-1;
ans=mid;
}
else
{
s=mid+1;
}
}
return ans%MOD;
}
int main() {
ll n,k,t;
cin>>n>>k>>t;
ll a[100006];
for(ll i=0;i<n;i++)cin>>a[i];
ll final_ans=painter_allocation(a,n,k);
cout<<(final_ans*t)%MOD<<endl;
}
