Cod sursa(job #479359)

Utilizator mihai995mihai995 mihai995 Data 23 august 2010 20:19:53
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
using namespace std;

struct plasa{long long timp,peste;} a[1<<16];
long long n,k,t,v[1<<16],b[1<<16];

ifstream in("peste.in");
ofstream out("peste.out");

bool cmp(plasa a,plasa b)
{
	return a.timp<b.timp;
}

inline bool comp(plasa a,plasa b)
{
	return a.peste<b.peste;
}

inline void sch(long long &a,long long &b)
{
	long long d=a;
	a=b;
	b=d;
}

inline void down(int x)
{
	int m=x;
	if (2*x<=k && comp(a[b[2*x]],a[b[m]]))
		m=2*x;
	if (2*x<k && comp(a[b[2*x+1]],a[b[m]]))
		m=2*x+1;
	if (m!=x)
	{
		sch(b[m],b[x]);
		down(m);
	}
}

int main()
{
	int i,j,s=0;
	in>>n>>k>>t;
	for (i=1;i<=n;i++)
		in>>a[i].peste>>a[i].timp;
	sort(a+1,a+n+1,cmp);
	for (i=j=1;i<=1000;v[i]=s,i++)
		for (;j<=n && a[j].timp<=i;j++)
			if (comp(a[b[1]],a[j]))
			{
				s-=a[b[1]].peste;
				b[1]=j;
				s+=a[b[1]].peste;
				down(1);
			}
	for (i=1;i<=t;i++)
		for (j=min(i,1000);j>=0;j--)
			v[i]=max(v[i],v[j]+v[i-j]);
	out<<v[t]<<"\n";
	return 0;
}