Cod sursa(job #478812)

Utilizator mihai995mihai995 mihai995 Data 20 august 2010 14:39:14
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
using namespace std;

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

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

bool cmp(plasa a,plasa b)
{
	return a.peste>b.peste;
}

inline long long min(long long a,long long b)
{
	return a+(b-a)*(b<a);
}

inline long long max(long long a,long long b)
{
	return a+(b-a)*(b>a);
}

int main()
{
	int i,j,q;
	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=1;i<=1000;i++)
		for (j=q=1,v[i]=0;j<=n && q<=k;j++)
			if (a[j].timp<=i)
			{
				v[i]+=a[j].peste;
				q++;
			}
	for (i=1;i<=t;i++)
		for (j=min(i,1000)-1;j>=0;j--)
			v[i]=max(v[i],v[j]+v[i-j]);
	out<<v[t]<<"\n";
	return 0;
}