Cod sursa(job #705848)

Utilizator misinoonisim necula misino Data 5 martie 2012 06:56:26
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#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;
}