Pagini recente » Cod sursa (job #84811) | Diferente pentru utilizator/raresegay intre reviziile 13 si 14 | Cod sursa (job #1423867) | Cod sursa (job #1138939) | Cod sursa (job #705848)
Cod sursa(job #705848)
#include<fstream>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
int maxi,max1,i,j,k,l,x,nr,c1,d1,n,d[100001],ca1[100001],ca[100001],nro[100001];
int poz(int li,int ls)
{int i,j,x,y;
i=li;
j=ls;
x=d[i];
y=ca1[i];
while(i<j)
{while(i<j&&x<d[j]||(x==d[j]&&y<=ca1[i]))
--j;
d[i]=d[j];
ca1[i]=ca1[j];
while(i<j&&x>d[i]||(x==d[i]&&y<=ca1[i]))
++i;
d[j]=d[i];
ca1[j]=ca1[i];
}
d[i]=x;
ca1[i]=y;
return i;
}
void quick(int li,int ls)
{int k;
if(li<ls)
{k=poz(li,ls);
if(li<k-1)
quick(li,k-1);
if(ls>k+1)
quick(k+1,ls);
}}
int main()
{f>>n>>x>>l;
nr=0;
for(i=1;i<=n;++i)
{f>>d1>>c1;
if(d1<=x)
{++nr;
d[nr]=d1;
ca1[nr]=c1;
}}
quick(1,nr);
max1=0;
for(i=nr;i>=1;--i)
{maxi=-1;
for(j=i+1;j<=nr+1;++j)
if(l*nro[j]+d[i]<=x)
if(ca[j]>maxi)
{maxi=ca[j];
k=j;
}
nro[i]=nro[k]+1;
ca[i]=ca[k]+ca1[i];
if(max1<ca[i])
max1=ca[i];
}
g<<max1<<'\n';
f.close();
g.close();
return 0;
}