Pagini recente » Cod sursa (job #1088326) | Cod sursa (job #563415) | Cod sursa (job #2378642) | Cod sursa (job #2614092) | Cod sursa (job #172202)
Cod sursa(job #172202)
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#define maxN 50001
#define maxT 1001
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
struct Comp
{
bool operator()(int i, int j)
{
return i > j;
};
};
vector < pair <int, int> > V;
priority_queue <int, vector <int>, Comp> Pq;
int N, K, T;
int D[maxN], Cnt[maxT];
int main()
{
freopen("peste.in", "rt", stdin);
freopen("peste.out", "wt", stdout);
int i, p, t;
for(scanf("%d %d %d", &N, &K, &T), i=1; i<=N; ++i)
{
scanf("%d %d", &p, &t);
V.pb(mp(t, p));
}
sort(V.begin(), V.end());
int s = 0;
for(i=0; i<N; ++i)
{
if(i < K)
{
s += V[i].ss;
Cnt[V[i].ff] = s;
Pq.push(V[i].ss);
}
else
{
int c = Pq.top();
if(V[i].ss > c)
{
Pq.pop();
s -= c;
s += V[i].ss;
Pq.push(V[i].ss);
Cnt[V[i].ff] = s;
}
}
}
for(i=1; i<=1000; ++i)
if(Cnt[i-1] > Cnt[i]) Cnt[i] = Cnt[i-1];
int j;
for(i=1; i<=T; ++i)
for(j=1; j<=1000 && j<=i; ++j)
if(D[i] < D[i-j] + Cnt[j])
D[i] = D[i-j] + Cnt[j];
printf("%d", D[T]);
fclose(stdin);
fclose(stdout);
return 0;
}