Pagini recente » Statistici Ortan Mihai (Kingster95) | Cod sursa (job #2741006) | Cod sursa (job #1035969) | Monitorul de evaluare | Cod sursa (job #1076856)
#include <algorithm>
#include <cstdio>
#include <queue>
#define PII pair<int, int>
#define x first
#define y second
using namespace std;
const int N=50005, M=1001;
bool comp(int a, int b)
{
return a>b;
}
int main()
{
freopen("peste.in", "r", stdin);
freopen("peste.out", "w", stdout);
int t=0, n=0, k=0, i, j;
long long b[N], c[1001], s=0;
PII a[N];
char cit[50], *p;
vector <int> h;
fgets(cit, 50, stdin);
for(p=cit;*p>='0'&&*p<='9';p++) n=10*n+*p-'0'; p++;
for(;*p>='0'&&*p<='9';p++) k=10*k+*p-'0'; p++;
for(;*p>='0'&&*p<='9';p++) t=10*t+*p-'0';
for(i=1;i<=n;i++)
{
fgets(cit, 50, stdin);
for(p=cit;*p>='0'&&*p<='9';p++) a[i].y=10*a[i].y+*p-'0'; p++;
for(;*p>='0'&&*p<='9';p++) a[i].x=10*a[i].x+*p-'0';
}
sort(a+1, a+n+1);
b[0]=c[0]=0;
for(i=1;i<=n;i++)
{
s+=a[i].y;
h.push_back(a[i].y);
push_heap(h.begin(), h.end(), comp);
if(i>k)
{
s-=h.front();
pop_heap(h.begin(), h.end(), comp);
h.pop_back();
}
c[a[i].x]=s;
}
for(i=1;i<M;i++) if(c[i]<c[i-1]) c[i]=c[i-1];
for(i=1;i<=t;i++)
{
b[i]=c[i];
for(j=1;i>j&&j<M;j++)
{
if(b[i]<b[i-j]+c[j]) b[i]=b[i-j]+c[j];
}
if(b[i]<b[i-1]) b[i]=b[i-1];
}
printf("%lld", b[t]);
}