1048 – Conquering Keokradong

 

Problem Link

#Solution

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
int a[1005];
int n , k,i ;
int ck(int f)
{
int s=0,co=0;
for(i=0;i<=n;i++)
{
if(a[i]>f)
return 1e7;
else if(a[i]+s==f)
{
co++;
s=0;
}
else if(s+a[i]>f)
{
s=a[i];
co++;
}
else s+=a[i];
}
if(s>0)
co++;
return co;
}

int main()
{int t,j=0;
cin>>t;
while(t–)
{
cin>>n>>k;
for(i=0;i<=n;i++)
{
cin>>a[i];

}
int l=0,h=100010,mid,ans;
while(l<=h)
{
mid=(l+h)/2;
if(ck(mid)<=k+1)
{
ans=mid;
h=mid-1;
}
else l=mid+1;

}
printf(“Case %d: %d\n”,++j,ans);
int sum = 0 ;
int c = 0;

for(i=0;i<=n;i++)
{
if(sum+a[i]>ans)
{
printf(“%d\n”,sum); c++;
sum=a[i];

}
else if(sum+a[i]==ans ||n-i==k-c)
{
printf(“%d\n”,sum+a[i]);
c++;
sum=0;
}
else sum+=a[i];
}
}
return 0;
}

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in lightoj, Uncategorized and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s