Cod sursa(job #1027947)

Utilizator alecsandrualex cuturela alecsandru Data 13 noiembrie 2013 12:10:53
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct sheep
{
    int oaie,time;
};
sheep temp;
long long s;
int n,x,l,i,di,lana[100001];
int h[100001],poz,nh,cnt;
vector <sheep> v;
bool cmp(const sheep &a,const sheep &b)
{
    return a.time>b.time;
}
void schimba(int a, int b)
{
    int c,d;
    c=h[a];
    h[a]=h[b];
    h[b]=c;
}
void coboara(int p)
{
    int fs=2*p,fd=2*p+1,bun=p;
    if(fs<=nh&&lana[h[fs]]>lana[h[bun]])
        bun=fs;
    if(fd<=nh&&lana[h[fd]]>lana[h[bun]])
        bun=fd;
    if(bun!=p)
    {
        schimba(p,bun);
        coboara(bun);
    }
}
void urca(int p)
{
    while(p!=1&&lana[h[p]]>lana[h[p/2]])
    {
        schimba(p,p/2);
        p/=2;
    }
}
void adauga(int x)
{
    h[++nh]=x;
    urca(nh);
}
void sterge(int p)
{
    schimba(p,nh--);
    urca(p);
    coboara(p);
}
int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%d%d%d",&n,&x,&l);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&di,&lana[i]);
        temp.time=(x-di)/l+1;
        temp.oaie=i;
        v.push_back(temp);
    }
    sort(v.begin(),v.end(),cmp);
    cnt=v[0].time;
    for(i=0;i<n;i++)
    {
        if(v[i].time==cnt)
        {
            adauga(v[i].oaie);
        }
        else
        {
            if(nh!=0)
            {
                s+=lana[h[1]];
                sterge(1);
            }
            cnt=v[i].time;
            adauga(v[i].oaie);
        }
    }
    if(nh!=0)
    s+=lana[h[1]];
    printf("%lld",s);
    return 0;
}