Cod sursa(job #1541960)

Utilizator tudorcomanTudor Coman tudorcoman Data 4 decembrie 2015 19:40:25
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 0.95 kb

#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;
typedef long long i64;

const i64 maxN = 100000;
i64 N, x, L;

i64 ans;
priority_queue<i64> Heap;

class Sheep {
public:
  i64 D, A;
  Sheep(i64 _D = 0, i64 _A = 0) : D(_D), A(_A) {}
} v[maxN + 1];

class cmp {
public:
  inline bool operator () (const Sheep x, const Sheep y) {
    return x.D < y.D;
  }
};

int main() {
  freopen("lupu.in", "r", stdin);
  freopen("lupu.out", "w", stdout);

  scanf("%d %d %d", &N, &x, &L);
  for(register int i = 1; i <= N; ++ i) {
    int D, A;
    scanf("%d %d", &D, &A);
    v[i] = Sheep(D, A);
  }

  sort(v + 1, v + N + 1, cmp());
  int j = 1;

  for(register int i = 0; i <= x and j <= N; i += L) { /// pasi lupului
    while(j <= N and v[j].D <= i)
      Heap.push(v[j ++].A);
    if(!Heap.empty()) {
      ans += Heap.top();
      Heap.pop();
    }
  }

  printf("%lld\n", ans);
  return 0;
}