Cod sursa(job #3220847)

Utilizator Robilika2007Robert Badea Robilika2007 Data 5 aprilie 2024 01:11:02
Problema Lupul Urias si Rau Scor 12
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

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

struct oaie
{
    int dist, wool, section;
};

#define MAX_N 100000
oaie v[MAX_N];

priority_queue<int> heap;

bool cmp (oaie a, oaie b)
{
    if(a.section == b.section)
        return a.wool > b.wool;
    return a.section < b.section;
}

int extractTop() {
  int top;

  top = 0;
  if (!heap.empty()) {
    top = heap.top();
    heap.pop();
  }

  return top;
}

int main()
{
    int n, x, l;
    in >> n >> x >> l;
    for(int i = 0; i < n; ++i)
    {
        in >> v[i].dist >> v[i].wool;
        v[i].section = ( x - v[i].dist ) / l + 1;

        if(v[i].section < 0) v[i].section = -1;
    }

    sort(v, v + n, cmp);

    int curr = v[0].section, no = 0, nr = 0, ans = 0;
    for(int i = 0; i < n; ++i)
    {
        if(v[i].section != curr)
        {
            curr++;
            no = 0;
        }

        //cout << v[i].wool << " " << v[i].section << " | " << no << " " << curr << " " << nr << " " << ans << '\n';
        if(no <= curr - nr)
        {

            //this can enter
            nr++;
            no++;
            ans += v[i].wool;
            heap.push(v[i].wool);
        } else if(no < curr)
        {
            no++;
            int top = extractTop();
            if(v[i].wool > top)
            {
                ans += v[i].wool - top;
                heap.push(v[i].wool);
            }
        }
    }

    out << ans;


    return 0;
}