Pagini recente » Cod sursa (job #1631796) | Cod sursa (job #16929) | Cod sursa (job #245928) | Cod sursa (job #2839725) | Cod sursa (job #1867049)
#include <cstdio>
#include <algorithm>
#define MAXN 50000
#define MAXK 50000
#define MAXT 1000
typedef struct{
int p, t;
}pr;
pr v[MAXN];
int heap[MAXK], dh = 0;
int smax[MAXT];
int d[MAXK + 1];
bool cmp(pr a, pr b){
if(a.t < b.t)
return 1;
return 0;
}
inline void intersch(int x, int y){
int aux;
aux = heap[x];
heap[x] = heap[y];
heap[y] = aux;
}
inline void urc(int x){
while(x > 0 && heap[(x - 1) / 2] > heap[x]){
intersch((x - 1) / 2, x);
x = (x - 1) / 2;
}
}
inline void cobor(int x){
int best = x;
do{
x = best;
if(heap[best] > heap[2 * x + 1])
best = 2 * x + 1;
if(2 * x + 2 < dh && heap[best] > heap[2 * x + 2])
best = 2 * x + 2;
intersch(x, best);
}while(2 * best + 1 < dh && best != x);
}
int main(){
FILE *in = fopen("peste.in", "r");
int k, n, t, i, j, sum = 0, tmax;
fscanf(in, "%d%d%d", &n, &k, &t);
for(i = 0; i < n; i++)
fscanf(in, "%d%d", &v[i].p, &v[i].t);
fclose(in);
std::sort(v, v + n, cmp);
for(i = 0; i < n; i++){
if(dh < k){
sum += v[i].p;
heap[dh] = v[i].p;
urc(dh);
dh++;
}
else{
if(heap[0] < v[i].p){
sum -= heap[0];
sum += v[i].p;
heap[0] = v[i].p;
cobor(0);
}
}
smax[v[i].t] = sum;
}
tmax = v[n - 1].t;
for(i = 1; i <= t; i++)
for(j = 1; j <= i && j <= tmax; j++)
if(d[i] < d[i - j] + smax[j])
d[i] = d[i - j] + smax[j];
FILE *out = fopen("peste.out", "w");
fprintf(out, "%d", d[t]);
fclose(out);
return 0;
}