Cod sursa(job #1489424)

Utilizator PletoPletosu Cosmin-Andrei Pleto Data 21 septembrie 2015 08:18:09
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");

priority_queue <int> h;
pair <int,int> a[100010];
int N,X,L,i;
long long sol;
///N=numarul de oi
///X=distanta maxima de la care lupul poate alege oi
///L=distanta cu care se departeaza oile de lup dupa fiecare alegere

int main()
{
    in>>N>>X>>L;
    for(i=1;i<=N;i++)
        in>>a[i].first>>a[i].second;
    in.close();
    sort(a+1,a+i+1);
    for(int d=0,i=1;d<=X;d+=L)
    {
        while(i<=N && a[i].first<=d)
        {
            h.push(a[i].second);
            i++;
        }
        if(!(h.empty()))
        {
            sol+=h.top();
            h.pop();
        }
    }
    out<<sol<<'\n';
    out.close();
    return 0;
}