Pagini recente » Cod sursa (job #2048573) | Cod sursa (job #2583170) | Cod sursa (job #1226764) | Cod sursa (job #2486798) | Cod sursa (job #440007)
Cod sursa(job #440007)
#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;
typedef struct gutuie{
int interval;
int g;
}gutuie;
//pentru transformarea priority_queue in minheap
class mycomparison{
public:
bool operator() (const int& a, const int& b) const{
return (a > b);
}
};
//pentru qsort
int sortare(const void * x,const void * y){
gutuie *temp1=(gutuie*)x;
gutuie *temp2=(gutuie*)y;
return ( temp1->interval - temp2->interval );
};
int main(){
FILE *in=fopen("gutui.in","rt");
FILE *out=fopen("gutui.out","wt");
int n,h,u;
int inaltime;
int i,rang,max = 0;
gutuie v[110000];
fscanf(in,"%d %d %d",&n,&h,&u);
priority_queue<int,vector<int>,mycomparison> minheap;
for (i = 0;i < n;i++){
fscanf(in,"%d %d",&inaltime,&v[i].g);
v[i].interval = (h - inaltime) / u;
}
for (i = 0;i < n;i++)
if (v[i].interval >= 0)
v[i].interval++;
qsort(v,n,sizeof(gutuie),sortare);
i=0;
//pozitionare pe prima gutuie disponibila (interval pozitiv)
while(v[i].interval < 0)
i++;
rang = v[i].interval;
while (i < n){
if (v[i].interval == rang){
minheap.push(v[i].g);
i++;
}
else {
while(minheap.size() > rang)
minheap.pop();
rang=v[i].interval;
}
}
while(minheap.size() > rang)
minheap.pop();
while(minheap.size() > 0) {
max = max + minheap.top();
minheap.pop();
}
fprintf(out,"%d",max);
return 0;
}