Cod sursa(job #1130912)

Utilizator stefanzzzStefan Popa stefanzzz Data 28 februarie 2014 16:29:09
Problema Peste Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <algorithm>
#include <queue>
#define MAXN 50005
#define MAXT 1005
using namespace std;
ifstream f("peste.in");
ofstream g("peste.out");

int n,m,t,pesti[MAXN],timp[MAXN],ord[MAXN],mxtimp,cnt,x;
long long pd1[MAXT],pd2[MAXN],mx,sol,S;

bool Comp(int p,int q){
    return timp[p]<timp[q];}

struct Comp2{
    bool operator()(int p,int q){
        return pesti[p]>pesti[q];}};

priority_queue<int,vector<int>,Comp2> pq;

int main()
{
    int i,j;
    f>>n>>m>>t;
    for(i=1;i<=n;i++){
        f>>pesti[i]>>timp[i];
        if(timp[i]>mxtimp)
            mxtimp=timp[i];
        ord[i]=i;}
    sort(ord+1,ord+n+1,Comp);
    for(i=1,j=1;i<=mxtimp;i++){
        while(j<=n&&timp[ord[j]]<=i){
            cnt++;
            S+=pesti[ord[j]];
            pq.push(ord[j++]);}
        while(cnt>m){
            x=pq.top();
            pq.pop();
            S-=pesti[x];
            cnt--;}
        pd1[i]=S;}
    for(i=1;i<=t;i++){
        mx=0;
        for(j=1;j<=mxtimp&&i>=j;j++)
            if(pd1[j]+pd2[i-j]>mx)
                mx=pd1[j]+pd2[i-j];
        pd2[i]=mx;
        if(mx>sol)
            sol=mx;}
    g<<sol<<'\n';
    f.close();
    g.close();
    return 0;
}