Cod sursa(job #2268765)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 25 octombrie 2018 11:51:45
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>
#define maxn 100000

using namespace std;

struct oaie
{
  int dst, cnt;
};

oaie v[maxn+5];
priority_queue <int> hp;

bool cmp ( oaie a, oaie b )
{
  if ( a.dst != b.dst )
    return a.dst > b.dst;
  return a.cnt > b.cnt;
}

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

  int n, x, l;

  fin >> n >> x >> l;

  int i;

  for ( i = 0; i < n; i++ )
  {
    fin >> v[i].dst >> v[i].cnt;
    v[i].dst = ( x - v[i].dst ) / l;
  }

  sort ( v, v + n, cmp );

  long long ans = 0LL;
  int j = 0;

  for ( i = v[0].dst; i >= 0; i-- )
  {
    while ( j < n && v[j].dst == i )
    {
      hp.push ( v[j].cnt );
      j++;
    }

    if ( !hp.empty () )
    {
      ans += 1LL * hp.top ();
      hp.pop ();
    }
  }

  fout << ans;

  fin.close ();
  fout.close ();

  return 0;
}