Cod sursa(job #3198600)

Utilizator Allie28Radu Alesia Allie28 Data 29 ianuarie 2024 20:37:13
Problema Lupul Urias si Rau Scor 84
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");

const int LMAX = 100005;
priority_queue<int> Q;
struct interval{
    int st, dr;
    bool operator < (interval b) {
        if (st < b.st) return true;
        else if (st == b.st && dr > b.dr) return true;
        return false;
    }
}v[LMAX];

int main() {
    int n, i, x, l;
    fin>>n>>x>>l;
    for (i = 0; i < n; i++) {
        fin>>v[i].st>>v[i].dr;
        v[i].st = (x - v[i].st)/l + 1; //dupa cate atacuri oaia iese din raza lupului
    }
    sort(v, v + n);
    long long lana = 0; //distanta parcursa de oi
    int maxsizeQ;
    i = 0;
    while (i < n) {
        //adaug maximul de elemente posibile
        maxsizeQ = v[i].st;
        int locpos = maxsizeQ - Q.size();
        while (i < n && v[i].st == maxsizeQ && locpos > 0) {
            locpos--;
            Q.push(-v[i].dr);
            i++;
        }
        while (i < n && v[i].st == maxsizeQ) {
            if (-Q.top() < v[i].dr) {
                Q.pop();
                Q.push(-v[i].dr);
            }
            i++;
        }
    }
    while (!Q.empty()) {
        lana = lana - Q.top();
        Q.pop();
    }
    fout<<lana;

    fin.close();
    fout.close();
    return 0;
}