Pagini recente » Cod sursa (job #1648088) | Cod sursa (job #774251) | Cod sursa (job #1772875) | Cod sursa (job #971393) | Cod sursa (job #439325)
Cod sursa(job #439325)
//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;
typedef struct
{
unsigned int nmax,nluate;
} Nivel;
typedef struct
{
unsigned int h,g;
} TGutuie;
bool compg(const TGutuie &g1,const TGutuie &g2)
{
return g1.g > g2.g;
}
bool comph(const map<unsigned int,Nivel>::iterator it1,const map<unsigned int,Nivel>::iterator it2)
{
return it1->first > it2->first;
}
int main()
{
unsigned int N,H,U,G=0,i,ntotal,hmin;
short c=1;
FILE *in,*out;
TGutuie* gutui;
map<unsigned int,Nivel> nivele;
map<unsigned int,Nivel>::iterator it,it2;
Nivel niv;
niv.nluate=0;
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 % U != 0)
gutui[i].h = gutui[i].h - gutui[i].h % U + U;
niv.nmax = (H - gutui[i].h)/U +1;
//printf("%u: %u \n",gutui[i].h,niv.nmax);
nivele[gutui[i].h]=niv;
if(c)
{
hmin=gutui[i].h;
c=0;
}
else if(hmin > gutui[i].h)
hmin = gutui[i].h;
}
sort(gutui,gutui+N,compg); //sortare in ordine descrescatoare dupa greutate
ntotal = (H - hmin)/U +1; //nr total de gutui care pot fi culese
for(i=0; i < N; i++)
{
if(ntotal==0) break; //am cules toate gutuile pe care le puteam culege
it=nivele.find(gutui[i].h);
if(it->second.nluate < it->second.nmax) //putem culege gutuia
{
c=1;
for(it2 = nivele.begin(); it2 !=it; it2++)
if(it2->second.nluate+1 > it2->second.nmax)
{
c=0;
break;
}
if(c)
{
G += gutui[i].g;
ntotal--;
(it->second.nluate)++;
for(it2 = nivele.begin(); it2 !=it; it2++)
(it2->second.nluate)++;
/*it++;
for(it2 = it; it2 != nivele.end(); it2++)
(it2->second.nmax)--;*/
}
}
}
/* //afisare date citite
printf("%u %u %u\n",N,H,U);
for(i=0; i<N; i++)
printf("%u %u\n",gutui[i].h,gutui[i].g);
getch();
for(it=nivele.begin(); it!=nivele.end(); it++)
{
printf("\n%u %u\n",it->first,it->second.nmax);
}
getch();
*/
fprintf(out,"%u",G);
fclose(in);
fclose(out);
return 0;
}