Cod sursa(job #938629)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 13 aprilie 2013 10:36:12
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

struct oaie1
{
    int dist;
    int puf;
}v1[100005];

struct oaie2
{
    int dist;
    int puf;
}v2[100005];

bool operator<(const oaie1 &a,const oaie1 &b)
{
    if(a.dist<b.dist)
        return 1;
    return 0;
}

bool operator<(const oaie2 &a,const oaie2 &b)
{
    if(a.puf<b.puf)
        return 1;
    return 0;
}

int main()
{
    ifstream cin("lupu.in");
    ofstream cout("lupu.out");

    int n,x,l,i;
    cin>>n>>x>>l;

    int plecare=x%l;

    for(i=0;i<n;i++)
    {
        cin>>v1[i].dist;
        cin>>v1[i].puf;
    }
    sort(v1,v1+n);

    for(i=0;i<n;i++)
    {
        v2[i].puf=v1[i].puf;
        v2[i].dist=v1[i].dist;
    }
    priority_queue<oaie2> coada;

    int poz=0;

    long long int maxim=0;

    for(;plecare<=x;plecare+=l)
    {
        while(v2[poz].dist<=plecare)
          coada.push(v2[poz++]);

        if(!coada.empty())
        {
          maxim+=coada.top().puf;
          coada.pop();
        }
    }

    cout<<maxim<<'\n';
    cin.close();
    cout.close();
    return 0;
}