Pagini recente » Cod sursa (job #127796) | Cod sursa (job #1903600) | Cod sursa (job #1898091) | Cod sursa (job #1848433) | Cod sursa (job #1848438)
#include <fstream>
#include <algorithm>
#define DIM 50010
#define p second
#define t first
#define INF 1000010
using namespace std;
class heap {
private:
int H[1010];
int n;
public:
int top() {
return H[1];
}
int size() {
return n;
}
void push (int x) {
H[++n] = x;
int c = n;
while (c > 1) {
if (H[c] < H[c/2]) {
swap(H[c], H[c/2]);
c /= 2;
} else
break;
}
}
void pop() {
H[1] = H[n--];
int p = 1, c = 2;
while (c <= n) {
if (c+1 <= n && H[c+1] < H[c])
c++;
if (H[p] > H[c]) {
swap(H[p], H[c]);
p = c;
c *= 2;
} else
break;
}
}
};
heap s;
pair<int, int> v[DIM];
int x[DIM];
long long d[DIM];
int n, k, total, sum;
int main () {
ifstream fin ("peste.in");
ofstream fout("peste.out");
fin>>n>>k>>total;
for (int i=1;i<=n;i++) {
fin>>v[i].second>>v[i].first;
}
sort(v+1, v+n+1);
x[0] = -INF;
int j = 1;
for (int i = 1;i<=v[n].t;i++) {
if (i < v[j].t) {
x[i] = x[i-1];
} else {
while (j<=n && v[j].t == i) {
s.push(v[j].p);
sum += v[j].p;
j++;
}
while (s.size() > k) {
sum -= s.top();
s.pop();
}
x[i] = sum;
}
}
d[0] = 0;
for (int i=1;i<=total;i++) {
d[i] = -INF;
for (int last = 1; i-last+1 >= 1 && last <= v[n].t; last++) {
if (d[i-last] + x[last] > d[i])
d[i] = d[i-last] + x[last];
}
}
fout<<d[total];
return 0;
}