Cod sursa(job #173805)
Utilizator | Data | 8 aprilie 2008 03:44:34 | |
---|---|---|---|
Problema | Peste | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.48 kb |
#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 1024
#define SMAX 50002
#define pb push_back
#define sz size()
#define mp make_pair
#define ff first
#define ss second
long int a[NMAX];
long int d[SMAX];
long int h[NMAX];
long int n,i,j,k,T,Tm,aux,cnt;
vector< pair<int, int> > v;
set<int> S;
set<int> ::iterator it;
long int x,y;
int main()
{
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%ld %ld %ld",&n,&k,&T);
Tm=0;
for (i=1;i<=n;i++)
{
scanf("%ld %ld",&x,&y);
v.pb( mp(y,x) );
Tm=max(y,Tm);
}
sort( v.begin(), v.end() );
x=-1;
a[0]=0;
cnt=0;
for (i=1;i<=Tm;i++)
{
a[i]=a[i-1];
while ( (x<n-1)&&(v[x+1].ff==i) ) {
x++;
if (cnt < k ) {S.insert(v[x].ss);
a[i]+=v[x].ss;
h[ v[x].ss ]++;
cnt++;
continue;}
if (cnt == k)
{
it=S.begin();
if ( (*it) < v[x].ss ) {
a[i]-=(*it);
h[(*it)]--;
if ( h[(*it)]==0 ) S.erase(it);
a[i]+=v[x].ss;
S.insert(v[x].ss);
h[ v[x].ss ] ++;
}
}
}
// printf("%ld %ld\n",i,a[i]);
}
d[0]=0;
for (i=1;i<=T;i++)
{
d[i]=0;
for (j=min(i,Tm);j;j--)
d[i]=max(d[i],d[i-j]+a[j]);
}
printf("%ld",d[T]);
return 0;
}