Cod sursa(job #1318664)

Utilizator emiiMihailescu Ionut Emanuel emii Data 16 ianuarie 2015 11:00:35
Problema Lupul Urias si Rau Scor 28
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 0.93 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
int i,n,m;
long long D,L,s,h[100001];
struct oaie
{
    long long d,l;

}v[100002];
void interschimb(int i,int j)
{
    int x=h[i];
    h[i]=h[j];
    h[j]=x;
}
void up (int i)
{
    while(h[i]<h[i/2]&&i>=2)
        interschimb(i,i/2),i/=2;
}
void down (int i)
{
    int x=2*i+1,y=2*i;
    int k=i;
    if(h[x]<k&&x<=m)
        k=x;
    if(h[y]<k&&y<=m)
        k=y;
    if(k!=i)
    interschimb(i,k),down(k);
}
bool compar(oaie a,oaie b)
{
    return a.d<b.d;
}
int main()
{f>>n>>D>>L;
for(i=1;i<=n;i++)
    f>>v[i].d>>v[i].l,v[i].d=(D-v[i].d)/L;
sort(v,v+n+1,compar);
m=1;
h[m]=v[1].l;
for(i=2;i<=n;i++)
{
    if(m<=v[i].d)
        m++,h[m]=v[i].l,up(m);
    else
        if(h[1]<v[i].l)
            h[1]=v[i].l,down(1);
}
s=0;
for(i=1;i<=m;i++)
    s+=h[i];
g<<s;
return 0;
}