Cod sursa(job #2296273)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 4 decembrie 2018 16:30:26
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

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

const int NMAX = 100004;

int N, D, L;
struct oaie
{
  int t, cant;
} A[NMAX];

priority_queue <int> Heap;

void Read()
{
  fin >> N >> D >> L;

  int aux;

  for( int i = 1; i <= N; ++i )
    {
      fin >> aux >> A[i].cant;
      A[i].t = 1 + ( D - aux ) / L;
    }

  fin.close();
}

bool comp( oaie A, oaie B )
{
  return A.t < B.t;
}

void Do()
{
  int t_max = 0;

  for( int i = 1; i <= N; ++i )
    t_max = max( t_max, A[i].t );

  sort( &A[1], &A[N + 1], comp );

  int cursor = N;
  long long sum = 0;

  for( int i = t_max; i > 0; --i )
  {
    while( A[cursor].t == i && cursor > 0 )
    {
      Heap.push( A[cursor].cant );
      --cursor;
    }

    if( Heap.size() > 0 )
    {
      sum += Heap.top();
      Heap.pop();
    }
  }

  //for( int i = 1; i <= N; ++i )
   // fout << A[i].t << '\n';

  fout << sum << '\n';

  fout.close();
}

int main()
{
    Read();
    Do();

    return 0;
}