Cod sursa(job #2824471)

Utilizator db_123Balaban David db_123 Data 2 ianuarie 2022 14:19:45
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.45 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

/// https://www.infoarena.ro/job_detail/2823893

using namespace std;

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

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

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

bool sortVector(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>,Compare> Q;
    priority_queue<Oaie,vector<Oaie>,CompareDESC> Q_Sol;
    stack<Oaie> S,S_Temp;


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

    int i =1,zona = maxZona,howMany=1,k=1;
    while(zona >=0){

        ///cout << "\n\nANALYZE zone " << zona << "\n\n";

        k=1;                                        /// resetting

        while(!Q.empty())Q.pop();
        while(!S.empty())S.pop();
        while(!S_Temp.empty())S_Temp.pop();

        while( i<=n and v[i].zona == zona){         /// load full zone
            Q.push(v[i]);
            ///cout << "adding from zone dist : " << v[i].distInit << " lana : " << v[i].cantitateLana << " \n";
            i++;
        }
        ///cout<<"\n";
        while(k <= howMany and !Q.empty()){         /// from each zone take only the how many items
            S.push(Q.top());
            ///cout << "adding to STACK from zone dist : " << Q.top().distInit << " lana : " << Q.top().cantitateLana << " \n";
            Q.pop();
            k++;
        }
        ///cout<<"\n";
        while(!S.empty() and !Q_Sol.empty() and S.top().cantitateLana >= Q_Sol.top().cantitateLana ){ /// remove smaller from sol
            ///cout << "removing from SOL dist : " << Q_Sol.top().distInit << " lana : " << Q_Sol.top().cantitateLana << " \n";
            Q_Sol.pop();
            S_Temp.push(S.top());
            S.pop();
        }

        while(!S.empty() and S.size()>1) S.pop();

        if(!S.empty()){
            Q_Sol.push(S.top());
            ///cout << "adding to SOL dist : " << S.top().distInit << " lana : " << S.top().cantitateLana << " \n";
            S.pop();
        }

        while(!S_Temp.empty()){
            Q_Sol.push(S_Temp.top());
            ///cout << "adding to SOL better values dist : " << S_Temp.top().distInit << " lana : " << S_Temp.top().cantitateLana << " \n";
            S_Temp.pop();
        }

        howMany++;
        zona--;
    }

    ///cout << "IN FINAL we have " << Q_Sol.size() << " items \n";

    i = 0;
    while(!Q_Sol.empty()){
            res += Q_Sol.top().cantitateLana;
            ///cout << " finalizing  " << Q_Sol.top().distInit << " lana " << Q_Sol.top().cantitateLana << "\n";
            Q_Sol.pop();
    }
    cout<<res;
}

int main() {

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