Cod sursa(job #1318464)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 15 ianuarie 2015 23:14:44
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 0.94 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int n,X,L,Tmax;
struct Oaie{
    int d,lana,t;
    bool operator <(const Oaie &A) const
    {
        return t>A.t;
    }
};
Oaie v[100100];
long long sol;
vector <int> H;
 
int main()
{
    int i,j;
    ifstream fin("lupu.in");
    fin>>n>>X>>L;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].d>>v[i].lana;
        v[i].t=(X-v[i].d)/L+1;
        Tmax=max(Tmax,v[i].t);
    }
    fin.close();
     
    sort(v+1,v+n+1);
    for(i=Tmax,j=1;i>0;i--)
    {
        while(j<=n && v[j].t==i)
        {
            H.push_back(v[j].lana);
            push_heap(H.begin(),H.end());
            j++;
        }
        if(H.size())
        {
            sol+=1LL*H[0];
            pop_heap(H.begin(),H.end());
            H.pop_back();
        }
    }
     
    ofstream fout("lupu.out");
    fout<<sol<<"\n";
    fout.close();
    return 0;
}