Pagini recente » Cod sursa (job #34326) | Cod sursa (job #826484) | Cod sursa (job #2924496) | Cod sursa (job #434292) | Cod sursa (job #437479)
Cod sursa(job #437479)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
class Gutuie{
public:
unsigned int greutate, nivel;
};
//functie de comparare sortare initiala
bool comp1(Gutuie a, Gutuie b){
if( a.nivel < b.nivel )
return false;
else
if( a.nivel == b.nivel ){
if( a.greutate > b.greutate )
return true;
else
return false;
}
else
return true;
}
//functie de comparare heap
bool comp2(unsigned int a, unsigned int b){
return a > b;
}
//calcul nivel pentru inaltimea a
inline unsigned int nivel( unsigned int a, unsigned int u, unsigned int hmax ){
return a % u <= hmax % u ? a / u : a / u + 1;
}
int main(){
unsigned int n, u, hmax;
ifstream fin("gutui.in");
ofstream fout("gutui.out");
//citire date intrare
fin >> n >> hmax >> u;
unsigned int i, x, y;
vector<Gutuie> v(n);
for(i = 0; i < n; i++){
fin >> x >> y;
v[i].greutate = y;
v[i].nivel = nivel(x, u, hmax);
}
//sortare
sort( v.begin(), v.end(), comp1 );
unsigned int nivmax = nivel(hmax, u, hmax), niv = v[0].nivel, nr = 0;
unsigned int gmax = 0;
vector<unsigned int> greutate;
//incepem sa culegem de la nivelul cel mai apropiat de hmax la cel mai de jos
for(i = 0; i < n; i++){
if( v[i].nivel == niv ){
if( nr < nivmax - niv + 1 ){
nr ++;
//mai putem sa culegem gutui
if( greutate.size() < nivmax - niv + 1 ){
gmax += v[i].greutate;
greutate.push_back( v[i].greutate );
push_heap( greutate.begin(), greutate.end(), comp2 );
}
else
//trebuie sa inlocuim gutui culese
if( greutate.front() < v[i].greutate ){
gmax -= greutate.front();
gmax += v[i].greutate;
pop_heap( greutate.begin(), greutate.end(), comp2 );
greutate.pop_back();
greutate.push_back( v[i].greutate );
push_heap( greutate.begin(), greutate.end(), comp2 );
}
}
}
else{
//trecem la urmatorul nivel
niv = v[i].nivel;
nr = 0;
i --;
}
}
//afisam greutatea maxima
fout << gmax;
fin.close();
fout.close();
return 0;
}