Cod sursa(job #578504)

Utilizator GrimpowRadu Andrei Grimpow Data 11 aprilie 2011 12:37:24
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.45 kb
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

struct vai
{
       long long int niv,gr;
};
int comp(const void* x,const void* y)
{
 vai t=*((vai*)x);
 vai r=*((vai*)y);
 if(r.niv==t.niv)
  return r.gr-t.gr;
 else
  return t.niv-r.niv;
}

void stanga(long long int a[],long long int n,long long int h)
{
    int i;
    for(i=1;n>a[i]&&i<h;i++)
       a[i-1]=a[i];
    a[i-1]=n;


}

void dreapta(long long int a[],long long int n,long long int h)
{
    int i;
    for(i=h-1;n<a[i]&&i>0;i--)
       a[i+1]=a[i];
    a[i+1]=n;


}



int main()
{
  long long int s,a[100055],h,u,j,i,n,b,min,y=0,q;
  vai *v=new vai [100055];
  FILE *f=fopen("gutui.in","rt");
  fscanf(f,"%lli%lli%lli",&n,&h,&u);
  for(i=0;i<n;i++)
  {
                  fscanf(f,"%lli%lli",&q,&b);
                  if(u!=0) v[i].niv=(h-q)/u;
                  else v[i].niv=i;
                  v[i].gr=b;
  }
  fclose(f);
  h=0;
  qsort(v,n,sizeof(vai),comp);
  for(i=0;i<n;i++)
  {
       if(v[i].niv>=h)
         dreapta(a,v[i].gr,h);
       else
       if(v[i].gr>a[0]) stanga(a,v[i].gr,h);


       {
            min=a[0];
            y=0;
            for(j=0;j<h;j++)
               if(a[j]<min) {min=a[j]; y=j;}
            if(v[i].gr>min) a[y]=v[i].gr;
       }
  }
  s=0;
  for(i=0;i<h;i++)
     s+=a[i];
  FILE *g=fopen("gutui.out","wt");

  fprintf(g,"%lli",s);
  fclose(g);
   return 0;
}