2014年12月30日 星期二

USACO 2014 December Contest, Gold Problem 3. Cow Jog

/* 
    名字相同 題目不同.___. 
    感覺比 silver 那題簡單...
*/
// http://www.usaco.org/index.php?page=viewproblem2&cpid=496
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

typedef long long ll;

typedef pair<ll, ll> xv;
#define x first
#define v second

xv cow[200000];

int N, T;

multiset<ll, greater<ll> > s;

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

    scanf("%d %d", &N, &T);

    for(int Ni = 0; Ni < N; Ni++)
        scanf("%lld %lld", &cow[Ni].x, &cow[Ni].v);


    for(int Ni = 0; Ni < N; Ni++)
    {
        ll p = cow[Ni].v*T+cow[Ni].x;

        multiset<ll, greater<ll> >::iterator it;
        it = s.upper_bound(p);

        if( it != s.end() ) s.erase(it );
        s.insert(p);
    }

    printf("%lu\n", s.size());
}

沒有留言:

張貼留言