Pagini recente » Cod sursa (job #2656202) | Cod sursa (job #2928194) | Cod sursa (job #2155601) | Borderou de evaluare (job #1010306) | Cod sursa (job #640674)
Cod sursa(job #640674)
#include<cstdio>
#include<vector>
#include<algorithm>
#define infile "lupu.in"
#define outfile "lupu.out"
#define n_max 100005
#define INF 1 << 30
#define ls(i) i<<1
#define rs(i) (i<<1) + 1
#define f(i) i>>1
#define mkp make_pair
#define pii pair<int,int>
using namespace std;
vector < pii > H(1);
int N, D, L;
int sol;
void sift(int);
void citeste()
{
freopen(infile,"r",stdin);
scanf("%d %d %d",&N,&D,&L);
int x,y;
H.reserve(n_max);
for(int i=1;i<=N;i++)
{
scanf("%d %d",&x,&y);
H.push_back(mkp(y,x));
}
fclose(stdin);
}
pii get_max_heap()
{
pii maxim = H[1];
H[1] = H[N--];
sift(1);
return maxim;
}
int cmp(pii x, pii y)
{
if(x.first < y.first)
return 1;
if(x.first == y.first)
if(x.second < y.second)
return 1;
return 0;
}
void sift(int k)
{
int son = k, l = ls(k), r =rs(k);
if(l<=N && cmp(H[son],H[l]))
son = l;
if(r<=N && cmp(H[son],H[r]))
son = r;
if(son!=k)
{
swap(H[son], H[k]);
sift(son);
}
}
void percolate(int k)
{
while(k>1 && cmp(H[f(k)],H[k]) )
{
swap(H[k], H[f(k)]);
k = f(k);
}
}
void build_heap()
{
for(int i = N/2; i; i--)
sift(i);
}
void rezolva()
{
build_heap();
pair < int, int > nodc;
int dist = 0;
while(N)
{
nodc = get_max_heap();
if(nodc.second + dist > D)
continue;
sol += nodc.first;
dist += L;
}
}
void afiseaza()
{
freopen(outfile,"w",stdout);
printf("%d\n",sol);
fclose(stdout);
}
int main()
{
citeste();
rezolva();
afiseaza();
return 0;
}