Cod sursa(job #2637718)

Utilizator euyoTukanul euyo Data 24 iulie 2020 14:56:15
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin( "lupu.in" );
ofstream fout( "lupu.out" );

const int MaxN = 100001;

int d[MaxN], l[MaxN], ind[MaxN], lg[MaxN];
long long t[MaxN], heap[MaxN];

int indH;
 
static inline int fth( int node ) {
  return (node >> 1);
}
static inline int lSon( int node ) { 
  return (node << 1);
}
static inline int rSon( int node ) {
  return ((node << 1) + 1);
}
void swap( int a, int b ) {
  long long aux;
 
  aux = heap[a];
  heap[a] = heap[b];
  heap[b] = aux;
}
void repairUpp( int node ) {
  while ( node > 1 && heap[node] > heap[fth( node )] ) {
	swap( node, fth( node ) );
	node = fth( node );
  }
}
void repairDown( int node ) { 
  int son;	
 
  while ( node < indH ) {
	if ( lSon( node ) <= indH && rSon( node ) <= indH ) {
      if ( heap[lSon( node )] > heap[rSon( node )] ) {
        son = lSon( node );
	  } else {
		son = rSon( node );
	  }
	} else if ( lSon( node ) > indH && rSon( node ) <= indH ) {
	  son = rSon( node );
	} else if ( rSon( node ) > indH && lSon( node ) <= indH ) {
	  son = lSon( node );
	} else {
	  son = indH + 1;
	}
    if ( son <= indH && heap[son] > heap[node] ) {
      if ( son <= indH ) {
		swap( son, node );
	    node = son;
	  } else {
		node = indH + 1;
	  }
	} else {
	  node = indH + 1;
	}	
  }
}
void add( long long value ) {
  ++indH;
  heap[indH] = value;
  repairUpp( indH );
}
void cutMax() {
  swap( indH, 1 );
  --indH;
  repairUpp( 1 );
  repairDown( 1 );
}

int cmp( int a, int b ) {
  return t[a] > t[b];
}

int main() {
  int n, range, dist, i, k;
  long long maxl;
  
  fin >> n >> range >> dist;
  k = 0;
  for ( i = 0; i < n; ++i ) {
	fin >> d[i] >> l[i];
	if ( range >= d[i] ) {
      t[k] = (range - d[i]) / dist + 1;
	  ind[k] = k;
	  lg[k] = l[i];
      ++k;
	}
  }
  sort( ind, ind + k, cmp ); 
  maxl = 0;
  add( lg[ind[0]] );  
  for ( i = 1; i < k; ++i ) {
	if ( t[ind[i]] < t[ind[i - 1]] ) {
      for ( int j = 0; j < t[ind[i - 1]] - t[ind[i]]; ++j ) {
		if ( indH > 0 ) {
	      maxl += heap[1];
	      cutMax();
		}
	  }
	}
	add( lg[ind[i]] );
  }
  maxl += heap[1];
  fout << maxl;
  fin.close();
  fout.close();
  return 0;
}