Pagini recente » Cod sursa (job #3158915) | Cod sursa (job #661542) | Cod sursa (job #3266958) | Cod sursa (job #781100) | Cod sursa (job #3194696)
#include <bits/stdc++.h>
#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
ifstream fin ("peste.in");
ofstream fout ("peste.out");
const int NMAX=1e5+5;
#define int long long
int dp_time[NMAX];
int dp_tank[NMAX];
struct elem {
int shark_tank;
int time;
}v[NMAX];
bool cmp(elem a,elem b)
{
if(a.time==b.time)
return a.shark_tank<b.shark_tank;
return a.time<b.time;
}
signed main()
{
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
int n,i,j,t,k,curr=0;
priority_queue<int,vector<int>,greater<int>>pq;
fin>>n>>k>>t;
t=min(t,1000LL);
for(i=1;i<=n;i++)
fin>>v[i].shark_tank>>v[i].time;
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++)
{
curr+=v[i].shark_tank;
pq.push(v[i].shark_tank);
if(pq.size()>k)
{
curr-=pq.top();
pq.pop();
}
dp_tank[v[i].time]=curr;
}
for(i=1;i<=t;i++)
dp_tank[i]=max(dp_tank[i],dp_tank[i-1]);
for(i=1;i<=t;i++)
{
dp_time[i]=dp_time[i-1];
for(j=1;j<=i;j++)
dp_time[i]=max(dp_time[i],dp_time[i-j]+dp_tank[j]);
}
fout<<dp_time[t];
fin.close();
fout.close();
return 0;
}