Pagini recente » Cod sursa (job #787657) | Cod sursa (job #558625) | Cod sursa (job #1283648) | Cod sursa (job #796853) | Cod sursa (job #2040806)
#include <fstream>
#include <algorithm>
#include <queue>
#define DIM 50002
using namespace std;
ifstream f("peste.in");
ofstream g("peste.out");
int n, k, T;
long long d[DIM], s, aux[DIM];
class compare
{
public:
bool operator() (int a, int b)
{
return a > b;
}
};
priority_queue <int, vector<int>, compare> h;
struct plasa
{
int p, t;
}v[DIM];
bool cmp(plasa a, plasa b)
{
if(a.t == b.t)
return a.p < b.p;
return a.t < b.t;
}
int main()
{
f>>n>>k>>T;
for(int i = 1; i <= n; ++ i)
f>>v[i].p>>v[i].t;
sort(v + 1, v + n + 1, cmp);
for(int i = 1; i <= n; ++ i)
{
h.push(v[i].p);
s += v[i].p;
if(h.size() > k)
{
s -= h.top();
h.pop();
}
aux[v[i].t] = max(aux[v[i].t], s);
}
for(int i = 1; i <= T; ++ i)
for(int j = 0; j <= min(i, v[n].t); ++ j)
d[i] = max(d[i], d[i - j] + aux[j]);
g<<d[T];
return 0;
}