Cod sursa(job #1148789)

Utilizator gedicaAlpaca Gedit gedica Data 21 martie 2014 09:18:07
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

long long n, x, l;
long long s, tmax=-1, j;

struct oaie
{
    long long t, m;
};

oaie a[1000001];

struct comp
{
    bool operator()(const oaie &a, const oaie &b)
    {
        if(a.m<=b.m)
            return 1;
        return 0;
    };
};

bool comps(oaie a, oaie b)
{
    if(a.t>b.t || (a.t==b.t && a.m>=b.m))
        return 1;
    return 0;
}

priority_queue<oaie, vector<oaie>, comp>codita;

ifstream in("lupu.in");
ofstream out("lupu.out");

inline void citire()
{
    for(int i=0; i<n; i++)
    {
        in >> a[i].t >> a[i].m;
        if(l!=0)
        {
            a[i].t=(x-a[i].t)/l+1;
            if(a[i].t>tmax) tmax=a[i].t;
        }
    }
}

inline void solve()
{
    for( int i= tmax; i>=1; --i )
    {
        while( a[j].t==i && j<n )
        {
            codita.push(a[j++]);
        }
        if( !codita.empty() )
        {
            s+=codita.top().m;
            codita.pop();
        }
    }
}

int main()
{
    in >> n >> x >> l;

    citire();

    sort(a, a+n, comps);

    solve();

    out << s << '\n';

    in.close();
    out.close();
    return 0;
}