Cod sursa(job #1334039)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 3 februarie 2015 20:34:55
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 50005;
const int MAXT = 1001;

struct peste {
   int p, t;
};

peste P[MAXN];
int aux[MAXT];
long long dp[MAXN];

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

priority_queue < int, vector <int>, greater <int> > q;

int main()
{
    ifstream cin("peste.in");
    ofstream cout("peste.out");
    int N, K, T, maxt = 0;
    cin >> N >> K >> T;
    for(int i = 1; i <= N; ++i) {
      cin >> P[i].p >> P[i].t;
      if(P[i].t > maxt)
         maxt = P[i].t;
    }
    int s = 0;
    sort(P + 1, P + N + 1, cmp);
    for(int i = 1; i <= N; ++i) {
        q.push(P[i].p);
        s += P[i].p;
        if(i > K) {
            s -= q.top();
            q.pop();
        }
        aux[P[i].t] = s;
    }

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

    for(int i = 1; i <= T; ++i) {
         for(int j = 1; j <= maxt && j <= i; ++j)
            if(dp[i - j] + aux[j] > dp[i])
               dp[i] = dp[i - j] + aux[j];
    }
    cout << dp[T];
    return 0;
}