Cod sursa(job #1696468)

Utilizator assa98Andrei Stanciu assa98 Data 29 aprilie 2016 10:48:54
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

struct sp
{
    int lana,zi;
};

struct cmp {
  inline bool operator () (const sp &a, const sp &b) const {
    return a.lana < b.lana;
  }
};

priority_queue<sp, vector<sp>, cmp> S;

vector<sp> A[100100];

int n,x,l;

long long sol;

int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%d%d%d",&n,&x,&l);
    for(int i=1; i<=n; i++)
    {
        int a,b;
        scanf("%d%d",&b,&a);
        if(b>x)
            continue;
        int zi=(x-b)/l+1;
        if(zi>n)
            zi=n;
        sp str;
        str.lana=a;
        str.zi=zi;
        A[zi].push_back(str);
    }
    for(int i=n; i>=1; i--)
    {
        for(int j=0; j<A[i].size(); j++)
            S.push(A[i][j]);
        if(S.empty())
            continue;
        sp it=S.top();
        sol+=it.lana;
        S.pop();
    }
    printf("%lld",sol);
    return 0;
}