Cod sursa(job #1149719)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 22 martie 2014 10:49:10
Problema Lupul Urias si Rau Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>

using namespace std;

fstream f("lupu.in",ios::in);
fstream g("lupu.out",ios::out);

const long nmax=100005;

long n,x,l,a[nmax],t[nmax],tmax,el,fol[nmax],i,t1;
long long sol;

void quickSort(long li,long ls)
{
    long i=li,j=ls,aux;
    long pivot=a[(i+j)/2];
    while (i<=j)
    {
        while (a[i]>pivot) i++;
        while (a[j]<pivot) j--;
        if (i<=j)
        {
            aux=a[i];
            a[i]=a[j];
            a[j]=aux;
            aux=t[i];
            t[i]=t[j];
            t[j]=aux;
            i++;j--;
        }
    }
    if (li<j) quickSort(li,j);
    if (i<ls) quickSort(i,ls);
}

void read()
{
    f>>n>>x>>l;
    for (i=1;i<=n;i++)
    {
        f>>t1>>a[i];
        t[i]=(x-t1)/l+1;
        if (t[i]>tmax) tmax=t[i];
    }
}

int cautare(long li,long ls)
{
    if (li==ls)
        {
            if (!fol[li]) {
                                fol[li]=1;
                                el++;
                                return 1;
                                }
        }
        else {
                if (cautare((li+ls)/2+1,ls)) return 1;
                if (cautare(li,(li+ls)/2)) return 1;
                }
    return 0;
}

void solve()
{
    quickSort(1,n);
    el=0;
    for (i=1;i<=n;i++)
    {
        if (cautare(1,t[i])) sol=sol+a[i];
        if (el==tmax) break;
    }
    g<<sol;
}

int main()
{
    read();
    solve();
    return 0;
}