Cod sursa(job #2912621)

Utilizator Alex_HossuHossu Alexandru Alex_Hossu Data 9 iulie 2022 15:18:24
Problema Lupul Urias si Rau Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 100000

struct SheepData {
  int d;
  int a;
};
SheepData sheep[MAX_N];

//struct Node {
  //vector<int> nodes;
//};
//vector<Node> heap;

struct Node {
  int nodes[100];
};
Node heap[100];


bool cmp(SheepData a, SheepData b) { return a.d > b.d; }

static inline void swapVectElem(int depth, int indInRow) {
  int aux = heap[depth].nodes[indInRow];
  heap[depth].nodes[indInRow] = heap[depth - 1].nodes[indInRow / 2];
  heap[depth - 1].nodes[indInRow / 2] = aux;
}

void updateHeap(int indInRow, int depth) {
  if (depth <= 0)
    return;
  if (sheep[heap[depth].nodes[indInRow]].a < sheep[heap[depth - 1].nodes[indInRow / 2]].a)
    swapVectElem(depth, indInRow);
  updateHeap(indInRow / 2, depth - 1);
}

int main() {
  FILE *fin, *fout;
  int n, x, d;
  int i, heapDepth, sum;
  int nrInHeap, eated;

  fin = fopen("lupu.in", "r");

  fscanf(fin, "%d%d%d", &n, &x, &d);

  //heap.resize(n + 1);
  //for (i = 0; i < n; i++)
    //heap[i].nodes.resize((1 << i) + 1);

  for (i = 1; i <= n; i++)
    fscanf(fin, "%d%d", &sheep[i].d, &sheep[i].a);

  fclose(fin);

  eated = 0;
  nrInHeap = 0;
  heapDepth = 0;
  sheep[0].d = 0;
  sheep[0].a = 0;
  heap[0].nodes[0] = -1;
  sort(sheep + 1, sheep + n + 1, cmp);
  for (i = 1; i <= n; i++) {
    if (heap[0].nodes[0] == -1) {
      if (sheep[i].d <= x) {
        heap[0].nodes[0] = i;
        eated++;
        heapDepth++;
      }
    } else {
      if (sheep[heap[0].nodes[0]].a >= sheep[i].a) {
        if (sheep[i].d + eated * d <= x) {
          heap[heapDepth].nodes[nrInHeap] = i;
          eated++;
          nrInHeap++;
          updateHeap(nrInHeap - 1, heapDepth);
        }
      } else if (sheep[heap[0].nodes[0]].a < sheep[i].a && sheep[i].d + eated * d > x) {
        heap[0].nodes[0] = i;
        for (int j = 0; j < nrInHeap; j++)
          updateHeap(j, heapDepth);
      } else if (sheep[heap[0].nodes[0]].a < sheep[i].a) {
        if (sheep[i].d + eated * d <= x) {
          heap[heapDepth].nodes[nrInHeap] = i;
          eated++;
          nrInHeap++;
          updateHeap(nrInHeap - 1, heapDepth);
        }
      }
    }
    if (nrInHeap == (1 << heapDepth)) {
      nrInHeap = 0;
      heapDepth++;
    }

    //for (int depth = 0; depth < heapDepth + 1; depth++) {
      //for (int pos = 0; pos < 1 << depth; pos++) {
        //printf("%d ", heap[depth].nodes[pos]);
      //}
      //putc('\n', stdout);
    //}
    //putc('\n', stdout);
  }

  sum = 0;
  for (int depth = 0; depth < heapDepth + 1; depth++) {
    for (int pos = 0; pos < 1 << depth; pos++) {
      //printf("%d ", heap[depth].nodes[pos]);
      sum = sum + sheep[heap[depth].nodes[pos]].a;
    }
    //putc('\n', stdout);
  }
  //putc('\n', stdout);

  fout = fopen("lupu.out", "w");
  fprintf(fout, "%d\n", sum);
  fclose(fout);

  return 0;
}