Pagini recente » Cod sursa (job #2419725) | Cod sursa (job #1523861) | Cod sursa (job #1777384) | Cod sursa (job #1716168) | Cod sursa (job #1773730)
#include<fstream>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
#include<deque>
using namespace std;
ifstream f("peste.in");
ofstream g("peste.out");
#define nmax 50005
#define Tmax 1005
#define ll long long
#define Cifmax 5000005
int n,K,Ttotal;
ll dp[nmax],cat[Tmax];
pair<int,int>v[nmax];
multiset<int>Heap;
int poz;
char S[Cifmax];
void buf(int &nr)
{
nr=0;
for(;S[poz]<'0'||S[poz]>'9';poz++);
for(;S[poz]>='0'&&S[poz]<='9';poz++)
nr=nr*10+(S[poz]-'0');
}
void citeste()
{
f.getline(S,Cifmax,EOF);
buf(n); buf(K);
buf(Ttotal);
for(int i=1;i<=n;++i)
{
int x,y;
buf(x);
buf(y);
v[i]=make_pair(y,x);
}
sort(v+1,v+n+1);
}
struct cmp
{
bool operator() (const int &A,const int &B)
{
return A>B;
}
};
void preprocesare()
{
priority_queue<int,vector<int>,cmp>Q;
ll sum=0LL;
for(int i=1;i<=n;++i)
{
sum+=v[i].second;
Q.push(v[i].second);
if(i>K)
{
sum-=1LL*(Q.top());
Q.pop();
}
cat[v[i].first]=sum;
}
for(int i=1;i<Tmax;++i)
cat[i]=max(cat[i],cat[i-1]);
}
void rezolva()
{
preprocesare();
dp[0]=0LL;
for(int i=1;i<=Ttotal;++i)
{
ll Max=0;
for(int j=0;j<Tmax&&i>=j;++j)
Max=max(Max,dp[i-j]+cat[j]);
dp[i]=max(dp[i-1],Max);
}
g<<dp[Ttotal]<<"\n";
}
int main()
{
citeste();
rezolva();
return 0;
}