Cod sursa(job #789508)

Utilizator visanrVisan Radu visanr Data 18 septembrie 2012 16:01:28
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>
using namespace std;

#define nmax 100010
#define ll long long

struct data
{
       ll x, y;
}V[nmax];
long long Tmax, N, X, L, ans;
priority_queue<ll> Q;

bool cmp(data one, data two)
{
     return one.x > two.x;
}

int main()
{
    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);
    int i, j = 1;
    scanf("%lld %lld %lld", &N, &X, &L);
    for(i = 1; i <= N; i++)
    {
          scanf("%lld %lld", &V[i].x, &V[i].y);
          V[i].x = (X - V[i].x) / L;
          Tmax = max(Tmax, V[i].x);
    }
    sort(V + 1, V + N + 1, cmp);
    for(i = Tmax; i >= 0; i--)
    {
          while(j <= N && V[j].x == i)
                  Q.push(V[j].y), j ++;
          if(!Q.empty())
                        ans += Q.top(), Q.pop();
    }
    printf("%lld\n", ans);
    return 0;
}