Cod sursa(job #922944)

Utilizator assa98Andrei Stanciu assa98 Data 22 martie 2013 18:47:14
Problema Lupul Urias si Rau Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <set>
#include <vector>
using namespace std;

struct sp
{
    int lana,zi;
};

class cmp
{
public:
    inline bool operator () (const sp a,const sp b)
    {
        if(a.lana==b.lana)
            return a.zi<b.zi;
        return a.lana>b.lana;
    }
};

multiset<sp,cmp> S;

vector<sp> A[100100];

int n,x,l;

int 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--)
    {
        if(A[i].empty())
            continue;
        for(int j=0; j<A[i].size(); j++)
            S.insert(A[i][j]);
        set<sp,cmp>::iterator it;
        it=S.begin();
        sol+=(*it).lana;
        S.erase(it);
    }
    printf("%d",sol);
    return 0;
}