Cod sursa(job #727962)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 28 martie 2012 13:22:45
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>

using namespace std;

long long n,x,l,max1,lanamax,d[100000],a[100000],i,sol,fol[100000],poz;

void quickSort(int st, int dr) 
{
      int i = st, j = dr;
      int aux;
      int m = d[(st + dr) / 2];
	  while (i <= j) {
            while (d[i] < m)
				  i++;
            while (d[j] > m)
                  j--;
            if (i <= j) {
                  aux = d[i];
                  d[i] = d[j];
                  d[j] = aux;
				  aux=a[i];
				  a[i]=a[j];
				  a[j]=aux;
				  if (d[i]>max1) max1=d[i];
				  if (d[j]>max1) max1=d[j];
                  i++;
                  j--;
            }
      };
      if (st < j)
            quickSort(st, j);
      if (i < dr)
            quickSort(i, dr);
}

int main()
{
	fstream f("lupu.in",ios::in);
	fstream g("lupu.out",ios::out);
	f>>n>>x>>l;
	for (i=1;i<=n;i++) f>>d[i]>>a[i];
	max1=0;
	quickSort(1,n);
	sol=0;
	while (x>=0)
	{
		lanamax=0;
		if (x-l+1>max1) {
			for (i=1;i<=n;i++) if ((a[i]>lanamax)&&(fol[i]==0)) {
                                                  				lanamax=a[i];
																poz=i;
			}
			fol[poz]=1;
		}
			else {
					i=n;
					while (d[i]>=x-l+1)
					{
						if ((a[i]>lanamax)&&(fol[i]==0)) lanamax=a[i];
						i--;
					}
					n=i;
			}
		sol=sol+lanamax;
        x=x-l;
    }		
	g<<sol;
	f.close();
	g.close();
	return 0;
}