Pagini recente » Cod sursa (job #2756711) | Cod sursa (job #1174559) | Cod sursa (job #308828) | Cod sursa (job #1650279) | Cod sursa (job #160824)
Cod sursa(job #160824)
Utilizator |
Adrian Diaconu DITzoneC |
Data |
16 martie 2008 22:58:34 |
Problema |
Peste |
Scor |
Ascuns |
Compilator |
cpp |
Status |
done |
Runda |
|
Marime |
0.96 kb |
#include <stdio.h>
#include <assert.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define f first
#define s second
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define nmax 65536
#define tmax 1024
typedef long long lint;
priority_queue <short int> Q;
pair <int,int> P[nmax];
int n,k,T,H[tmax];
lint A[nmax],sol;
int main()
{
int i,j,l,aux;
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%d %d %d",&n,&k,&T);
assert(1<=n && n<=50000);
assert(1<=k && k<=50000);
assert(1<=T && T<=50000);
FOR(i,0,n)
{
scanf("%d %d",&P[i].s,&P[i].f);
assert(1<=P[i].f && P[i].f<=1000);
assert(1<=P[i].s && P[i].s<=1000);
}
sort(P,P+n);
i=aux=l=0;
FOR(j,1,1001)
{
for(;i<n && P[i].f==j;Q.push(-P[i].s),l++,aux+=P[i].s,i++);
for(;l>k;aux+=Q.top(),l--,Q.pop());
H[j]=aux;
}
FOR(i,0,T+1)
{
if(A[i]>sol) sol=A[i];
FOR(j,1,1001)
if(A[i+j]<A[i]+H[j])
A[i+j]=A[i]+H[j];
}
printf("%lld\n",sol);
return 0;
}