(USACO) Stamps

/*
ID: himuhas1
TASK: stamps
LANG: C++
*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<sstream>
#include<set>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define ll long long
#define pb push_back
#define MP make_pair
#define mem(a, v) memset(a,  v, sizeof(a))
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define SZ(a) (int(a.size()))
#define INF (1<<29)
#define paii pair<int, int>
#define sf scanf
#define pf printf


using namespace std;


#define MAXX 2000002

#define dump(x) cout<<#x<<" = "<<x<<endl

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


    int n, k, values[52];

    sf("%d %d", &k, &n);

    loop(i, n)
    {
        sf("%d", &values[i]);
    }

    int dp[MAXX];
    mem(dp, 1);
    dp[0] = 0;
    int mxSum = 0;
    int tmp;

    loop(i, n)
    {
        for(int j=0; j<=mxSum; j++)
        {
            if(dp[j] != 16843009 && dp[j]+1 <=k)
            {
                tmp = j + values[i];
                dp[tmp] = min(dp[tmp], dp[j] + 1);
                mxSum = max(mxSum, tmp);
            }
        }
    }

    int res;
    for(res=0; res<=mxSum; res++)
    {
        if(dp[res] == 16843009 )
        {
            break;
        }
    }
    res--;

    cout<<res<<endl;




}

(lightOj) 1048 – Conquering Keokradong

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;

#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;
struct ASDFG{
    template<typename T>
    ASDFG& operator,(vector<T> &v){
        pf("[");
        cout<<v[0];
        FOR(i, 1, SZ(v)){
            cout<<", "<<v[i];
        }
        pf("]");
        return *this;
    }

    template<typename T>
    ASDFG& operator,(T x) {
        cout<<x<<" ";
        return *this;
    }


}asdfg;



//Header ends here

#define MAXX 1003

int main()
{

    int kases, kaseno =  0;
    take(kases);
    int dist[MAXX];
    while(kases--)
    {
        int N, K;
        take(N, K);
        take(dist[0]);
        int low=dist[0], high;
        for(int i=1; i<=N; i++)
        {
            take(dist[i]);
            low = max(low, dist[i]);
            dist[i] += dist[i-1];
        }
        high = dist[N];

        //for(int i=0; i<=N; i++) pf("dist[%d] = %d\n", i, dist[i]);


        int pos, last_value;
        while(low<=high)
        {
            int mid = (low+high)>>1;
            //debug(low, mid, high);
            last_value = mid;

            //dump(mid);
            for(int i=0; i<=K; i++)
            {
                int l = 0, h = N, m;
                while(l <= h)
                {
                    m = (l+h)>>1;
                    if(dist[m] <= last_value)
                    {
                        l = m + 1;
                    }
                    else
                    {
                        h = m - 1;
                    }
                }
                pos = l - 1;
                //cout<<"\tpos"<<pos<<endl;
                last_value = dist[pos] + mid;
                if(pos >= N) break;
            }


            if(pos >= N)
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        high++;
        pf("Case %d: %d\n", ++kaseno, high);
        stack<int>all[302];
        last_value = high;
        int last_pos = 0;
        int s;
        for(s=0; s<=K; s++)
        {
            //dump(last_value);
            int l=0, h = N, m;
            while(l <= h)
            {
                m = (l+h)>>1;
                if(dist[m] <= last_value)
                    l = m + 1;
                else
                    h = m - 1;
            }
            pos = l - 1;
            last_value = dist[pos] + high;


            for(;last_pos<=pos; last_pos++)
            {
                all[s].push( dist[last_pos] - (last_pos?dist[last_pos-1]:0) );
            }

            if(pos>= N) break;
        }

        for(int i=K; i>-1 && all[i].size() == 0; i--)
        {
            if(SZ(all[s]) == 0)
                s--;
            all[i].push(all[s].top());
            all[s].pop();
        }

        for(int i=0; i<=K; i++)
        {
            int sum = 0;
            while(SZ(all[i]))
            {
                //cout<<all[i].top()<<", ";
                sum += all[i].top();
                all[i].pop();
            }
            //cout<<endl<<endl;
            pf("%d\n", sum);
        }


    }


    return 0;
}