Pagini recente » Cod sursa (job #2692770) | Cod sursa (job #318402) | Cod sursa (job #915911) | Cod sursa (job #522273) | Cod sursa (job #727962)
Cod sursa(job #727962)
#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;
}