Cod sursa(job #2894554)

Utilizator andiRTanasescu Andrei-Rares andiR Data 27 aprilie 2022 22:54:55
Problema Lupul Urias si Rau Scor 32
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>

#define Nmax 100000
using namespace std;
ifstream fin ("lupu.in");
ofstream fout ("lupu.out");
int N,X,L,i,total,rn;
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=0;i<N && rn>=0;i++)
    {
        if (t[i]!=rn)
        {
            total+=q.top();
            q.pop();
            rn=t[i];
        }
        q.push(val[i]);
    }
    if (rn>=0)
        total+=q.top();
    fout<<total;
    return 0;
}