Cod sursa(job #2823529)

Utilizator lolismekAlex Jerpelea lolismek Data 28 decembrie 2021 19:08:15
Problema Peste Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

#define int long long

using namespace std;

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

struct peste{
    int p, t;
};

const int N = 5 * 1e4 + 1, TMAX = 1000;
priority_queue <int> heap;
peste v[N];
int aux[N], dp[N];

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

signed main(){
    int n, k, T;
    fin >> n >> k >> T;
    for(int i = 1; i <= n; i++) fin >> v[i].p >> v[i].t;
    sort(v + 1, v + n + 1, cmp);
    int s = 0;

    // aux[i] = cantitatea maxima de peste daca folosesc maximum k plase, iar toate plasele au timpul mai mic sau egal cu i
    //  > cu ajutorul unui heap, daca am depasit numarul de k plase, le scot pe cele mai mici drept cantitate peste
    for(int i = 1; i <= n; i++){
        s += v[i].p;
        heap.push(-v[i].p);
        while(heap.size() > k){
            s += heap.top();
            heap.pop();
        }
        aux[v[i].t] = s;
    }

    // uniformizare:
    for(int i = 1; i <= n; i++) aux[i] = max(aux[i], aux[i - 1]);

    // dp[i] = numarul maxim de peste la momentul i
    // dp[i] = max(dp[i - 1] + aux[1], dp[i - 2] + aux[2], ... , dp[i - TMAX] + aux[TMAX]), unde TMAX -> timpul maxim de lansare
    // a unei plase, a.i. TMAX <= i
    // > deoarece momentul oportun sa lansez plasele este simultan

    for(int i = 1; i <= T; i++){
        dp[i] = dp[i - 1];
        int lim = min(i, TMAX);
        for(int j = 1; j <= lim; j++)
            dp[i] = max(dp[i], dp[i - j] + aux[j]);
    }
    fout << dp[T] << '\n';
    return 0;
}