Cod sursa(job #1425064)

Utilizator GinguIonutGinguIonut GinguIonut Data 26 aprilie 2015 15:59:17
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <algorithm>
#define dim 100001
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
long long sum;
int lana[dim],i,j,dist,n,x1,l,Max1,val,heap[dim],Max,poz,t,k;
struct cub
{
    int x;
    int y;
}timp[dim];
int cmp(cub o, cub p)
{
    return o.x>p.x;
}
void upDate(int poz)
{
    while(poz/2>0)
    {
        if(heap[poz]>heap[poz/2])
        {
                swap(heap[poz],heap[poz/2]);
                poz/=2;
        }
        else
            break;
    }
}
void downDate(int poz)
{
    int po;
    while(poz*2<=k)
    {
        po=poz*2;
        if(po+1<=k&&heap[po]<heap[po+1])
            po++;
        if(heap[poz]<heap[po])
        {
            swap(heap[po],heap[poz]);
            poz=po;
        }
        else
            break;
    }
}
int main()
{
    fin>>n>>x1>>l;
    for(i=1;i<=n;i++)
    {
        fin>>dist>>lana[i];
        if(dist<=x1)
        {
            if(dist==x1)
                timp[i].x=1;
            else
                timp[i].x=(x1-dist)/l+1;
        }
        else
            timp[i].x=0;
        if(timp[i].x>Max)
            Max=timp[i].x;
        timp[i].y=i;
    }
    sort(timp+1,timp+n+1,cmp);
    poz=1;
    for(j=Max;j>=1;j--)
    {
        for(t=poz;timp[t].x==j&&t<=n;t++)
        {
            heap[++k]=lana[timp[t].y];
            upDate(k);
        }
        if(k>0)
        {
            sum+=heap[1];
            swap(heap[1],heap[k]);
            k--;
            downDate(1);
        }
        poz=t;
    }
    fout<<sum;
    return 0;
}