Cod sursa(job #2894603)

Utilizator andiRTanasescu Andrei-Rares andiR Data 27 aprilie 2022 23:42:52
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>

#define Nmax 100000
using namespace std;
ifstream fin ("lupu.in");
ofstream fout ("lupu.out");
int N,X,L,i,rn,j;
long long total;
priority_queue<int> q;
int t[Nmax], val[Nmax];
void quicksort (int v[], int begin, int end )
{
  	int aux, b = begin, e = end;
  	long long pivot = v[(begin + end) / 2]; // pivotul: o pozitie intre begin si end

  while ( b <= e )
  {
  	while ( v[b] > pivot ) b++;
  	while ( v[e] < pivot ) e--;
    	if ( b <= e )
        {
     	    aux = v[b]; v[b] = v[e]; v[e] = aux;
      	    aux=val[b]; val[b]=val[e]; val[e]=aux;
            b++; e--;
        }
   }
   if ( begin < e ) quicksort(v, begin, e );
   if ( b < end ) quicksort(v, b, end );
}
int main()
{
    fin>>N>>X>>L;
    for (i=0;i<N;i++)
    {
        fin>>t[i]>>val[i];
        t[i]=(X-t[i])/L;
    }
    quicksort(t,0,N-1);
    rn=t[0];
    for (i=rn;i>=0;i--)
    {
        while (t[j]==i)
        {
            q.push(val[j]);
            j++;
        }
        if (!q.empty())
        {
            total+=q.top();
            q.pop();
        }
    }
    fout<<total;
    return 0;
}