Cod sursa(job #1326077)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 24 ianuarie 2015 17:46:15
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 0.78 kb
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;
const int NMAX = 100005;

int N, X, L, i, D, A, M, t;
long long sol, add;
struct Sheep
{
    int d, a;
} P[NMAX];
priority_queue<int> PQ;

bool cmp(Sheep A, Sheep B)
{
    return A.d < B.d;
}

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

    scanf("%d%d%d", &N, &X, &L);
    for(i = 1; i <= N; i++)
    {
        scanf("%d%d", &D, &A);
        if(D <= X) P[++M].d = (X - D) / L + 1, P[M].a = A;
    }

    N = M;
    sort(P + 1, P + N + 1, cmp);
    for(i = N, t = P[N].d; t; t--)
    {
        while(i && P[i].d == t) PQ.push(P[i].a), i--;
        if(!PQ.empty()) sol += PQ.top(), PQ.pop();
    }
    printf("%lld\n", sol);

    return 0;
}