Pagini recente » Istoria paginii runda/mnmxmnmxmnmx_what/clasament | Cod sursa (job #768231) | Cod sursa (job #1324073) | Cod sursa (job #997217) | Cod sursa (job #2032529)
#include <fstream>
#include <queue>
#include <algorithm>
#define DIM 50001
using namespace std;
int n,k,t,i,j,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);
}
for (i=1;i<=t;i++)
aux[i] = max (aux[i],aux[i-1]);
/// 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;
}