1048 - Conquering Keokradong

Problem Link

K এর মধ্যে possible এমন  walking distance এর maximum টা বের করতে হবে এবং যা হবে সবচাইতে minimize করা value.
1st Test Case:
4 3
7
------   K = 1
2     |
       |   -> 8 এর চাইতে minimize possible না
6     |
------   K = 2
4
------   K = 3
5

তাই এটা binary search দিয়ে খুব সহজেই সল্ভ করা সম্ভব।

My Solution:

#include<bits/stdc++.h>
using namespace std;
int a[1005], total_dist, n, k, highest, mx;

bool check(int x)
{
    int part = 0, sum = 0;
    for(int i = 0; i <= n; i++)
    {
        sum+=a[i];
        if(sum > x)
        {
            sum = a[i];
            part++;
        }
    }
    return part<=k;
}

void BS()
{
    int Left = mx, Right = total_dist, mid;
    while(Left<=Right)
    {
        mid = (Left+Right)/2;
        if(check(mid))
        {
            highest = mid;
            Right = mid - 1;
        }
        else
            Left = mid + 1;
    }
}

int main()
{
    int T;
    cin>>T;
    for(int t = 1; t <= T; t++)
    {
        total_dist = 0;
        mx = 0;
        memset(a, 0, sizeof(a));
        cin>>n>>k;
        for(int i = 0; i <= n; i++)
        {
            cin>>a[i];
            total_dist += a[i];
            mx = max(mx,a[i]);
        }
        BS();
        cout<<"Case "<<t<<": "<<highest<<endl;
        int flag = 0, cnt = 0;
        for(int i = 0; i <= n; i++)
        {
            flag+=a[i];
            if(flag > highest || cnt+(n+1-i)==k)
            {
                cout<<flag-a[i]<<endl;
                flag = a[i];
                cnt++;
            }
        }
        cout<<flag<<endl;
    }
    return 0;
}