Pagini recente » Cod sursa (job #992626) | Cod sursa (job #535478) | Cod sursa (job #1396926) | Cod sursa (job #1049713) | Cod sursa (job #1316342)
#include<fstream>
#include<queue>
#include<algorithm>
#define N 50100
#define D 10000
using namespace std;
ofstream g("peste.out");
int n,k,i,t,s,j,poz = D + 1,a[1010];
long long d[N];
char buf[D];
pair<int,int>v[N];
struct cmp{
bool operator()(int a,int b){
return a > b;
}
};
priority_queue<int, vector<int>, greater<int> >h;
inline int ianr(){
unsigned int nr=0;
while((buf[poz] < '0' || buf[poz] > '9') && buf[poz] != '-')
if(++ poz >= D)
fread(buf , D , 1 , stdin) , poz = 0;
int semn = 1;
if(buf[poz] == '-')
++ poz , semn = -1;
while('0' <= buf[poz] && buf[poz] <= '9')
{
nr = nr * 10 + buf[poz] - '0';
if(++ poz >= D)
fread(buf , D , 1 , stdin) , poz = 0;
}
return nr * semn;
}
int main()
{
freopen("peste.in","r",stdin);
n = ianr();
k = ianr();
t = ianr();
for(i = 1; i <= n; ++i)
v[i].second = ianr(),
v[i].first = ianr();
sort(v + 1, v + n + 1);
for(i = 1; i <= n; ++i)
{
h.push(v[i].second);
s += v[i].second;
if(i > k)
{
s -= h.top();
h.pop();
}
a[v[i].first] = s;
}
for(i = 1; i <= 1000; ++i)
a[i] = max(a[i - 1], a[i]);
for(i = 1; i <= t; ++i)
{
for(j = 1; j <= 1000 && j <= i; ++j)
d[i] = max(d[i], d[i - j] + a[j]);
}
g << d[t] << '\n';
return 0;
}