Cod sursa(job #2498406)

Utilizator eusebiu_alexandruMorar Eusebiu eusebiu_alexandru Data 23 noiembrie 2019 21:09:57
Problema Lupul Urias si Rau Scor 4
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<fstream>
#include<algorithm>
#define nmax 100005
using namespace std;
ifstream f ("lupu.in");
ofstream g ("lupu.out");
int  heap[nmax],i,j,n,m,x,l,distanta,lana,cnt,deficit;
unsigned long long sol;
void percolate(int  k)
{
  int  tata=k-1;
  while(k>1 && heap[tata]<heap[k])
  {
      swap(heap[tata],heap[k]);
      k=tata;
      tata=k-1;
  }
}
void sift (int  k)
{
    int fiu=1;
  while(fiu)
  {
    fiu=0;
   if(k+1<=n)
       fiu=k+1;
   if(heap[k]>heap[fiu])
         fiu=0;
   else
   {
       swap(heap[k],heap[fiu]);
       k=fiu;
   }
  }
}
struct ele
{

    int  lana,distanta;

}oaie[nmax];
bool cmp(ele a,ele b)
{
    return a.distanta>b.distanta;
}
int main()
{
 f>>n>>x>>l;
 for(i=1;i<=n;i++)
 {
     f>>distanta>>lana;
     if(distanta<=x)
     {
         oaie[++cnt].distanta=(x-distanta)/l+1;
         oaie[cnt].lana=lana;
     }
 }
 sort(oaie+1,oaie+cnt+1,cmp);
int tmax=oaie[1].distanta,pos=1,ok=0;
n=0;
while(tmax!=0 && pos<=cnt)
{
   while(tmax==oaie[pos].distanta && pos<=cnt)
   {
      if(deficit)
      {
          heap[1]=oaie[pos].lana;
          percolate(1);
          deficit=0;
      }
      else
      {
         n++;
          heap[n]=oaie[pos].lana;
          percolate(n);
          
      }
    pos++;
   }
      if(n!=0)
      {
       sol+=heap[1];
       deficit=n-1;
      }
      else
        deficit=0;
  tmax--;
}
g<<sol;
}