Pagini recente » Cod sursa (job #446640) | Cod sursa (job #393428) | Cod sursa (job #1981880) | Cod sursa (job #520766) | Cod sursa (job #463463)
Cod sursa(job #463463)
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <limits>
using namespace std;
const string in = "gutui.in";
const string out = "gutui.out";
class gutuie{
public:
//inaltime si valoare
unsigned int h,v;
bool operator< (const gutuie& p_gut) const{
return (v < p_gut.v);
}
bool operator<= (const gutuie& p_gut) const{
return (v < p_gut.v);
}
};
inline unsigned int clamp(unsigned int i, unsigned int n){return i<n?i:n;}
bool lessh(const gutuie& g1, const gutuie&g2){return g1.h < g2.h;}
bool lessv(const gutuie& g1, const gutuie&g2){return g1.v > g2.v;}
int main(){
ifstream str_in;
ofstream str_out;
str_in.open(in.c_str(), ifstream::in);
str_out.open(out.c_str(), ifstream::out);
unsigned int n,h,d;
//citeste datele din fisier
str_in>>n>>h>>d;
vector<gutuie> gut_vect(n);
for(unsigned int i = 0; i < n;++i){
str_in>>gut_vect[i].h>>gut_vect[i].v;
//daca inaltimea la care se afla o gutuie este mai mare decat
//inaltimea maxima, ignor-o
if(gut_vect[i].h > h){i--;n--;};
}
//ia in calcul gutuile ignorate
gut_vect.resize(n);
//sorteaza vectorul de gutui dupa inaltime
sort(gut_vect.begin(),gut_vect.end(),lessh);
priority_queue< gutuie > pr;
unsigned int w = 0;
//rezolva problema pentru inaltimi maxime alese astfel incat sa se
//poate culege 1,2..etc gutui
for(unsigned int i = (gut_vect[0].h) +( h -gut_vect[0].h ) % d ,j = 0; i <= h;){
//introdu intr-un heap toate gutuile cu inaltimea mai mica decat i
if(gut_vect[j].h <= i && j < n){
pr.push(gut_vect[j]);
j++;
continue;
}
//pentru intervalul [i-d,i], alege gutuia de valoare maxima
if(!pr.empty()){
w += pr.top().v;
pr.pop();
}
//creste copacul cu d
i += d ;
}
str_out<<w<<endl;
return 0;
}