Pagini recente » Cod sursa (job #875973) | Cod sursa (job #1039948) | Cod sursa (job #885674) | Cod sursa (job #845936) | Cod sursa (job #1854056)
#include<fstream>
#include<algorithm>
#define f first
#define s second
#define DIM 50005
using namespace std;
int n, k, m, i, j, t, nr, sum;
int h[DIM], s[1005];
long long d[DIM], sol;
pair<int, int> v[DIM];
ifstream fin("peste.in");
ofstream fout("peste.out");
void upd(int poz){
int c = poz, p = c / 2;
while(p > 0 && v[ h[p] ].s > v[ h[c] ].s){
swap(h[p], h[c]);
c = p;
p = c / 2;
}
}
void elim(){
int p = 1, c = 2;
while(c <= nr){
if(c + 1 <= nr && v[ h[c] ].s > v[ h[c + 1] ].s){
c++;
}
if(v[ h[p] ].s > v[ h[c] ].s){
swap(h[p], h[c]);;
p = c;
c = 2 * p;
}
else{
break;
}
}
}
int main(){
fin>> n >> k >> t;
for(i = 1; i <= n; i++){
fin>> v[i].s >> v[i].f;
m = max(m, v[i].f);
}
sort(v + 1, v + n + 1);
for(i = 1; i <= n; i++){
j = i;
while(v[i].f == v[j].f){
nr++;
h[nr] = j;
sum += v[j].s;
upd(nr);
if(nr > k){
sum -= v[ h[1] ].s;
elim();
nr--;
}
j++;
}
s[ v[i].f ] = sum;
i = j - 1;
}
for(i = 1; i <= t; i++){
for(j = 1; j <= min(i, m); j++){
d[i] = max(d[i], d[i - j] + s[j]);
}
sol = max(sol, d[i]);
}
fout<< d[t] <<"\n";
return 0;
}