Pagini recente » Cod sursa (job #1464766) | Cod sursa (job #2959925) | Cod sursa (job #1649306) | Cod sursa (job #2445320) | Cod sursa (job #1994244)
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
ofstream fout ("peste.out");
class InputReader {
public:
InputReader() {}
InputReader(const char *name) {
fin = fopen(name, "r");
buffpos = Size - 1;
}
inline InputReader &operator >>(int &n) {
char ch = nextpos();
while(ch < '0' || ch > '9') {
ch = nextpos();
}
n = 0;
while('0' <= ch && ch <= '9') {
n = n * 10 + ch - '0';
ch = nextpos();
}
return *this;
}
private:
FILE *fin;
static const int Size = 1 << 18;
int buffpos;
char buff[Size];
inline char nextpos() {
++ buffpos;
if(buffpos == Size) {
buffpos = 0;
fread(buff, Size, 1, fin);
}
return buff[ buffpos ];
}
} fin ("peste.in");
const int nmax = 5e4;
const int tmax = 1000;
const int inf = 1 << 30;
long long p[tmax + 1], d[nmax + 1];
pair<int, int> v[nmax + 1];
priority_queue < int > h;
int main() {
int n, k, ttotal;
fin >> n >> k >> ttotal;
int lim = 0;
for (int i = 1; i <= n; ++ i) {
int x, t;
fin >> x >> t;
v[ i ] = make_pair(t, x);
lim = max(lim, t);
}
sort(v + 1, v + n + 1);
int sum = 0, ind = 1;
for (int i = 1; i <= tmax; ++ i) {
while (ind <= n && v[ ind ].first <= i) {
if ((int)h.size() < k) {
sum += v[ ind ].second;
h.push(-v[ ind ].second);
} else if (v[ ind ].second > -h.top()) {
sum += v[ ind ].second + h.top();
h.pop();
h.push(-v[ ind ].second);
}
++ ind;
}
p[ i ] = sum;
}
d[ 0 ] = 0;
for (int i = 1; i <= ttotal; ++ i) {
d[ i ] = -inf;
for (int j = 1; j <= lim && j <= i; ++ j) {
d[ i ] = max(d[ i ], d[i - j] + p[ j ]);
}
}
fout << d[ ttotal ] << "\n";
fout.close();
return 0;
}