Cod sursa(job #2288549)

Utilizator andrew_assassin789Andrei Manea andrew_assassin789 Data 23 noiembrie 2018 17:00:06
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <queue>
#include <algorithm>
#include <vector>
#define nmax 200005
using namespace std;
struct oaie
{
    unsigned int dist,lana;
    bool operator() (const oaie &A, const oaie &B)
    {
        return A.lana<B.lana;
    }
};
oaie V[nmax];
inline bool distanta(oaie A, oaie B)
{
    return A.dist<B.dist;
}
priority_queue <oaie,vector <oaie>, oaie> Q;
int main()
{
    ifstream fin("lupu.in");
    ofstream fout("lupu.out");
    unsigned int n,L,X,i,dmax;
    long long total=0;
    fin>>n>>X>>L;
    for (i=1;i<=n;i++)
    {
        fin>>V[i].dist>>V[i].lana;
    }
    fin.close();
    sort(V+1,V+n+1,distanta);
    //sortam oile dupa distanta
    for (dmax = X%L, i = 1; dmax <= X; dmax += L)
    {
        //inseram oile din interval
        for (; V[i].dist <= dmax && i<=n; i++)
        {
            Q.push(V[i]);
        }
        // o alegem pe cea mai mare
        if (!Q.empty())
        {
            total+=(Q.top().lana);
            Q.pop();
        }
    }
    fout<<total<<'\n';
    fout.close();
    return 0;
}