Cod sursa(job #1915104)

Utilizator felixiPuscasu Felix felixi Data 8 martie 2017 19:42:12
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

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

typedef long long I64;

const int NMAX = 50005;
const int TMAX = 1001;

struct TIP {
   int p, t;
};

TIP P[NMAX + 4];
int aux[TMAX + 4];
I64 d[NMAX + 4];
int N, K, T;
priority_queue < int, vector <int>, greater<int> > H;

bool cmp( const TIP& a, const TIP& b ) {
   if( a.t == b.t )  return a.p < b.p;
   return a.t < b.t;
}

int main()
{
    in >> N >> K >> T;
    for( int i = 1;  i <= N;  ++i ) {
        in >> P[i].p >> P[i].t;
    }

    int s = 0;
    sort( P+1, P+N+1, cmp );
    for( int i = 1;  i <= N;  ++i ) {
        H.push( P[i].p );
        s += P[i].p;

        if(i > K) {
            s -= H.top();
            H.pop();
        }

        aux[P[i].t] = s;
    }

    for( int i = 1;  i <= TMAX;  ++i ) {
        aux[i] = max( aux[i - 1], aux[i] );
    }

    for( int i = 1;  i <= T;  ++i ) {
        for( int j = 1;  j <= TMAX && j <= i;  ++j ) {
            if( d[i - j] + aux[j] > d[i] ) {
                d[i] = d[i - j] + aux[j];
            }
        }
    }

    out << d[T] << '\n';

    return 0;
}