Cod sursa(job #1749721)

Utilizator Athena99Anghel Anca Athena99 Data 28 august 2016 17:09:49
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <algorithm>
#include <fstream>
#include <set>

using namespace std;

ifstream fin("peste.in");
ofstream fout("peste.out");

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], 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;
}