Cod sursa(job #1404237)

Utilizator azkabancont-vechi azkaban Data 27 martie 2015 22:25:19
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<bits/stdc++.h>
using namespace std;
const int Max=100005;
int h[Max],hp,hc;
int n,l,H,i,j,gr;
int tmax(0),x;
long long cost(0); 
struct gutui 
         {
          int time;
          int weight;
		 } G[Max];

bool cmp(const gutui &i,const gutui &j)
 {
  return (i.time>j.time);
 }       
 
void upheap(int nod)
 {
 int tata=nod/2;
 if (!tata) return ;
 if (tata>=1 && h[nod]>h[tata])
     {
      swap(h[nod],h[nod/2]);
      upheap(tata);
     }              
 }

void downheap(int nod)
 {
 int fiu=2*nod;
 if (fiu>hp) return ;
 if (fiu<hp && h[fiu+1]>h[fiu]) ++fiu;
 if (h[fiu]<=h[nod]) return ;
 swap(h[nod],h[fiu]);
 downheap(fiu);               
 }

void sterge()
{
 h[1]=h[hp--];  
 downheap(1);  
 return ; 
}

void add_Heap(int value)
{
 h[++hp]=value;
 upheap(hp);
 return ;
}
 
int main(void)
 {
  ifstream cin("lupu.in");
  ofstream cout("lupu.out");
  cin>>n>>H>>l;
  for(i=1;i<=n;++i)
  {
   cin>>hc>>gr;
   int timp=(H-hc)/l;
   G[i]={timp,gr};
   tmax=max(tmax,timp);          
  }
  sort(G+1,G+n+1,cmp); 
  for (i=1,j=tmax;j>=0;--j)
    {
     while(G[i].time==j && i<=n)
	     { 
		 add_Heap(G[i].weight);    
		 ++i; 
		 }       
     if(hp)     
        {
         cost+=h[1];  
         sterge();
        }              
    }
 cout<<cost;            
 return 0;   
}