Cod sursa(job #2268749)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 25 octombrie 2018 11:21:44
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 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 );

  int cur;
  long long ans = 0LL;

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

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

  fout << ans;

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

  return 0;
}