Cod sursa(job #2288788)

Utilizator Iulia25Hosu Iulia Iulia25 Data 23 noiembrie 2018 21:28:52
Problema Lupul Urias si Rau Scor 68
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

ifstream fin ("lupu.in");
ofstream fout ("lupu.out");

long long total;
int urm = 1, n, x, l, d, k, y, mod, b[320];
bool v[100001];

struct oaie  {
  int nr, val;
} o[100001];

bool cmp (oaie a, oaie b)  {
  return (a.val > b.val || a.val == b.val && a.nr < b.nr);
}

int main()  {
  fin >> n >> x >> l;
  for (int i = 1; i <= n; ++i)  {
    fin >> d >> o[i].val;
    o[i].nr = (x - d) / l + 1;
    if (o[i].nr > k)
      k = o[i].nr;
  }
  mod = sqrt(n);
  b[mod] = n - mod * mod;
  sort (o + 1, o + n + 1, cmp);
  for (int i = 1; i <= k; ++i)  {
    y = o[i].nr / mod;
    while (b[y] == mod)
      --y;
    y = min(y * mod + mod - 1, o[i].nr);
    while (v[y])
      --y;
    if (y != 0)  {
      v[y] = true, total += o[i].val;
      ++b[y / mod];
    }
    else if (k < n)
      ++k;
  }
  fout << total;
}