Pagini recente » Borderou de evaluare (job #2973056) | Cod sursa (job #3353576) | Cod sursa (job #3335309) | Cod sursa (job #3301427) | Cod sursa (job #3316992)
#include <stdio.h>
#include <algorithm>
#define DEBUG 0
#define MAXN 100000
struct oneSheep{
int time;
int wool;
};
oneSheep sheep[MAXN+1];
static inline void mySwap(int &a, int &b){
a = a^b;
b = a^b;
a = a^b;
}
struct heap{
int heap[MAXN+2];
int size = 0;
void HeapUp(int pos){
while(pos > 1 && sheep[heap[pos]].wool > sheep[heap[(pos>>1)]].wool){
mySwap(heap[pos], heap[(pos>>1)]);
pos = (pos >> 1);
}
}
void HeapDown(int pos){
int st, dr, best;
while((pos << 1) <= size){
st = (pos << 1);
best = st;
dr = st+1;
if(dr <= size && sheep[heap[dr]].wool > sheep[heap[st]].wool)
best = dr;
if(sheep[heap[pos]].wool < sheep[heap[best]].wool){
mySwap(heap[pos], heap[best]);
pos = best;
}else{
break;
}
}
}
void AddSheep(int id){
size++;
heap[size] = id;
HeapUp(size);
}
int GiveBestSheep(){
int val;
val = heap[1];
mySwap(heap[1], heap[size]);
size--;
HeapDown(1);
return val;
}
};
heap sheepTime;
int main(){
FILE *in, *out;
int n, maxDist, distPlus, i, dist, pos, lpos, tn;
unsigned long long maxWool;
in = fopen("lupu.in", "r");
fscanf(in, "%d%d%d", &n, &maxDist, &distPlus);
if(distPlus > 0){
tn = 0;
for(i = 0; i < n; i++){
fscanf(in, "%d%d", &dist, &sheep[i].wool);
sheep[i-tn].time = (maxDist-dist)/distPlus + 1;//Calculates the time a sheep will be added
if(maxDist < dist)
tn++;
}
n-=tn;
std::sort(sheep, sheep+n, [](const oneSheep &a, const oneSheep &b){
return a.time > b.time;
});//Sorts the sheeps in descending order from when they get added;
if(DEBUG){
for(i = 0; i < n; i++)
printf("%d: %d %d\n", i, sheep[i].time, sheep[i].wool);
printf("\n\n");
}
pos = lpos = 0;
maxWool = 0;
sheep[n].time = 0;
while(pos < n){
lpos = pos;
while(sheep[pos].time == sheep[lpos].time){
sheepTime.AddSheep(pos);
lpos = pos;
pos++;
}
for(i = sheep[pos].time; i < sheep[lpos].time; i++)
maxWool += sheep[sheepTime.GiveBestSheep()].wool;
//printf("%d (%d - %d %d)\n", maxWool, sheep[lpos].time, sheep[pos].time, i-sheep[lpos].time);
}
}else{
maxWool = 0;
for(i = 0; i < n; i++){
fscanf(in, "%d%d", &dist, &sheep[i].wool);
if(dist <= maxDist)
maxWool += sheep[i].wool;
}
}
fclose(in);
out = fopen("lupu.out", "w");
fprintf(out, "%llu\n", maxWool);
fclose(out);
return 0;
}