Pagini recente » Cod sursa (job #1778958) | Cod sursa (job #1152098) | Cod sursa (job #2299401) | Istoria paginii runda/ionut | Cod sursa (job #441450)
Cod sursa(job #441450)
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
class gut{
public:
int interval;
int greutate;
};
//pentru transformarea priority_queue in minheap
class mycomparison{
public:
bool operator() (const int& a, const int& b) const{
return (a > b);
}
};
bool operator<(const gut &x,const gut &y){
return ( x.interval<y.interval );
}
// bool operator<(const Thread &a, const Thread &b)
// {
// return a.getpriority() < b.getpriority();
// }
int main(){
FILE *in=fopen("gutui.in","rt");
FILE *out=fopen("gutui.out","wt");
int n,h,u;
int inaltime;
int greu;
int i,rang,max = 0;
fscanf(in,"%d %d %d",&n,&h,&u);
vector<gut> v;
gut g;
priority_queue<int,vector<int>,mycomparison> minheap;
priority_queue<gut> v1;
for (i = 0;i < n;i++){
fscanf(in,"%d %d",&inaltime,&greu);
g.greutate=greu;
g.interval = (h - inaltime) / u;
if (g.interval >= 0)
g.interval++;
g.interval=-g.interval;
v1.push(g);
}
/*while(v1.size()>0){
printf("%d \n",v1.top().interval);
v1.pop();
}*/
i=0;
//pozitionare pe prima gutuie disponibila (interval pozitiv)
// while(v[i].interval < 0)
// i++;
gut temporar;
temporar=v1.top();
rang = -temporar.interval;
printf("**rang=%d ",rang);
while (i < n){
temporar=v1.top();
temporar.interval=-temporar.interval;
if (temporar.interval == rang){
printf("greu %d\n",temporar.greutate);
minheap.push(temporar.greutate);
i++;
v1.pop();
}
else {
while(minheap.size() > rang)
minheap.pop();
rang=temporar.interval;
}
printf("rang=%d ",rang);
}
while(minheap.size() > rang)
minheap.pop();
while(minheap.size() > 0) {
max = max + minheap.top();
minheap.pop();
}
fprintf(out,"%d",max);
return 0;
}