Pagini recente » Cod sursa (job #569174) | Cod sursa (job #1484004) | Cod sursa (job #2204707) | Cod sursa (job #794169) | Cod sursa (job #440017)
Cod sursa(job #440017)
//Lecu Marina 322CB
// TEMA 1 - Problema 2
#include <stdio.h>
#include <stdlib.h>
//#include<conio.h>
#include <algorithm>
using namespace std;
#include <map>
using namespace std;
#include <vector>
using namespace std;
typedef struct
{
unsigned int h,g;
} TGutuie;
bool compg(const TGutuie &g1,const TGutuie &g2)
{
return g1.g < g2.g;
}
bool comph(const TGutuie &g1,const TGutuie &g2)
{
return g1.h > g2.h;
}
bool compg2(const unsigned int &g1,const unsigned int &g2)
{
return g1 > g2;
}
int main()
{
unsigned int N,H,U,G=0,i,nculese=0;
FILE *in,*out;
TGutuie* gutui;
vector<unsigned int> culese;
vector<unsigned int>::iterator it;
in=fopen("gutui.in","r");
out=fopen("gutui.out","w");
fscanf(in,"%u %u %u",&N,&H,&U); //citire N,H,U
gutui = (TGutuie*) malloc(N*sizeof(TGutuie)); //alocare vector gutui
//citire inaltimi si greutati gutui
for(i=0; i<N; i++)
{
fscanf(in,"%u %u",&(gutui[i].h),(&gutui[i].g));
if(gutui[i].h > H)
{
i--;
N--;
continue;
}
gutui[i].h = H - U *((H-gutui[i].h)/U);
//niv.nmax = (H - gutui[i].h)/U +1;
}
sort(gutui,gutui+N,comph); //sortare in ordine descrescatoare dupa inaltime
make_heap(culese.begin(),culese.end(),compg2);
for(i=0; i < N; i++)
{
//printf("h:%u g:%u\n",gutui[i].h,gutui[i].g);
if(nculese < (H - gutui[i].h)/U +1) //daca mai putem culege de pe nivelul curent
{
culese.push_back(gutui[i].g);
push_heap(culese.begin(),culese.end(),compg2); //inseram in heap
nculese++; // crestem nr de gutui culese
}
else // nu mai putem culege decat daca renuntam la una anterioara
{
if(*(culese.begin()) < gutui[i].g)
{
pop_heap(culese.begin(),culese.end(),compg2);
culese.pop_back();
culese.push_back(gutui[i].g);
push_heap(culese.begin(),culese.end(),compg2);
}
}
/* printf("heap: ");
for(it=culese.begin(); it!=culese.end(); it++)
{
printf("%u ",*it);
}
printf("\n");
*/
}
//calcul suma greutati
for(it=culese.begin(); it!=culese.end(); it++)
{
G+= *it;
}
// printf("G: %u",G);
// getch();
fprintf(out,"%u",G);
fclose(in);
fclose(out);
return 0;
}