Light OJ 1048 – Conquering Keokradong


/*
Link : http://www.lightoj.com/volume_showproblem.php?problem=1048
*/

#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 10000
#define CIN ios_base::sync_with_stdio(0)
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define getint2(a,b) scanf("%d%d",&a,&b)
#define getint3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define loop(i,n) for(int i=0;i<n;i++)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

int ara[2000],n,m;

bool test(int x)
{
    int t=x;
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        if(x<ara[i]) return 0;
        if(t-ara[i]>=0) t-=ara[i];
        else
        {
            cnt++;
            t=x-ara[i];
        }
        if(cnt>m) return 0;
    }
    return 1;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    sc("%d",&t);


    TEST_CASE(t)
    {
        int sum=0,maxx=-1;
        getint2(n,m);
        n++;
        for(int i=1; i<=n; i++)
        {
            getint(ara[i]);
            maxx=max(maxx,ara[i]);
            sum+=ara[i];
        }

        int l,r,mid;
        l=min(maxx,sum);
        r=max(maxx,sum);

        while(l<r)
        {
            mid=(l+r)/2;
            if(test(mid))
                r=mid;
            else
                l=mid+1;
        }
        while(!test(mid)) mid++;
        m++;
        PRINT_CASE;
        pf("%d\n",mid);
        int temp=0;
       l=n;
        for(int i=1; i<=l; i++)
        {
            temp+=ara[i];
            n--;
            m--;
            if(temp+ara[i+1]<=mid && n>m)
            {
                int j=i+1;
                temp+=ara[j];
                n--;
                while(temp+ara[j+1]<=mid && n>m)
                {
                    j++;
                    temp+=ara[j];
                    n--;
                }
                i=j;
            }
            pf("%d\n",temp);
            temp=0;
        }
    }
    return 0;
}

Here is another solution…


#include <bits/stdc++.h>
using namespace std;

int d[1024];
int main()
{
    int t, tc = 0, n, i, j, k, hi, lo, mid, sum;
    scanf ("%d", &t);
    while (tc < t)
    {
        tc++;
        scanf ("%d%d", &n,&k);
        n++;
        k++;
        hi = 0;
        lo = 0;
        for (i = 0; i < n; i++)
        {
            scanf ("%d", &d[i]);
            hi += d[i];
        }

        while (hi >= lo)
        {
            mid = (hi+lo)/2;
            for (i = 1, j = 0; i <= k ; i++)
            {
                sum = 0;
                for (; j < n; j++)
                {
                    if (sum+d[j]>mid) break;
                    sum += d[j];
                }
            }
            if (j < n) lo = mid+1;
            else hi = mid-1;
        }

        printf ("Case %d: %d\n", tc, lo);
        for (i = k, j = 0; i > 0; i--)
        {
            sum = 0;
            for (; n-j >= i; j++)
            {
                if (sum+d[j] > lo) break;
                sum += d[j];
            }
            printf ("%d\n",sum);
        }
    }
    return 0;
}


Advertisements

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