Poj Solution 2184

http://poj.org/problem?id=2184

#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <functional>
using namespace std;

bool mem[200100],*sign = mem+100000;
int mem2[200100],*ans = mem2+100000;

typedef pair<int,int> node;
node c[100];
int n;

node mem3[2][100000],*s = mem3[0], *t = mem3[1];
int sn,tn;

int main()
{
    int i, j, n, k, h, m, v;

    scanf( "%d", &n );

    for( i=0; i<n; i++ )
        scanf( "%d %d", &c[i].first, &c[i].second );

    memset( sign-1000*n-5, 0, sizeof(bool) * ( 1000*2*n+10 ) );

    sign[0] = true;
    ans[0] = 0;
    sn = 0;

    s[sn].first = 0;
    s[sn].second = 0;
    sn++;

    for( i=0; i<n; i++ )
    {
        for( m=sn, j=0 ; j < m ; j++ )
        {
            h = s[j].second + c[i].second;
            k = s[j].first + c[i].first;

            if( ! sign[k] )
            {
                sign[k] = true;
                ans[k] = h;
                
                s[sn].first = k;
                s[sn].second = h;
                sn++;
            }
            else if( h > ans[k] )
            {
                ans[k] = h;

                s[sn].first = k;
                s[sn].second = h;
                sn++;
            }

        }
        
        std::merge( s, s+m, s+m, s+sn, t, greater<node>() );
        swap( t, s );

        m = sn;
        v = s[0].second;
        tn = 0;
        t[tn++] = s[0];

        for( j = 1; j<m; j++ )
        {
            if( s[j].second > v )
            {
                t[tn++] =  s[j];
                v = s[j].second;
            }
        }

        swap( t, s);
        swap( tn, sn);

        if( tn >= 100000 || sn >=100000 )
            while(1) printf( "faintn" );
        
    }

    int answer = 0;
    
    for( i=0; i<=1000*n; i++ )
        if( sign[i] && ans[i] >=0 && i + ans[i] > answer )
            answer = i + ans[i];

    printf( "%dn", answer );

    return 0;
}