Pagini recente » Cod sursa (job #1924691) | Cod sursa (job #1665381) | Cod sursa (job #1390306) | Cod sursa (job #427699) | Cod sursa (job #1867795)
#include <cstdio>
#include <queue>
#include <algorithm>
#define INF 1000000000
#define MAXG 50000
#define MAXT 1000
std::priority_queue <int, std::vector <int>, std::greater <int> > q;
std::vector <int> v[MAXT+1];
int d[MAXG+1];
int main(){
FILE *fin, *fout;
fin=fopen("peste.in", "r");
fout=fopen("peste.out", "w");
int n, k, g;
fscanf(fin, "%d%d%d", &n, &k, &g);
for(int i=1; i<=n; i++){
int x, y;
fscanf(fin, "%d%d", &x, &y);
v[y].push_back(x);
}
for(int i=1; i<=MAXG; i++)
d[i]=-INF;
int sum=0;
for(int i=1; i<=MAXT; i++){
for(auto x:v[i]){
if(k>(int)q.size()){
sum+=x;
q.push(x);
}else if(x>q.top()){
sum+=x-q.top();
q.pop();
q.push(x);
}
}
for(int j=i; j<=g; j++)
d[j]=std::max(d[j], d[j-i]+sum);
}
int ans=0;
for(int i=1; i<=g; i++)
ans=std::max(ans, d[i]);
fprintf(fout, "%d\n", ans);
fclose(fin);
fclose(fout);
return 0;
}