Pagini recente » Cod sursa (job #353544) | Cod sursa (job #1457788) | Rating Cereteu Paul (Paul23232) | Cod sursa (job #963598) | Cod sursa (job #441457)
Cod sursa(job #441457)
#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);
}
i=0;
gut temporar;
temporar=v1.top();
//pozitionare pe prima gutuie disponibila (interval pozitiv)
while(temporar.interval >0) {
v1.pop();
i++;
}
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;
}