Pagini recente » Cod sursa (job #964788) | Cod sursa (job #971611) | Cod sursa (job #2206055) | Cod sursa (job #1779862) | Cod sursa (job #438592)
Cod sursa(job #438592)
#include<stdio.h>
#include <algorithm>
#include <list>
#include <map>
using namespace std;
#define min(a,b) (a < b)?(a):(b)
struct gutuie{
int h,g;
};
int getLevel(gutuie Gutuie, int H, int U){
if(H >= Gutuie.h)
return (1+getLevel(Gutuie,H-U,U));
return 0;
}
bool compare(const gutuie &g1, const gutuie &g2){
return g1.g > g2.g;
}
map<int, list<gutuie> > Gutui;
int countHeavier(int level, int nrNiv){
int i, counter=0;
for(i = level+1;i<nrNiv+1;i++){
list<gutuie>::iterator it;
for(it = (Gutui[i]).begin(); it != (Gutui[i]).end(); it++)
if((Gutui[level].front().g) < (*it).g)
counter++;
}
return counter;
}
int GMAX(int nrNiv, int N){
int i,chosen=0,gr = 0;
int numarGutui = (min(nrNiv,N));
for(i=1;i<nrNiv+1;i++){
if(i<=chosen)
i=chosen+1;
if(!Gutui[i].empty()){
if(i-chosen > countHeavier(i,nrNiv) || N==numarGutui){
gr += (Gutui[i].front().g);
Gutui[i].pop_front();
chosen++;
i--;
N--;
numarGutui--;
}
else
N-=Gutui[i].size();
}
}
return gr;
}
int main(){
int N,H,U,gr,nrNiv,i;
gutuie Gutuie;
FILE *f=fopen("gutui.in","r"), *g=fopen("gutui.out","w");
fscanf(f,"%i %i %i\n",&N,&H,&U);
nrNiv = H/U;
for(i=0;i<N;i++){
fscanf(f, "%i %i\n", &(Gutuie.h), &(Gutuie.g));
Gutui[getLevel(Gutuie,H,U)].push_front(Gutuie);
}
for(i=1;i<1+nrNiv;i++){
Gutui[i].sort(compare);
}
gr = GMAX(nrNiv, N);
fprintf(g,"%i", gr);
fclose(f);
fclose(g);
return 0;
}