Cod sursa(job #2533248)

Utilizator sichetpaulSichet Paul sichetpaul Data 28 ianuarie 2020 21:04:25
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>
#define Nmax 100005
#define ll long long
using namespace std;

ifstream f("lupu.in");
ofstream g("lupu.out");

int N, X, L;
ll ans;

priority_queue<int> Q;
struct sheep{
  int d, nr;
};
sheep v[Nmax];
bool cmp(sheep a, sheep b) {
   if (a.d == b.d) return a.nr > b.nr;
   return a.d < b.d;
}
int main()
{
    f >> N >> X >> L;
    for (int i = 1; i <= N; ++i)
        f >> v[i].d >> v[i].nr;
    sort(v + 1, v + N + 1, cmp);

    int pos = 0;
    for (int i = N; i >= 1; --i)
    if (v[i].d <= X) {
        pos = i;
        break;
    }

    int i = pos, len = 0;
    while (i >= 1) {
        int j = i;
        while (j >= 1 && v[j].d + len > X)
            Q.push(v[j].nr), --j;
        if (!Q.empty()) ans += Q.top();

        while (!Q.empty())
             Q.pop();
        len += L;
        i = j;
    }

    g << ans << '\n';

    return 0;
}