Cod sursa(job #3143480)

Utilizator Ana_22Ana Petcu Ana_22 Data 30 iulie 2023 16:15:50
Problema Lupul Urias si Rau Scor 88
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define NMAX 100000

using namespace std;

struct str {
  int pasi, val;
} v[NMAX], heap[NMAX];
int nexxt[NMAX];
int heapsize, pas;

bool cmp( str a, str b ) {
  if( a.pasi != b.pasi )
    return a.pasi < b.pasi;
  return a.val < b.val;
}

inline int parent(int i) { return (i - 1) / 2; }
inline int leftChild(int i) { return i * 2 + 1; }
inline int rightChild(int i) { return i * 2 + 2; }

void first_del();

void upHeap(int i) {
  while (i && heap[parent(i)].val < heap[i].val) {
    swap(heap[parent(i)], heap[i]);
    i = parent(i);
  }
}

void downHeap(int i) {
  int left, right, biggest;

  biggest = i;
  left = leftChild(i), right = rightChild(i);

  if (left < heapsize && heap[left].val > heap[biggest].val)
    biggest = left;
  if (right < heapsize && heap[right].val > heap[biggest].val)
    biggest = right;

  if (i != biggest) {
    swap(heap[i], heap[biggest]);
    downHeap(biggest);
  }
}


void extractMax() {
  swap( heap[0], heap[--heapsize] );
  downHeap( 0 );
}

void heap_insert( str oaie ) {
  heap[heapsize++] = oaie;
  upHeap( heapsize - 1 );
}

void update(int i, int value) {
  heap[i].val = value;
  upHeap(i);
  downHeap(i);
}

int getMax() {
  return heap[0].val;
}

void heap_delete(int i) {
  update(i, getMax());
  extractMax();
}

void first_del() {
  while( heapsize && heap[0].pasi < pas )
    heap_delete( 0 );
}


int main() {
    FILE *fin, *fout;
    int n, x, l, i, d, a, pas_max, st, finn, j;
    long long sum;
    fin = fopen( "lupu.in", "r" );
    fout = fopen( "lupu.out", "w" );
    fscanf( fin, "%d%d%d", &n, &x, &l );
    pas_max = 0;
    sum = 0;
    for( i = 0; i < n; i++ ) {
      fscanf( fin, "%d%d", &d, &a );
      v[i].pasi = ( x - d + l ) / l;
      v[i].val = a;
      if( v[i].pasi > pas_max )
        pas_max = v[i].pasi;
    }
    sort( v, v + n, cmp );
    i = n - 1;
    for( pas = pas_max; pas > 0; pas-- ) {
      while( i >= 0 && v[i].pasi >= pas ) {
        heap_insert( v[i] );
        i--;
      }
      sum += getMax();
      extractMax();
    }
    fprintf( fout, "%lld", sum );
    fclose( fin );
    fclose( fout );
    return 0;
}