Pagini recente » Cod sursa (job #2624288) | Cod sursa (job #2330933) | Cod sursa (job #2278719) | Cod sursa (job #2346181) | Cod sursa (job #1867799)
#include <cstdio>
#include <queue>
#include <algorithm>
#define MAXG 50000
#define MAXT 1000
std::priority_queue <int, std::vector <int>, std::greater <int> > q;
std::vector <int> v[MAXT+1];
long long 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);
}
long long 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);
}
fprintf(fout, "%lld\n", d[g]);
fclose(fin);
fclose(fout);
return 0;
}