Cod sursa(job #2099820)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 4 ianuarie 2018 18:33:13
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#define x first
#define y second
#define MAX 100001
#define VMAX 10000000000

using namespace std;
typedef long long ll;

ll n,X,l,heap[MAX],sz,ans,nrp,ds,na;
pair<ll,ll> a[MAX];
void adauga(ll ind){
  sz++;
  heap[sz]=a[ind].y;
  ll ii=sz;
  while(sz/2>0&&heap[sz/2]<heap[sz])swap(heap[sz],heap[sz/2]),sz/=2;
}
void elimina(){
  ans+=heap[1];
  heap[1]=heap[sz];sz--;
  ll ii=1;
  while(ii*2<=sz){
    ds=0;
    if(heap[ii]<heap[ii*2])ds=ii*2;
    if(ii*2+1<=sz&&heap[ii]<heap[ii*2+1]&&heap[ii*2+1]>heap[ii*2])ds=ii*2+1;
    if(ds==0)break;
    swap(heap[ii],heap[ds]);
    ii=ds;
  }
}
void afiseaza(int st,int dr){
  if(st>sz)return;
  for(int ii=st;ii<=dr&&ii<=sz;ii++)cout<<heap[ii]<<" ";
  cout<<'\n';
  afiseaza(st*2,dr*2+1);
}

int main()
{
    ifstream f ("lupu.in");
    ofstream g ("lupu.out");
    f>>n>>X>>l;
    for(int i=1;i<=n;i++){
      f>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1);na=1;nrp=VMAX;
    for(int i=1;nrp>=0&&i<=n;i++){
      nrp=min(nrp,(X-a[i].x)/l);
      for(;na<=n&&a[na].x+nrp*l<=X;na++)adauga(na);
      //afiseaza(1,1);cout<<"--------\n";
      if(sz>=0){
        elimina();
        nrp--;
        //i=na;
      }
    }
    g<<ans;
    f.close ();
    g.close ();
    return 0;
}