Pagini recente » Cod sursa (job #518943) | Cod sursa (job #1060697) | Cod sursa (job #1334937) | Cod sursa (job #1097068) | Cod sursa (job #1848444)
#include <cstdio>
#include <algorithm>
#include <queue>
#define DIM 50010
#define p second
#define t first
#define INF 1000010
#define DIMBUFF 100000
using namespace std;
FILE *fin = fopen("peste.in", "r");
FILE *fout = fopen("peste.out", "w");
class heap {
private:
int H[51010];
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>>1]) {
swap(H[c], H[c>>1]);
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 <<= 1;
} else
break;
}
}
};
//heap s;
priority_queue<int,vector<int>,greater<int> > s;
struct pereche {
int t;
int p;
} v[DIM];
int x[DIM];
long long d[DIM];
int n, k, total, sum;
int cmp(const pereche &a, const pereche &b) {
if(a.first == b.first)
return a.second < b.second;
else
return a.first < b.first;
}
char buff[DIMBUFF];
int pp;
int numar() {
int val = 0;
while (!(buff[pp] >= '0' && buff[pp] <= '9')) {
pp++;
if (pp == DIMBUFF) {
fread(buff, 1, DIMBUFF, fin);
pp=0;
}
}
while (buff[pp] >= '0' && buff[pp] <= '9') {
val = val*10 + buff[pp] - '0';
pp++;
if (pp == DIMBUFF) {
fread(buff, 1, DIMBUFF, fin);
pp=0;
}
}
return val;
}
int main () {
// fin>>n>>k>>total;
n = numar();
k = numar();
total = numar();
for (int i=1;i<=n;i++) {
//fin>>v[i].p>>v[i].t;
v[i].p = numar();
v[i].t = numar();
}
sort(v+1, v+n+1, cmp);
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 (v[j].t == i && j<=n) {
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;
int m = v[n].t;
for (int i=1;i<=total;i++) {
for (int last = 1; last <= m && i-last >= 0; last++) {
d[i] = max(d[i], d[i-last] + x[last]);
}
}
fprintf(fout, "%lld", d[total]);
return 0;
}