Pagini recente » Cod sursa (job #2739292) | Cod sursa (job #727582) | Cod sursa (job #2870236) | Cod sursa (job #433287) | Cod sursa (job #80900)
Cod sursa(job #80900)
#include <fstream>
std::ifstream f1("lupu.in");
std::ofstream f2("lupu.out");
struct elem { long d,a;};
long part(struct elem sir[110000], long jos, long sus);
void quicksort(struct elem sir[110000], long jos, long sus);
int main()
{
struct elem sir[110000];
long n, x, l, poz, dmax, i, dtemp, atemp;
int liber[110000];
long long sol;
f1>>n>>x>>l;
poz=0;
dmax=-1;
for (i=0; i<n; i++)
{
f1>>dtemp>>atemp;
if (dtemp<=x)
{
sir[poz].d=(x-dtemp)/l;
sir[poz].a=atemp;
if (sir[poz].d>dmax)
dmax=sir[poz].d;
poz++;
}//if
}//for i
n=poz;
quicksort(sir, 0, n-1);
// for (i=0; i<n; i++)/////////////////////////
// f2<<sir[i].d<<" "<<sir[i].a<<"\n";////////////////////
for (i=0; i<n; i++)
liber[i]=1;
sol=0;
for (i=0; i<n; i++)
{
poz=sir[i].d;
if (liber[poz]<2)
{
while ((liber[poz]!=1)&&(poz>=0))
poz--;
if (poz>=0)
{
sol+=sir[i].a;
liber[poz]=0;
}//if
else
liber[sir[i].d]=2;
}//if
}//for i
f2<<sol;
f1.close();
f2.close();
return 0;
}//main
long part(struct elem sir[110000], long jos, long sus)
{
long p, q;
struct elem temp;
p=jos;
q=sus;
while (p<q)
{
while ((sir[p].a>=sir[jos].a)&&(p<=q))
p++;
while ((sir[q].a<sir[jos].a)&&(q>=p))
q--;
if (p<q)
{
temp=sir[p];
sir[p]=sir[q];
sir[q]=temp;
}//if
}//while
temp=sir[q];
sir[q]=sir[jos];
sir[jos]=temp;
return q;
}//part
void quicksort(struct elem sir[110000], long jos, long sus)
{
if (jos<sus)
{
long p=part(sir, jos, sus);
quicksort(sir, jos, p-1);
quicksort(sir, p+1, sus);
}//if
}//quicksort