Cod sursa(job #434710)

Utilizator lucicanuAndrei-Lucian Croitoru lucicanu Data 6 aprilie 2010 14:19:12
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2.4 kb
# include <fstream>
# include <vector>
# include <algorithm>
# include <list>

# define MAXL 100000

using namespace std;

typedef struct gut{
               int h;
               int v;
               int p;
               }Gutuie;

bool compare(Gutuie a, Gutuie b){
    //Gutuie *aa = (Gutuie*)a;
    //Gutuie *bb = (Gutuie*)b;
    if (a.p < b.p)
       return false;
    else
        if (a.p > b.p)
           return true;
        else
            if (a.v < b.v)
               return true;
            else
                return false;
}




int main(){
    int n, H, U, i, j, nsol, pas, s, k, l;
    Gutuie x;
    list <int> sol;
    list <int>::iterator it;
    vector <Gutuie> g;
    fstream fin, fout;
    fin.open("gutui.in",ios::in);
    fout.open("gutui.out",ios::out);
    
    fin>>n>>H>>U;
    for (i=0;i<n;i++){
        //fscanf(fin,"%d%d",&g[i].h,&g[i].v);
        fin>>x.h>>x.v;
        x.p = (H - x.h)/U + 1;
        g.push_back(x);
    }
    
    sort(g.begin(), g.end(), compare);
    
    nsol = 0;
    for (i=0;i<n;i++){
        if (i==0 || g[i].p != g[i-1].p){ //pasul urmator;
           pas = g[i].p;
           for (j=i;j<n && g[j].p == pas && j-i<pas;j++){//parcurg gutuile de la pasul curent(sunt in ordine descrescatoare;
               if (nsol<pas){
                  //inserez pe g[j].v in vectorul sol a.i. sa ramana sortat descrescator;
                  //for (k=0;k<nsol;k++)
                  for (it = sol.begin(), k=0;k<nsol;++k,++it)  
                      if (*it<g[j].v)
                         break;
                  sol.insert(it,g[j].v);
                  nsol++;
               }
               else{
                    if (g[j].v > sol.back()){
                       //elimin ultimul element din sol si inserez pe g[j].v;
                       for (k=0, it = sol.begin();k<nsol;++k, ++it)
                           if (*it<g[j].v)
                              break;
                       //for (l=nsol;l>k;l--)
                       //   sol[l] = sol[l-1];
                       //sol[l] = g[j].v;
                       sol.insert(it,g[j].v);
                    }
               }
           }
        }
    }
    s = 0;
    for (it = sol.begin();it!=sol.end();++it)
        s+=*it;
    //fprintf(fout,"%d\n",s);   
    fout<<s<<"\n";
    fin.close();
    fout.close();
    return 0;              
}