Cod sursa(job #2032642)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 5 octombrie 2017 15:17:01
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
# include <fstream>
# include <set>
# include <algorithm>
# define DIM 50010
# define f first
# define s second
using namespace std;
ifstream fin("peste.in");
ofstream fout("peste.out");
multiset<int> myset;
multiset<int>::iterator it;
pair<int,int> v[DIM];
int d[DIM],n,k,t,i,j,sum;
int main () {
    fin>>n>>k>>t;
    for(i=1;i<=n;i++)
        fin>>v[i].s>>v[i].f;
    sort(v+1,v+n+1);
    for(i=1;i<=k;i++){
        d[v[i].f]=v[i].s+d[v[i-1].f];
        myset.insert(v[i].s);
    }
    sum=d[v[k].f];
    for(;i<=n;i++){
        sum+=v[i].s;
        myset.insert(v[i].s);
        it=myset.begin();
        sum-=(*it);
        myset.erase(it);
        d[v[i].f]=max(d[v[i].f],sum);
    }
    for(i=1;i<=t;i++)
        for(j=1;j<=min(i-1,1000);j++)
            d[i]=max(d[i],d[i-j]+d[j]);
    fout<<d[t]<<"\n";
    return 0;
}