Pagini recente » Cod sursa (job #882452) | Cod sursa (job #1362981) | Cod sursa (job #1692602) | Borderou de evaluare (job #2051227) | Cod sursa (job #1798820)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
if(pbuf==BUF_SIZE){
fread(buf, BUF_SIZE, 1, fi);
pbuf=0;
}
return buf[pbuf++];
}
inline long long nextnum(){
long long a=0;
char c=nextch();
while((c<'0' || c>'9') && c!='-')
c=nextch();
int semn=1;
if(c=='-'){
semn=-1;
c=nextch();
}
while('0'<=c && c<='9'){
a=a*10+c-'0';
c=nextch();
}
return a*semn;
}
#define MAXN 100000
class A{
public:
long long val[MAXN+1], val2[MAXN+1];
int pos[MAXN+1];
int heap[MAXN+1], last;
inline int Heap_father(int p){
return p/2;
}
inline int Heap_leftson(int p){
return 2*p;
}
inline int Heap_rightson(int p){
return 2*p+1;
}
inline int cmp(int p1, int p2){
if(val[heap[p1]]>val[heap[p2]] || (val[heap[p1]]==val[heap[p2]] && val2[heap[p1]]>val2[heap[p2]]))
return 1;
return 0;
}
inline void Heap_Swap(int p1, int p2){
pos[heap[p1]]=p2;
pos[heap[p2]]=p1;
int aux=heap[p1];
heap[p1]=heap[p2];
heap[p2]=aux;
}
inline void Heap_upheap(int p){
while(Heap_father(p)>0 && cmp(p, Heap_father(p))){
Heap_Swap(p, Heap_father(p));
p=Heap_father(p);
}
}
inline void Heap_downheap(int p){
int flag=1;
int ts=-1;
while(flag){
ts=-1;
if(Heap_leftson(p)>last)
flag=0;
else{
if(cmp(Heap_leftson(p), p))
ts=Heap_leftson(p);
if(Heap_rightson(p)<=last && cmp(Heap_rightson(p), Heap_leftson(p)) && cmp(Heap_rightson(p), p))
ts=Heap_rightson(p);
if(ts==-1)
flag=0;
else{
Heap_Swap(p, ts);
p=ts;
}
}
}
}
inline void Heap_insert(int poz){
heap[++last]=poz;
pos[poz]=last;
Heap_upheap(last);
}
inline void Heap_erase(int poz){
int p=pos[poz];
Heap_Swap(p, last);
last--;
if(Heap_father(p)>0 && cmp(p, Heap_father(p)))
Heap_upheap(p);
else
Heap_downheap(p);
}
} H1;
#define MAXN 100000
struct Oaie{
int d, a;
};
std::vector <Oaie> v[MAXN+1];
inline int min(int a, int b){
return a < b ? a : b;
}
int main(){
fi=fopen("lupu.in","r");
fo=fopen("lupu.out","w");
int n=nextnum();
int x=nextnum(), l=nextnum();
Oaie moarta;
for(int i=0;i<n;i++){
int d=nextnum(), a=nextnum();
if(d<=x){
int day=min(n, (x-d)/l+1);
//printf("%d ", day);
moarta.a=a;
moarta.d=day;
v[day].push_back(moarta);
}
}
int ind=0;
long long sum=0LL;
for(int i=n;i>0;i--){
for(int j=0;j<v[i].size();j++){
H1.val[++ind]=v[i][j].a;
H1.val2[ind]=v[i][j].d;
H1.Heap_insert(ind);
}
if(H1.last!=0){
sum+=H1.val[H1.heap[1]];
H1.Heap_erase(H1.heap[1]);
}
}
fprintf(fo,"%lld", sum);
fclose(fi);
fclose(fo);
return 0;
}