Pagini recente » Cod sursa (job #2026865) | Cod sursa (job #2972466) | Cod sursa (job #1699119) | Cod sursa (job #722817) | Cod sursa (job #1749725)
#include <algorithm>
#include <fstream>
#include <set>
using namespace std;
ifstream fin("peste.in");
ofstream fout("peste.out");
typedef long long i64;
const int nmax= 50000;
const int tmax= 1000;
struct str {
int x, y;
};
bool cmp( str x, str y ) {
return x.y<y.y;
}
int a[tmax+1];
i64 d[nmax+1];
str v[nmax+1];
multiset <int> s;
int main( ) {
int n, k, t, timpmax= 0;
fin>>n>>k>>t;
for ( int i= 1; i<=n; ++i ) {
fin>>v[i].x>>v[i].y;
if ( v[i].y>timpmax ) {
timpmax= v[i].y;
}
}
sort( v+1, v+n+1, cmp );
for ( int i= 1, j= 0; i<=timpmax; ++i ) {
a[i]= a[i-1];
while ( j<=n && v[j].y<=i ) {
s.insert(v[j].x);
a[i]+= v[j].x;
++j;
}
while ( (int)s.size()>k ) {
multiset <int>::iterator it= s.begin();
a[i]-= *it;
s.erase(it);
}
}
for ( int i= 1; i<=t; ++i ) {
for ( int j= 1; j<=i && j<=timpmax; ++j ) {
if ( d[i-j]+a[j]>d[i] ) {
d[i]= d[i-j]+a[j];
}
}
}
fout<<d[t]<<"\n";
return 0;
}