Cod sursa(job #2809417)

Utilizator vladburacBurac Vlad vladburac Data 26 noiembrie 2021 22:55:47
Problema Lupul Urias si Rau Scor 8
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
using namespace std;
#define MAXN 100000

struct oaieee{
  int dist, lana;
};

oaieee heap[MAXN];
int n;

void downheap( int poz ) {
  while( 2 * poz < n && heap[poz].lana < max( heap[2*poz].lana, heap[2*poz+1].lana ) ) {
    if( heap[2*poz].lana > heap[2*poz+1].lana ) {
      swap( heap[poz], heap[2*poz] );
      poz = 2 * poz;
    }
    else {
      swap( heap[poz], heap[2*poz+1] );
      poz = 2 * poz + 1;
    }
  }
}

void build() {
  int i;
  for( i = n / 2 - 1; i >= 0; i-- )
    downheap(i);
}

void extractMax() {
  heap[0].dist = heap[n-1].dist;
  heap[0].lana = heap[n-1].lana;
  n--;
  downheap(0);
}

int main() {
  FILE *fin, *fout;
  int x, l, nr, i;
  long long s;
  fin = fopen( "lupu.in", "r" );
  fscanf( fin, "%d%d%d", &n, &x, &l );
  for( i = 0; i < n; i++ )
    fscanf( fin, "%d%d", &heap[i].dist, &heap[i].lana );
  fclose( fin );
  build();
  nr = 0;
  s = 0;
  while( nr < x / l + 1 ) {
    while( heap[0].dist + nr * l > x )
      extractMax();
    s += heap[0].lana;
    nr++;
    extractMax();
  }
  fout = fopen( "lupu.out", "w" );
  fprintf( fout, "%lld", s );
  fclose( fout );
  return 0;
}