Cod sursa(job #438592)

Utilizator mihaiticamihaitica mihaitica Data 10 aprilie 2010 21:30:09
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.74 kb
#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;
}