Cod sursa(job #1813268)

Utilizator BogauuuBogdan Ivancu Bogauuu Data 22 noiembrie 2016 20:37:29
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <algorithm>

#define f first
#define s second

using namespace std;

pair <int,int> v[100002], a[100002];

long long n,dmax,l,maxim,i,j,d,c,p,sol,k;

ifstream fin ("lupu.in");
ofstream fout ("lupu.out");

int cmp (pair<int,int> x, pair<int,int> y)
{
    return x.f>y.f;
}

int main ()
{

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

    return 0;
}