Pagini recente » Cod sursa (job #3271480) | Cod sursa (job #2828062) | Cod sursa (job #2596144) | Cod sursa (job #2888427) | Cod sursa (job #1867028)
#include <cstdio>
#include <algorithm>
#define MAXN 50000
#define MAXK 50000
typedef struct{
int p, t;
}pr;
pr v[MAXN];
int heap[MAXK], dh = 0;
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, sum = 0, rez = 0;
fscanf(in, "%d%d%d", &k, &n, &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];
heap[0] = v[i].p;
cobor(0);
}
}
if(t / v[i].t * sum > rez)
rez = t / v[i].t * sum;
}
FILE *out = fopen("peste.out", "w");
fprintf(out, "%d", rez);
fclose(out);
return 0;
}