Cod sursa(job #599772)

Utilizator SmarandaMaria Pandele Smaranda Data 29 iunie 2011 15:58:12
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
long long n,x,l;
struct LUP
{
	long long d,a;
};
vector <LUP> z;
vector <long long> c;
inline bool cmp (LUP v , LUP w)
{
	if (v.d>w.d)
		return true;
	if (v.d<w.d)
		return false;
	if (v.d==w.d)
		if (v.a>w.a)
			return true;
		else
			return false;
}

void read ()
{
	long long i;
	LUP temp;
	scanf("%lld%lld%lld",&n,&x,&l);
	for (i=1;i<=n;i++)
	{
		scanf("%lld%lld",&temp.d,&temp.a);
		z.push_back(temp);
	}
	sort(z.begin(),z.end(),cmp);
}

void rez()
{
	long long i,u=0,cu,lim;
	long long  s=0,sc;
	vector <LUP> :: iterator it;
	vector <long long> :: iterator jt;
	LUP temp;
	for (it=z.begin();it!=z.end();++it)
	{
		temp=*it;
		if (temp.d+l*u<=x)  // t=(x-temp.d)/l
		{
			u++;
			c.push_back(temp.a);
			s=s+(long long )temp.a;
		}
		else
			if (!c.empty())
			/*	if(temp.a>c.front())
				{
					s=(long long long long)s-c.back()+temp.a;
					c.pop();
					c.push(temp.a);
					
				}*/
			{
				lim=(x-temp.d)/l;
				if ((x-temp.d)%l)
					lim++;
				sc=0;
				for (jt=c.end()-1,i=1;i<=lim;--jt,++i)
					sc=sc+(long long )*jt;
				if (s<(long long )s-sc+temp.a)
				{
					s=(long long)s-sc+temp.a;
					for (i=1;i<=lim;i++)
						c.pop_back();
					c.push_back(temp.a);
					u=u-lim+1;
				}
			}
	}
	printf("%lld\n",s);
}

int main()
{
	
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	
	read();
	rez();
	return 0;
}