Pagini recente » Cod sursa (job #1784602) | Cod sursa (job #2442207) | Cod sursa (job #1617977) | Cod sursa (job #1331381) | Cod sursa (job #437355)
Cod sursa(job #437355)
#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{
//if(h == p_gut.h){return v < p_gut.v;}
return (v < p_gut.v);
}
bool operator<= (const gutuie& p_gut) const{
//if(h == p_gut.h){return v < p_gut.v;}
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;
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;
if(gut_vect[i].h > h){i--;n--;};
}
gut_vect.resize(n);
sort(gut_vect.begin(),gut_vect.end(),lessh);
for(unsigned int i = 0; i < n;++i){
//cout<<gut_vect[i].h<<" "<<gut_vect[i].v<<endl;
}
priority_queue< gutuie > pr;
//if((gut_vect[n-1].h)%d == 0){h++;}
unsigned int w = 0;
for(unsigned int i = ((gut_vect[0].h)/d) * d,j = 0; i <= h;){
//cout<<j<<" "<<i<<" "<<i+d<<endl;//" "<<gut_vect[j].h<<endl;
if(gut_vect[j].h <= i && j < n){
//cout<<"*Inserting "<<gut_vect[j].h<<" "<<gut_vect[j].v<<endl;
pr.push(gut_vect[j]);
j++;
continue;
}
if(!pr.empty()){
//cout<<"*Extracting "<<pr.top().h<<" "<<pr.top().v<<endl;
w += pr.top().v;
pr.pop();
}
//else{break;};
i += d ;
}
str_out<<w<<endl;
//<<rez[n-1].first<<endl;
return 0;
}