Cod sursa(job #400910)

Utilizator popoiu.georgeGeorge Popoiu popoiu.george Data 22 februarie 2010 10:11:59
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<fstream>
#include<algorithm>
#define inf "lupu.in"
#define outf "lupu.out"
#define NMax 100010
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

int N,X,L;
int d[NMax],a[NMax];

typedef int Heap[NMax];
Heap H;
int hdim;

struct elem
{
int t;
int l;
};

elem v[NMax];

void read()
{
f>>N>>X>>L;
for(int i=1;i<=N;i++)
    {
    f>>d[i]>>a[i];
    v[i].t = ( (X-d[i])/L ) + 1 ;
    v[i].l = i;
    }
}

bool rule(elem a,elem b)
{
if( a.t < b.t ) return false;
return true;
}

void upheap(int nod)
{
int s;
while( nod>1 )
    {
    s= (nod>>1) ;
    if( a[ H[s] ] < a[ H[nod] ] )
        {
        swap( H[s], H[nod] );
        nod=s;
        }
    else break;
    }
}

void downheap(int nod)
{
int f;
while( true )
    {
    f= (nod<<1) ;
    if( f<=hdim )
        {
        if( f+1<=hdim && a[ H[f+1] ]>a[ H[f] ] ) ++f ;
        if( a[ H[f] ] > a[ H[nod] ] )
            {
            swap( H[f], H[nod] );
            nod=f;
            }
        else break;
        }
    else break;
    }
}

void solve()
{
int j=1;
int s=0;
sort(v+1, v+N+1, rule);
for(int i=v[1].t ; i>=1; --i)
    {
    while( v[j].t == i && j<=N)
        {
        ++hdim;
        H[hdim] = v[j].l ;
        upheap( hdim );
        ++j;
        }
    if( hdim )
        {
        s+= a [ H[1] ];
        H[1]=H[hdim];
        --hdim;
        downheap( 1 );
        }
    }
g<< s ;
}

int main()
{
read();
solve();
f.close();
g.close();
return 0;
}