Cod sursa(job #2824325)

Utilizator db_123Balaban David db_123 Data 1 ianuarie 2022 17:46:37
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.9 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

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

class Oaie{
public:
    int distInit;
    int cantitateLana;
    int zona;
};

class CompareDESC{
public:
    bool operator()(Oaie a,Oaie b){
        return a.cantitateLana > b.cantitateLana;
    }
};
class CompareASC{
public:
    bool operator()(Oaie a,Oaie b){
        return a.cantitateLana < b.cantitateLana;
    }
};
bool sortVectorByZona(Oaie a , Oaie b){
    return a.zona > b.zona;
}

int n,x,lng;///n:nr oi,x:distanta maxima lup oi,l:distanta de departare oi lup
int maxZona=0;
vector<Oaie> v;


void read(){
    cin>>n>>x>>lng;

    v.resize(n+1,{0,0,-1});

    for(int i=1;i<=n;i++){
        cin>>v[i].distInit>>v[i].cantitateLana;
        if(v[i].distInit>x)
            v[i].zona=-1;
        else{
            v[i].zona = (v[i].distInit + 1) / lng;
            maxZona =  max(maxZona,v[i].zona);
        }
    }
}

void solve(){
    long long int res=0;
    priority_queue<Oaie,vector<Oaie>,CompareDESC> Q_Final;
    priority_queue<Oaie,vector<Oaie>,CompareASC> Q_Zona;

    sort(v.begin()+1,v.end(),sortVectorByZona);

    int i=1,zona = maxZona,nrMaximOi=1,cnt=1;
    bool ok;
    while( i<=n ){
        cnt =1;
        ok = false;
        while(!Q_Zona.empty()) Q_Zona.pop();

        //cout << "Adding zona : " << zona<< "\n";
        /// move all from v[i] zona to Q_zona
        while(v[i].zona == zona){
            Q_Zona.push(v[i]);
            //cout << "element dist : " << v[i].distInit << " cant : " << v[i].cantitateLana<< "\n";
            i++;
            ok = true;
        }
        if(ok) i--;

        //cout << "\n\n Checking for FINAL " << nrMaximOi << " elements "<< "\n";

        /// ready to move from Q_zona to Q_final
        ///     only the first nrMaximOi
        ///     2 cases
        ///         a. Q_Zona > Q_Final
        ///                 Q_Final.pop
        ///                 Q_Final.push(Q_Zona.top())
        ///         b. Q_Zona < Q_Final
        ///                 Q_Final.push(Q_Zona.top())
        while(cnt <= nrMaximOi){
            if(!Q_Zona.empty() and Q_Final.empty()){
                Q_Final.push(Q_Zona.top());
                //cout << "add element dist : " << Q_Zona.top().distInit << " cant : " << Q_Zona.top().cantitateLana<< "\n\n";
                Q_Zona.pop();
                cnt++;
            }
            else if(!Q_Zona.empty() and Q_Zona.top().cantitateLana > Q_Final.top().cantitateLana){
                //cout << "\nremove from Final element dist : " << Q_Final.top().distInit << " cant : " << Q_Final.top().cantitateLana<< "\n";
                Q_Final.pop();
                Q_Final.push(Q_Zona.top());
                //cout << "add element dist : " << Q_Zona.top().distInit << " cant : " << Q_Zona.top().cantitateLana<< "\n\n";
                Q_Zona.pop();
                cnt++;
            }
            else if(!Q_Zona.empty() and Q_Zona.top().cantitateLana <= Q_Final.top().cantitateLana){
                Q_Final.push(Q_Zona.top());
                //cout << "add element dist : " << Q_Zona.top().distInit << " cant : " << Q_Zona.top().cantitateLana<< "\n\n";
                Q_Zona.pop();
                cnt++;
            }
            else
                break;
        }

        zona--;
        nrMaximOi++;
        i++;
    }

    i =0;
    //cout << "\n\n FINAL   " << maxZona + 1 << " elements "<< "\n";
    int total = Q_Final.size() - (maxZona+1);
    while(!Q_Final.empty() and total>0){Q_Final.pop();}

    while(!Q_Final.empty()){
        res += Q_Final.top().cantitateLana;
        //cout << "element dist : " << Q_Final.top().distInit << " cant : " << Q_Final.top().cantitateLana<< "\n";
        Q_Final.pop();
    }

    cout<<res;
}

int main() {

    read();
    solve();
    return 0;
}