Cod sursa(job #2809468)

Utilizator vladburacBurac Vlad vladburac Data 27 noiembrie 2021 02:22:15
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100000
#define MAXELEM 2147483647

struct oaieee{
  int dist, lana;
};

oaieee heap[MAXN+2];
oaieee v[MAXN+2];
int n = 1;

bool cmp( oaieee a, oaieee b ) {
  return a.dist < b.dist;
}

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 upheap( int poz ) {
  while( poz > 0 && heap[poz].lana > heap[poz/2].lana ) {
    swap( heap[poz].lana, heap[poz/2].lana );
    poz = poz / 2;
  }
}

void Insert( int val ) {
  heap[n++].lana = val;
  upheap(n-1);
}

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

int main() {
  FILE *fin, *fout;
  int x, l, i, poz;
  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", &v[i].dist, &v[i].lana );
  fclose( fin );
  heap[0].lana = MAXELEM;
  sort( v, v + n, cmp );
  i = 0;
  poz = x % l;
  s = 0;
  while( i < n && poz <= x ) {
    while( i < n && v[i].dist <= poz ) {
      Insert( v[i].lana );
      i++;
    }
    if( i < n ) {
      s += heap[1].lana;
      extractMax();
    }
    poz += l;
  }
  fout = fopen( "lupu.out", "w" );
  fprintf( fout, "%lld", s );
  fclose( fout );
  return 0;
}