Cod sursa(job #3316992)

Utilizator NERDVANA_MIHNEA_PURCAREAMihnea Purcarea NERDVANA_MIHNEA_PURCAREA Data 21 octombrie 2025 16:56:55
Problema Lupul Urias si Rau Scor 84
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.49 kb
#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;
}