Cod sursa(job #2823891)

Utilizator db_123Balaban David db_123 Data 29 decembrie 2021 22:54:11
Problema Lupul Urias si Rau Scor 72
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <bitset>

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){
        //if (a.zona == b.zona)
            return a.cantitateLana < b.cantitateLana;
        //return a.zona > b.zona;
    }
};

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);
        }
        //cout << "( " << v[i].distInit << " " << v[i].cantitateLana << " " << v[i].zona << "\n";
    }
    //cout << "maxZone : " << maxZona << "\n";
}

void solve(){
    long long int res=0;
    priority_queue<Oaie,vector<Oaie>,Compare> Q;

    sort(v.begin()+1,v.end(),sortVector);
    //for(int i =1 ; i<=n ; i++){
    //        cout << " .... " << v[i].distInit << " " << v[i].cantitateLana << " " << v[i].zona << "\n";
    //}
    //cout<<"\n\n";

    int i =1,zona = 0;
    bool ok;
    while(zona <= maxZona){
        while( i<=n and v[i].zona == zona){
      //      cout << " pushing " << v[i].distInit << " " << v[i].cantitateLana << " " << v[i].zona << "\n";
            Q.push(v[i]);
            i++;
        }

        if(!Q.empty()){
            res += Q.top().cantitateLana;
        //    cout << "ADDING : " << Q.top().distInit << " " << Q.top().cantitateLana << " " << Q.top().zona << "\n ";
            Q.pop();
        }

        //while(!Q.empty())Q.pop();

        zona++;
        //cout << "new value for zona : " << zona << " i : "<< i << "\n";
    }

    cout<<res;
}

int main() {

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