Cod sursa(job #570074)

Utilizator GrimpowRadu Andrei Grimpow Data 2 aprilie 2011 14:15:20
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.88 kb
#include<fstream>
#include<stdlib.h>
using namespace std;

struct valeu
{
    long long 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,max1,a,b,j,z,max,k,y,aux,q,max2=0,min;
    int **x=new long long int *[5000];
    for(i=0;i<5000;i++)
       x[i] =new long long int [i+1];
    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 */
    min=-1;
    qsort(v,q,sizeof(valeu),aleluia);
   for(i=0;i<q&&min<max2;i++)
      {
          if(v[i].nivel>=count[v[i].nivel]&&v[i].nivel>min)
            {
                s+=v[i].gr;
                for(j=v[i].nivel;j<max2;j++)
                   {
                       count[j]++;
                   }
            }
          for(j=min+1;j<max2;j++)
             if(count[j]==j+1&&j>min)
              min=j;

      }
ofstream g("gutui.out");
    g<<s;
g.close();
}