Poj Solution 2008

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

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

pair<int,int> p[1000];
pair<int,int> q[1000];

bool cmp( const pair<int,int> &a, const pair<int,int> &b ) {
    return a.second < b.second;
}

int main( ) {
    int a, b, c, n, i, j, m, limit, ans = 0;
    scanf( "%d", &n );
    scanf( "%d%d%d", &a, &b, &c );

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

    sort( p, p+n );
    priority_queue<int, vector<int> > pq;

    for( i=0; i<n; i++ ) {
        m = 0;
        for( j=i; j<n; j++ )
            q[m++] = p[j];
        
        sort( q, q+m, cmp );

        for( j=m-1; j>=0; j-- ) {

            pq.push( a*q[j].first+b*q[j].second );
            limit = a*p[i].first+b*q[j].second+c;

            while( !pq.empty() && pq.top() > limit )
                pq.pop();
            if( pq.size() > ans )
                ans = pq.size();

        }
        while( !pq.empty() )
            pq.pop();
    }

    printf( "%dn", ans );

    return 0;
}



											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *