Cod sursa(job #569063)

Utilizator GrimpowRadu Andrei Grimpow Data 31 martie 2011 22:18:09
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.74 kb
#include<fstream>
#include<stdlib.h>
using namespace std;

struct valeu
{
    int gr;
    int nivel;
};

int aleluia(const void* x,const void* y)
{
    valeu t,u;
    t = *((valeu*)x);
    u = *((valeu*)y);
    return u.gr-t.gr;

}


int main()
{
    int poz[10000]={0},n,h,u,i,s,x[100][100],max1,a,b,j,z,max,k,y,aux,q,max2=0;
    valeu v[10000];
    int count[10000];
    ifstream f("gutui.in");
    f>>n>>h>>u;
    s=0;
    z=0;
    max1=0;

    for(i=0;i<n;i++)
       {
           f>>a>>b;
           if(a<h) x[(h-a)/u][poz[(h-a)/u]]=b;
           poz[(h-a)/u]++;
           if ((h-a)/u>max2) max2=(h-a)/u+1;
           if((h-a)/u>max1) max1=(h-a)/u;
       }
    f.close();
    for(i=0;i<=max1;i++)
       {
       for(j=0;j<=i&&j<poz[i];j++)
          {
              max=x[i][j];
              k=0;
          for(y=j+1;y<poz[i];y++)
             {
                 if(x[i][y]>max) {max=x[i][y]; k=y;}
             }
          if(k>0) {aux=x[i][j]; x[i][j]=max; x[i][k]=aux;}

          }
       }
/* de aici avem piramida de maximi pt fiecare nivel*/
    q=0;
    for(i=0;i<=max1;i++)
       for(j=0;j<=i&&j<poz[i];j++)
          if(x[i][j]!=0)
          {
          v[q].gr=x[i][j];
          v[q++].nivel=i;
          }
    /* qsort pe sir v */
    qsort(v,q,sizeof(valeu),aleluia);
    q=0;
   for(i=0;i<n&&q<max2;i++)
      {
          if(v[i].nivel>=(count[v[i].nivel]&&q-count[v[i].nivel]>max2   ) )
            {
                q++;
                s+=v[i].gr;
                for(j=v[i].nivel;j<max2;j++)
                   {
                       count[j]++;
                   }
            }
      }
ofstream g("gutui.out");
    g<<s;
g.close();










          }