Pagini recente » Cod sursa (job #3174564) | Rating Didii Theodor-Cosmin (cosmin1123) | Cod sursa (job #240184) | Monitorul de evaluare | Cod sursa (job #745235)
Cod sursa(job #745235)
#include<cstdio>
#include<vector>
#include<algorithm>
#define NMAX 100005
#define maxim(a,b) ((a>b)?(a):(b))
#define lastm(d) ((X-d)/L+1)
#define go(x,y,v) (v.push_back(make_pair(x,y)))
using namespace std;
int H[NMAX];
int N,X,L,Tmax,n;
int S;
vector < pair < int , int > > oaie;
inline int father(int nod)
{
return nod>>1;
}
inline int left_son(int nod)
{
return nod<<1;
}
inline int right_son(int nod)
{
return (nod<<1)+1;
}
void swap(int i, int j)
{
int aux;
aux=H[i];
H[i]=H[j];
H[j]=aux;
}
void percolate(int i)
{
while(i>1 && H[i]>H[father(i)])
{
swap(i,father(i));
i=father(i);
}
}
void sift(int n, int i)
{
int son;
do
{
son=0;
if(left_son(i)<=n)
{
son=left_son(i);
if(right_son(i)<=n && H[son]<H[right_son(i)])
son=right_son(i);
if(H[son]<=H[i])
son=0;
}
if(son)
swap(i,son);
i=son;
}while(son);
}
void insert(int i)
{
H[++n] = i;
percolate(n);
}
void cut(int i)
{
swap(i,n);
n--;
sift(n,i); // pentru ca nu vom elimina decat elementul maxim, nu va fi necesar percolade()
}
void citire()
{
freopen("lupu.in","r",stdin);
scanf("%d %d %d",&N,&X,&L);
int i,d,l;
for(i=1;i<=N;i++)
{
scanf("%d %d",&d,&l);
go(lastm(d),l,oaie);
}
}
void BVO()
{
sort(oaie.begin()+1,oaie.end());
reverse(oaie.begin()+1,oaie.end());
int j,i;
for(j=oaie[1].first,i=1;j;j--)
{
for(;oaie[i].first>=j && i<=N;i++)
insert(oaie[i].second);
if(n)
{
S+=H[1];
cut(1);
}
}
}
void afisare()
{
freopen("lupu.out","w",stdout);
printf("%d",S);
}
int main()
{
go(0,0,oaie);
citire();
BVO();
afisare();
return 0;
}