Cod sursa(job #2812627)

Utilizator Teodor94Teodor Plop Teodor94 Data 4 decembrie 2021 20:36:45
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;

struct Sheep {
  int dist, value;
};

bool cmp(const Sheep& a, const Sheep& b) {
  return a.dist < b.dist;
}

#define MAX_N 100000

Sheep sheeps[MAX_N];
priority_queue<int> heap;

void insert(int value) {
  heap.push(value);
}
int extractTop() {
  int top;

  top = 0;
  if (!heap.empty()) {
    top = heap.top();
    heap.pop();
  }

  return top;
}

int main() {
  FILE *fin, *fout;
  fin = fopen("lupu.in", "r");
  fout = fopen("lupu.out", "w");

  int n, x, l, d, i;
  long long totalValue;

  fscanf(fin, "%d%d%d", &n, &x, &l);
  for (i = 0; i < n; ++i)
    fscanf(fin, "%d%d", &sheeps[i].dist, &sheeps[i].value);

  sort(sheeps, sheeps + n, cmp);

  d = x % l;
  i = 0;
  totalValue = 0;
  while (d <= x) {
    while (i <= n && sheeps[i].dist <= d)
      insert(sheeps[i++].value);

    totalValue += extractTop();
    d += l;
  }

  fprintf(fout, "%lld\n", totalValue);

  fclose(fin);
  fclose(fout);
  return 0;
}