Cod sursa(job #2812643)

Utilizator Teodor94Teodor Plop Teodor94 Data 4 decembrie 2021 20:50:43
Problema Lupul Urias si Rau Scor 52
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 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];
bool marked[MAX_N];
int markedSize;

void insert(int pos) {
  marked[pos] = true;
  markedSize = pos + 1;
}
int extractTop() {
  int i, top;

  i = 0;
  top = -1;
  while (i < markedSize) {
    if (marked[i] && (top == -1 || sheeps[i].value > sheeps[top].value))
      top = i;

    ++i;
  }

  if (top != -1) {
    marked[top] = false;
    top = sheeps[top].value;
  } else
    top = 0;

  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(i++);

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

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

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