Cod sursa(job #1813283)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 22 noiembrie 2016 20:45:08
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <algorithm>
#define DIM 100001
#define f first
#define s second
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
long long n,x,l,maxim,i,j,k,c,p,sol,nr;
pair <int,int> v[DIM],heap[DIM];
int cmp(pair<int,int> a, pair<int,int> b)
{
    return a.f>b.f;
}
int main ()
{

    fin>>n>>x>>l;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].f>>v[i].s;
        if(v[i].f<=x)
        {
            v[i].f=(x-v[i].f)/l;
            if(v[i].f>maxim)
                maxim=v[i].f;
        }
        else
            v[i].f=-1000000;
    }
    sort(v+1,v+n+1,cmp);
    i=0;
    k=0;
    for(j=maxim;j>=0;j--)
    {
        while(v[i+1].f==j)
        {
            i++;
            heap[++k]=v[i];
            c=k;
            p=k/2;
            while(p!=0)
            {
                if(heap[p].s<heap[c].s)
                {
                    swap(heap[p],heap[c]);
                    c=p;
                    p=c/2;
                }
                else
                    break;
            }
        }
        if(k!= 0)
        {
            sol+=heap[1].s;
            heap[1]=heap[k];
            k--;
            p=1;c=2;
            while(c<=k)
            {
                if(c+1<=k&&heap[c+1].s>heap[c].s)
                    c++;
                if (heap[p].s<heap[c].s){
                    swap(heap[p],heap[c]);
                    p=c;
                    c=p*2;
                }
                else
                    break;
            }
        }
    }
    fout<<sol;
    return 0;
}