Pagini recente » Cod sursa (job #794179) | Cod sursa (job #15973) | Cod sursa (job #2524805) | Cod sursa (job #849653) | Cod sursa (job #3252919)
//
// main.cpp
// lupul urias si rau
//
// Created by Andrada Minca on 31.10.2024.
//
#include <bits/stdc++.h>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int n,c,p,i,siz,k,d,j,a,l,vcc,x,val,v[100005],dist[100005],poz[100005];
struct hp
{
int v;
int p;
} heap[100005];
void myswap(int a, int b)
{
swap(heap[a],heap[b]);
swap(poz[heap[a].p],poz[heap[b].p]);
}
void uper(int po)
{
while(heap[po].v>=heap[po/2].v&&po>1)
{
if((heap[po].v==heap[po/2].v&&dist[heap[po].p]>dist[heap[po/2].p])||heap[po].v>heap[po/2].v)
myswap(po,po/2);
po=po/2;
}
}
void downy(int p)
{
while(p*2<=siz)
{
int t=p*2;
if(p*2<siz && heap[p*2+1].v>heap[p*2].v)t++;
if(heap[p].v<heap[t].v){myswap(p,t);p=t;}
if(heap[p].v==heap[t].v&&dist[heap[p].p]<dist[heap[t].p]){myswap(p,t);p=t;}
else break;
}
}
void add(int val,int p)
{
siz++;
heap[siz]={val,p};
poz[p]=siz;
uper(siz);
}
void del(int p)
{
if(poz[p]==siz)siz--;
else
{
int x=poz[p];
myswap(poz[p],siz);
siz--;
uper(x);
downy(x);
}
}
int main() {
fin>>n>>x>>l;
x++;
for(i=1;i<=n;i++)
{
fin>>d>>a;
d++;
add(a,i);
dist[i]=d;
}
sort(v+1,v+n+1,greater<int>());
int s=0,cop=x;
while(x>=0)
{
int i=1,m=0;
vcc=0;
for(j=n;j>=1;j--)
{
if(dist[j]>x-l)vcc++;
else break;
}
while(i<=cop/l+vcc)
{
if(dist[heap[i].p]>m&&dist[heap[i].p]<=x&&dist[heap[i].p]>0)val=heap[i].v,m=dist[heap[i].p];
i++;
}
s+=val;
x-=l;
}
fout<<s;
return 0;
}