Cod sursa(job #3316773)

Utilizator NERDVANA_MIHNEA_PURCAREAMihnea Purcarea NERDVANA_MIHNEA_PURCAREA Data 20 octombrie 2025 19:18:21
Problema Lupul Urias si Rau Scor 32
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <stdio.h>
#include <algorithm>

#define DEBUG 0
#define MAXN 100000

struct oneSheep{
	int time;
	int wool;
};
oneSheep sheep[MAXN];


static inline void mySwap(int &a, int &b){
	a = a^b;
	b = a^b;
	a = a^b;
}

struct heap{
	int heap[MAXN+1];
	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;
  unsigned long long maxWool;

	in = fopen("lupu.in", "r");
	fscanf(in, "%d%d%d", &n, &maxDist, &distPlus);
	for(i = 0; i < n; i++){
		fscanf(in, "%d%d", &dist, &sheep[i].wool);
		sheep[i].time = (maxDist-dist)/distPlus + 1;//Calculates the time a sheep will be added
    if(maxDist < dist)
      sheep[i].time = -1;
	}	
	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;
  while(pos < n){
    while(sheep[pos].time == sheep[lpos].time){
      if(sheep[lpos].time > 0)
        sheepTime.AddSheep(pos);

      lpos = pos;
      pos++;
    }
    if(sheep[lpos].time > 0)
      maxWool += sheep[sheepTime.GiveBestSheep()].wool;

    lpos = pos;
  }
	fclose(in);


	out = fopen("lupu.out", "w");
  fprintf(out, "%llu\n", maxWool);
	fclose(out);

  return 0;
}