Cod sursa(job #2032530)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 5 octombrie 2017 10:28:06
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <queue>
#include <algorithm>
#define DIM 50001
using namespace std;

int n,k,t,i,j;
long long suma,aux[DIM],best[DIM];
priority_queue < int,vector <int>,greater<int> > H;

class peste{
public:
    int p;
    int t;
};
peste v[DIM];
int comparare (peste a,peste b){
    return a.t<b.t;
}

int main (){

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

    fin>>n>>k>>t;
    for (i=1;i<=n;i++)
        fin>>v[i].p>>v[i].t;
    sort (v+1,v+n+1,comparare);
    for (i=1;i<=n;i++){
        H.push (v[i].p);
        suma += v[i].p;
        if (H.size() > k){ /// sunt mai mult de k plase
            suma -= H.top();
            H.pop(); /// scoatem plasa din varf
        }
        /// aux[t] - nr max de pesti pe care ii putem prinde daca plasele au timpul mai mic sau egal cu t
        aux[v[i].t] = max (aux[v[i].t],suma);
    }

    /// best[t] - nr maxim de pesti pe care ii putem prinde de la momentul 0 la momentul t
    /// best[t] = max (best[t]+aux[1],best[t-2]+aux[2],...,best[t-tmax]+aux[tmax]);
    for (i=1;i<=t;i++){
        for (j=0;j<=min(i,v[n].t);j++)
            best[i] = max (best[i],aux[j]+best[i-j]);
    }
    fout<<best[t];

    return 0;
}