Cod sursa(job #2288775)

Utilizator Iulia25Hosu Iulia Iulia25 Data 23 noiembrie 2018 21:00:30
Problema Lupul Urias si Rau Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int urm = 1, n, x, l, u[100001], d, k, y;
long long total;

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;
    u[i] = i;
  }
  sort (o + 1, o + n + 1, cmp);
  for (int i = 1; i <= n; ++i)  {
    if (o[i].nr >= urm)  {
      ++u[o[i].nr];
      y = o[i].nr;
      while (u[y] > y + 1)  {
        u[y - 1] += u[y] - (y + 1);
        u[y] = y + 1;
        --y;
      }
      if (y <= 0)
        continue;
      ++k;
      urm = u[k];
      total += o[i].val;
    }
  }
  fout << total;
}