Pagini recente » Cod sursa (job #2086684) | Cod sursa (job #1830087) | Cod sursa (job #1292661) | Cod sursa (job #1694248) | Cod sursa (job #164749)
Cod sursa(job #164749)
#include <stdio.h>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
const int n_max = 51000;
class set_cmp {
public:
bool operator() ( const long long &a, const long long &b ) { return (a > b); };
};
multiset < int, set_cmp > s;
multiset < int, set_cmp >::iterator it;
pair <int , int > v[n_max];
pair <int , int > x[n_max];
long long d[n_max], sol;
int i, j, k, o, n, t, p, q, plase;
inline long long maxim(long long a, long long b)
{
if ( a > b)
return a;
return b;
}
int main()
{
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%d %d %d", &n, &plase, &t);
for (i = 1; i <= n; ++ i)
{
scanf("%d %d", &x[i].second, &x[i].first);
v[i].first = x[i].first;
}
sort(x+1,x+n+1);
sort(v+1,v+n+1);
p = 1;
for (i = 2; i <= n; ++ i)
{
if (v[i].first !=v[i-1].first)
v[++p].first = v[i].first;
}
k = 1;
for (i = 1; i <= p; ++ i)
{
while (x[k].first <= v[i].first && k<=n)
s.insert(x[k++].second);
it = s.begin();
for (q = 1; q <= plase && q <=s.size(); ++it, ++q)
v[i].second+=*it;
}
d[0] = 1;
for (j = 0; j <= t; ++ j)
{
for (i = 1; i <=p; ++ i)
if (d[j] > 0 && j + v[i].first <= t)
{
d[j + tx] = maxim(d[j+v[i].first], d[j]+v[i].second);
if (d[j+v[i].first] > sol)
sol = d[j+v[i].first];
}
}
printf("%lld\n", sol-1);
return 0;
}