Cod sursa(job #2809414)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 26 noiembrie 2021 22:40:56
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
// Mihai Priboi

#include <stdio.h>
#include <iostream>
#include <algorithm>

// heap

#define MAXN 100000

inline int parent( int ind ) { return (ind - 1) / 2; }
inline int left_child( int ind ) { return ind * 2 + 1; }
inline int right_child( int ind ) { return ind * 2 + 2; }

int heap[MAXN];
int heap_size;

void upHeap( int nod ) {
  if( nod > 0 && heap[nod] > heap[parent(nod)] ) {
    std::swap( heap[nod], heap[parent(nod)] );
    upHeap( parent(nod) );
  }
}

void downHeap( int nod ) {
  int nod_min;
  nod_min = left_child(nod);
 
  if( right_child(nod) < heap_size && heap[right_child(nod)] > heap[nod_min] )
    nod_min = right_child(nod);
 
  if( nod_min < heap_size && heap[nod] < heap[nod_min] ) {
    std::swap( heap[nod], heap[nod_min] );
    downHeap( nod_min );
  }
}

void insertVal( int x ) {
  heap[heap_size] = x;
  upHeap( heap_size++ );
}

int deleteMin() {
  int rez;
  rez = heap[0];
  std::swap( heap[0], heap[--heap_size] );
  downHeap(0);
  return rez;
}

struct oaie {
  int dist, lana;
};

bool cmp( const oaie &a, const oaie &b ) {
  return a.dist < b.dist;
}

oaie v[MAXN];

int main() {
  FILE *fin, *fout;
  int n, i, x, l, ind;
  long long sum;
  fin = fopen( "lupu.in", "r" );
  
  fscanf( fin, "%d%d%d", &n, &x, &l );
  for( i = 0; i < n; i++ )
    fscanf( fin, "%d%d", &v[i].dist, &v[i].lana );

  fclose( fin );

  std::sort( v, v + n, cmp );

  ind = sum = 0;
  for( i = 0; i <= x; i += l ) {
    while( ind < n && v[ind].dist <= i )
      insertVal( v[ind++].lana );

    if( heap_size > 0 )
      sum += deleteMin();
  }

  fout = fopen( "lupu.out", "w" );
  fprintf( fout, "%lld", sum );
  fclose( fout );
  return 0;
}