Pagini recente » Cod sursa (job #588745) | Cod sursa (job #1832382) | Cod sursa (job #72398) | Monitorul de evaluare | Cod sursa (job #2912497)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <algorithm>
#include <cstring>
#include <iomanip>
using namespace std;
//ifstream f("in.in");
//ofstream g("out.out");
ifstream f("lupu.in");
ofstream g("lupu.out");
struct str{
int val;
int timp;
}v[100005];
int n,x,l,k=0;
int timpMax = -1;
int sol = 0;
int d,a;
int h[100005],hk=0;
bool cmp(str a,str b){
if(a.timp == b.timp){
return a.val>b.val;
}
return a.timp>b.timp;
}
int main(){
f>>n>>x>>l;
for(int i=1;i<=n;i++){
f>>d>>a;
if(d<=x){
k++;
v[k].timp = (x-d)/l + 1;
v[k].val = a;
timpMax = max(timpMax,v[k].timp);
}
}
sort(v+1,v+k+1,cmp);
int j=1;
for(int i=timpMax;i>=1;i--){
while(j<=k && v[j].timp == i){
///punere in heap
hk++;
h[hk] = v[j].val;
int tmp = hk;
while(tmp>1 && h[tmp] > h[tmp/2]){
swap(h[tmp],h[tmp/2]);
tmp/=2;
}
j++;
}
if(hk>0){
sol+=h[1];
///scoatere din heap
h[1] = h[hk];
hk--;
int p=1,c=2;
while(c<=hk){
if(h[c]<h[c+1] && c+1<=hk){
c++;
}
if(h[c]>h[p]){
swap(h[c],h[p]);
}else{
break;
}
p = c;
c = 2*p;
}
}
/*for(int y=1;y<=hk;y++){
cout<<h[y]<<" ";
}
cout<<'\n';*/
}
g<<sol;
f.close();
g.close();
return 0;
}