Pagini recente » Cod sursa (job #196971) | Cod sursa (job #233180) | Cod sursa (job #2270750) | Cod sursa (job #2762215) | Cod sursa (job #2823529)
#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;
}