Cod sursa(job #1773730)

Utilizator ionut98Bejenariu Ionut Daniel ionut98 Data 8 octombrie 2016 10:04:40
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#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;
}