Category Archives: Greedy

USACO: Ski Course Design

0
Posted on by

Problem Link : http://train.usaco.org/usacoprob2?a=tffkkLavmsp&S=skidesign


/*
PROG: skidesign
LANG: C++
*/

#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 db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;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 ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/


int main()
{
    freopen("skidesign.in","r",stdin);
    freopen("skidesign.out","w",stdout);
    int n,x;
    sf(n);
    vector<int>v;
    loop(i,n) sf(x),v.pb(x);
    ll ans=INT_MAX;

    for(int i=1; i<=83; i++)
    {
        ll temp=0;
        for(int j=0; j<n; j++)
        {
            if(v[j]<i) temp+=sqr(i-v[j]);
            else if(v[j]>i+17) temp+=sqr(v[j]-i-17);
        }
        ans=min(ans,temp);
    }
    cout<<ans<<endl;
    return 0;
}

USACO : Wormholes

0
Posted on by

Problem Link : http://train.usaco.org/usacoprob2?a=tffkkLavmsp&S=wormhole


/*
PROG: wormhole
LANG: C++
*/


#include <iostream>
#include <fstream>
using namespace std;
#define MAX_N 12

int N, X[MAX_N+1], Y[MAX_N+1];
int wife[MAX_N+1];
int next_on_right[MAX_N+1];

bool cycle_exists(void)
{
    for (int start=1; start<=N; start++)
    {
        int pos = start;
        for (int count=0; count<N; count++)
            pos = next_on_right[wife[pos]];
        if (pos != 0) return true;
    }
    return false;
}

int solve(void)
{
    int i, total=0;
    for (i=1; i<=N; i++)
        if (wife[i] == 0) break;

    // everyone paired?
    if (i > N)
    {
        if (cycle_exists()) return 1;
        else return 0;
    }

    // try pairing i with all possible other wormholes j
    for (int j=i+1; j<=N; j++)
        if (wife[j] == 0)
        {
            // try pairing i & j, let recursion continue to
            // generate the rest of the solution
            wife[i] = j;
            wife[j] = i;
            total += solve();
            wife[i] = wife[j] = 0;
        }
    return total;
}

int main(void)
{
    ifstream fin("wormhole.in");
    fin >> N;
    for (int i=1; i<=N; i++) fin >> X[i] >> Y[i];
    fin.close();

    for (int i=1; i<=N; i++) // set next_on_right[i]...
        for (int j=1; j<=N; j++)
            if (X[j] > X[i] && Y[i] == Y[j]) // j right of i...
                if (next_on_right[i] == 0 ||
                        X[j]-X[i] < X[next_on_right[i]]-X[i])
                    next_on_right[i] = j;

    ofstream fout("wormhole.out");
    fout << solve() << "\n";
    fout.close();
    return 0;
}

UVa 714 – Copying Books

0
Posted on by 

/*
User ID: turing_13
Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=655
*/

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#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 db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;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 ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int n,k,ara[510];
bool visited[510];

int func(ll mid)
{
    ms(visited,0);
    int cnt=0;
    for(int i=n-1;i>=0;)
    {
        ll sum=0;
        while(i>=0 && sum+ara[i]<=mid)
        {
            sum+=ara[i];
            i--;
        }
        if(sum==0)
            return k+1;
        cnt++;
        visited[i]=1;
    }
    return cnt;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    sf(t);
    TEST_CASE(t)
    {
        ll sum=0;
        sff(n,k);
        loop(i,n)
        {
            sf(ara[i]);
            sum+=ara[i];
        }

        ll lo=1,hi=sum,mid;
        while(lo<hi)
        {
            mid=lo+(hi-lo)/2;
            if(func(mid)<=k)
                hi=mid;
            else
                lo=mid+1;
        }

        int cnt=func(hi);
        for(int i=0;i<n && cnt<k;i++)
        {
            if(!visited[i])
                visited[i]=1,cnt++;
        }

        loop(i,n)
        {
            if(i)
                pf(" %d",ara[i]);
            else
                pf("%d",ara[i]);
            if(visited[i])
                pf(" /");
        }
        pf("\n");
    }
    return 0;
}

UVa 12032 – The Monkey and the Oiled Bamboo

0
Posted on by 

/*
User ID: turing_13
Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3183
*/

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#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 db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;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 ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int n;
ll ara[100005];

bool func(int mid)
{
    for(int i=1;i<=n;i++)
    {
        if(ara[i]-ara[i-1]>mid) return false;
        if(ara[i]-ara[i-1]==mid) mid--;
    }
    return true;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    sf(t);
    TEST_CASE(t)
    {
        ll lo=10000000000,hi=-10000000,mid;
        sf(n);
        REP(i,1,n+1)
        {
            sf(ara[i]);
            lo=min(lo,ara[i]);
            hi=max(hi,ara[i]);
        }
        while(lo<hi)
        {
            mid=lo+(hi-lo)/2;
            if(func(mid))
                hi=mid;
            else
                lo=mid+1;
        }
        PRINT_CASE;
        pf("%d\n",hi);
    }
    return 0;
}

UVa 11413 – Fill the Containers

0
Posted on by 

/*
User ID: turing_13
Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2408
*/

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#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 db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;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 ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int n,m;
int ara[100000];

int func(ll mid)
{
    int cnt=0;
    ll sum=0;
    for(int i=0;i<n;)
    {
        sum=0;
        while(i<n && sum+ara[i]<=mid)
        {
            sum+=ara[i];
            i++;
        }
        if(cnt>m)
            return cnt;
        cnt++;
    }
    return cnt;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    while(sff(n,m)==2)
    {
         ll lo=1, hi=0,mid;
        loop(i,n) sf(ara[i]),hi+=ara[i];

        while(lo<hi)
        {
            mid=lo+(hi-lo)/2;
            if(func(mid)<=m)
                hi=mid;
            else
                lo=mid+1;
        }
        pf("%lld\n",hi);
    }
    return 0;
}

USACO : Combination Lock

0
Posted on by

Problem Link : http://train.usaco.org/usacoprob2?a=4Hh6zP8GJZV&S=combo


/*
PROG: combo
LANG: C++
*/

#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); cin.tie(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 n;
bool check1(int a, int b)
{
    if(abs(a-b)<=2) return 1;
    if(abs(a-b)>=n-2) return 1;
    return 0;
}

bool check(int a1,int b1,int c1,int a2,int b2,int c2)
{
    return (check1(a1,a2) && check1(b1,b2) && check1(c1,c2));
}
int main()
{
    freopen("combo.in","r",stdin);
    freopen("combo.out","w",stdout);
    int a,b,c,x,y,z;
    int cnt=0;
    cin>>n;
    cin>>a>>b>>c>>x>>y>>z;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(check(i,j,k,a,b,c)||check(i,j,k,x,y,z))
                    cnt++;
    cout<<cnt<<endl;
    return 0;
}

USACO: Prime Cryptarithm

0
Posted on by

Problem Link : http://train.usaco.org/usacoprob2?a=dOLJGJAE7bv&S=crypt1


/*
TASK: crypt1
LANG: C++
*/

#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); cin.tie(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[11];
bool mp[11];

int main()
{
    freopen("crypt1.in","r",stdin);
    freopen("crypt1.out","w",stdout);

    int n;
    cin>>n;
    loop(i,n)
        {
            cin>>ara[i];
            mp[ara[i]]=1;
        }
    int cnt=0;
    loop(a,n)
    loop(b,n)
    loop(c,n)
    {
        int abc=ara[a]*100+ara[b]*10+ara;
        if( abc/1000 !=0)
            continue;
        int p1,p2;
        loop(d,n)
        {
            p1=abc*ara[d];
            if( p1/1000 !=0)
            continue;
            int temp1=p1;
            bool test=0;
            while(temp1)
            {
                if(mp[temp1%10]==1)
                {
                    temp1/=10;
                }
                else
                {
                    test=1;
                    break;
                }
            }
            if(test)
                continue;
            loop(e,n)
            {
                p2=abc*ara[e];
                if( p2/1000 !=0)
                continue;
                int temp2=p2;
                bool test=0;
                while(temp2)
                {
                    if(mp[temp2%10]==1)
                    {
                        temp2/=10;
                    }
                    else
                    {
                        test=1;
                        break;
                    }
                }
                if(test)
                    continue;
                int ans=p1+p2*10;
                while(ans)
                {
                    if(mp[ans%10]==1)
                        ans/=10;
                    else
                    {
                        test=1;
                        break;
                    }
                }
                if(test==0)
                    cnt++;
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

USACO: Barn Repair

0
Posted on by

Problem Link : http://train.usaco.org/usacoprob2?a=dOLJGJAE7bv&S=barn1


/*
PROG: barn1
LANG: C++
*/
#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); cin.tie(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;

bool test(int a,int b)
{
    return a>b;
}

int main()
{
    freopen("barn1.in","r",stdin);
    freopen("barn1.out","w",stdout);
    int sum=0,ans=0,m,s,c;
    int ara[300],len[300];
    cin>>m>>s>>c;
    loop(i,c)
    {
        cin>>ara[i];
    }
    ms(len,0);
    sort(ara,ara+c);
    int maxx=ara[c-1];
    int minx=ara[0];
    int cnt=0;
    sum=maxx-minx+1;

    for(int i=1;i<c;i++)
    {
        len[cnt++]=ara[i]-ara[i-1]-1;
    }

    sort(len,len+cnt,test);

    loop(i,m-1)
    {
        ans+=len[i];
    }
    cout<<sum-ans<<endl;
    return 0;
}

USACO : Mixing Milk

0
Posted on by

Problem Link : http://train.usaco.org/usacoprob2?a=ZjtQpZMHmbg&S=milk


/*
PROG: milk
LANG: C++
*/

#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); cin.tie(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;
vector<pii>v;

int main()
{
    freopen("milk.in","r",stdin);
    freopen("milk.out","w",stdout);
    int n,m,ans=0,a,b;
    getint2(n,m);
    loop(i,m)
    {
        getint2(a,b);
        v.pb(MP(a,b));
    }
    
    sort(all(v));

    for(int i=0;i<SZ(v);i++)
    {
        if(n==0)
            break;
        if(n<=v[i].ss)
        {
            ans+=(n*v[i].ff);
            break;
        }
        else
        {
            ans+=(v[i].ss*v[i].ff);
            n-=v[i].ss;
        }
    }
    cout<<ans<<endl;
    v.clear();
    return 0;
}

Light OJ 1048 – Conquering Keokradong

1
Posted on by 

/*
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;
}