Cod sursa(job #2288576)

Utilizator stefaannaStefana Mitrea stefaanna Data 23 noiembrie 2018 17:37:29
Problema Lupul Urias si Rau Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

struct oaie {
    int dist, lana;
};

bool cmp(oaie o1, oaie o2) {
    return o1.dist < o2.dist;
}

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

    priority_queue<pair<int,int> > distanta;
    int N, X, L;
    f>>N>>X>>L;
    int x,y;

    oaie o;
    vector<oaie> oi;
    for (int i=0; i<N; i++) {
        //f>>x>>y;
        //distanta.push(make_pair(x,y));
        f>>o.dist>>o.lana;
        oi.push_back(o);
    }
/*
    for (int i=0; i<N; i++) {
        pair<int,int> p;
        p = distanta.top();
        cout<<p.first<<' '<<p.second<<'\n';
        distanta.pop();
    }
*/
    sort(oi.begin(), oi.end(), cmp);//sortate descrescator dupa distanta
    int nr_maxim_alegeri;
    nr_maxim_alegeri = X/L + 1;

    int sum = 0, j = 0;
    priority_queue<int> lana;
    for (int i=nr_maxim_alegeri; i>=1; i--) {

        //cout<<"intervalul curent: "<<X-i*L+1<<' '<<X-(i-1)*L<<'\n';
        //cout << oi[j].dist << "\n";
        while (X-i*L+1 <= oi[j].dist && oi[j].dist <= X-(i-1)*L && j<N) {
               // cout << oi[j].lana << "\n";
            lana.push(oi[j].lana);
            j++;
        }
        if(!lana.empty()){
            sum += lana.top();
            //cout << "am ales" << lana.top() << "\n";
            lana.pop();
        }
    }
    g<<sum;

    return 0;
}