Pagini recente » Cod sursa (job #2633047) | Cod sursa (job #1858256) | Cod sursa (job #1896641) | Cod sursa (job #435096) | Cod sursa (job #441410)
Cod sursa(job #441410)
#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 sortare(gut x,gut y){
return ( x.interval<y.interval );
};
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;
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++;
v.push_back(g);
}
stable_sort(v.begin(),v.end(),sortare);
for (i=0; i<v.size(); i++){
cout << v[i].greutate << " " << v[i].interval << endl;
}
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){
printf("greu %d\n",v[i].greutate);
minheap.push(v[i].greutate);
i++;
}
else {
while(minheap.size() > rang)
minheap.pop();
rang=v[i].interval;
}
printf("size=%d ",minheap.size());
}
while(minheap.size() > rang)
minheap.pop();
while(minheap.size() > 0) {
max = max + minheap.top();
minheap.pop();
}
fprintf(out,"%d",max);
return 0;
}