Pagini recente » Borderou de evaluare (job #157036) | Cod sursa (job #1105017) | Borderou de evaluare (job #3250265) | Autentificare | Cod sursa (job #640793)
Cod sursa(job #640793)
#include<cstdio>
#include<algorithm>
#define infile "lupu.in"
#define outfile "lupu.out"
#define n_max 100005
#define ls(i) i<<1
#define rs(i) (i<<1) + 1
#define f(i) i>>1
using namespace std;
struct oaie
{ int dist, cost; } a[n_max];
int H[n_max];
int N;
int n, d, l;
int sol;
inline bool mycmp( const oaie &a, const oaie &b)
{ return a.dist > b.dist; }
void citeste()
{
freopen(infile,"r",stdin);
scanf("%d %d %d",&n,&d,&l);
for(int i=1;i<=n;i++)
scanf("%d %d",&a[i].dist,&a[i].cost);
fclose(stdin);
}
void sift(int k)
{
int son = k, l = ls(k), r =rs(k);
if(l<=N && H[son] > H[l] )
son = l;
if(r<=N && H[son] > H[r] )
son = r;
if(son!=k)
{
swap(H[son], H[k]);
sift(son);
}
}
int get_max_heap()
{
int maxim = H[1];
H[1] = H[N--];
sift(1);
return maxim;
}
void percolate(int k)
{
while(k>1 && H[f(k)] > H[k] )
{
swap(H[k], H[f(k)]);
k = f(k);
}
}
void insert(int x)
{
H[++N] = x;
percolate(N);
}
void rezolva()
{
sort(a+1,a+n+1,mycmp);
for(int i=1;i<=n;i++)
{
if(!N)
{
insert(a[i].cost);
d-=l;
sol+=a[i].cost;
continue;
}
if(a[i].dist <= d)
{
insert(a[i].cost);
sol+=a[i].cost;
d-=l;
continue;
}
if(H[1] < a[i].cost)
{
sol-= get_max_heap();
sol+=a[i].cost;
insert(a[i].cost);
}
}
}
void afiseaza()
{
freopen(outfile,"w",stdout);
printf("%d\n",sol);
fclose(stdout);
}
int main()
{
citeste();
rezolva();
afiseaza();
return 0;
}