Pagini recente » Cod sursa (job #1148872) | Cod sursa (job #2573764) | Cod sursa (job #2364558) | Cod sursa (job #522036) | Cod sursa (job #439845)
Cod sursa(job #439845)
Utilizator |
HighScore skyel |
Data |
11 aprilie 2010 19:53:25 |
Problema |
Gutui |
Scor |
100 |
Compilator |
cpp |
Status |
done |
Runda |
teme_upb |
Marime |
2.54 kb |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 0x7fffffff
#define in "gutui.in"
#define out "gutui.out"
#include <functional>
#include <queue>
#include <vector>
using namespace std;
typedef struct
{
int h;
int g;
int coef;
}pom;
int compare2(const void *a,const void *b) //compare pentru sortare dupa greutate
{
pom *x,*y;
x=(pom*)a;
y=(pom*)b;
return -x->g + y->g;
}
int compare(const void* a,const void* b) //compare pentru sortare dupa inaltime
{
pom *x,*y;
x=(pom*)a;
y=(pom*)b;
if (x->coef != y->coef)
return x->coef-y->coef;
else
return -x->g+y->g;
}
int main()
{
int n,i,max_height,up_height,taken,sum=0;
vector<int> heap;
pom *gutui;
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%d %d %d",&n,&max_height,&up_height);
gutui=(pom*)malloc(n*sizeof(pom));
for (i = 0; i < n; ++i)
{
scanf("%d %d",&gutui[i].h,&gutui[i].g);
gutui[i].coef=(max_height-gutui[i].h)/up_height+1; /* un coeficient pentru a "rotunji" inaltimile pana la
ordinul care are relevanta pentru problema */
if( gutui[i].h > max_height ) //elimin gutuile la care nu se poate ajunge din start
{
i--;
n--;
}
}
make_heap (heap.begin(),heap.end()); //STL::HEAP
qsort(gutui,n,sizeof(pom),compare);
taken=0;
for ( i = 0; i < n; ++i)
{
if (taken < gutui[i].coef) //daca pot sa iau gutuia fara modificari la solutia anterioara
{
taken++;
heap.push_back(INF - gutui[i].g); push_heap (heap.begin(),heap.end());
}
else
{ //modificam solutia anterioara incat sa fie cea mai buna
if (gutui[i].g > (INF - heap.front()))
{
pop_heap (heap.begin(),heap.end());
heap.pop_back();
heap.push_back(INF - gutui[i].g);
push_heap (heap.begin(),heap.end());
}
}
}
for ( i = 0; i < heap.size(); ++i) //calculul greutatii finale
{
sum+=INF - heap[i];
}
printf("%u\n",sum);
return 0;
}