Pagini recente » Cod sursa (job #144135) | Cod sursa (job #1503362) | Cod sursa (job #1756013) | Cod sursa (job #13615) | Cod sursa (job #485450)
Cod sursa(job #485450)
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define DIM 50005
#define sc second
#define fs first
#define MAX 1005
long long bst[DIM],nr[MAX];
pair <int,int> v[DIM];
int n,k,t;
struct cmp
{
bool operator () (const int &a,const int &b)
{
return a>b;
}
}; priority_queue <int,vector <int>,cmp> h;
void read ()
{
int i;
scanf ("%d%d%d",&n,&k,&t);
for (i=1; i<=n; ++i)
scanf ("%d%d",&v[i].sc,&v[i].fs);
}
void solve ()
{
long long sum;
int i,j;
sum=0;
sort (v+1,v+n+1);
for (i=j=1; i<MAX; ++i)
{
for ( ; j<=n && v[j].fs<=i; ++j)
{
sum+=v[j].sc;
h.push (v[j].sc);
}
for ( ; (int)h.size ()>k; h.pop ())
sum-=h.top ();
nr[i]=sum;
}
for (i=1; i<=t; ++i)
for (j=1; j<=min (i,MAX); ++j)
bst[i]=max (bst[i],bst[i-j]+nr[j]);
printf ("%lld",bst[t]);
}
int main ()
{
freopen ("peste.in","r",stdin);
freopen ("peste.out","w",stdout);
read ();
solve ();
return 0;
}