Cod sursa(job #2823809)

Utilizator db_123Balaban David db_123 Data 29 decembrie 2021 19:16:11
Problema Lupul Urias si Rau Scor 12
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.78 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;
    }
};
class Compare1{
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;
    int max1,max2;
    priority_queue<Oaie,vector<Oaie>,Compare1> Q1(v.begin()+1,v.end());
    priority_queue<Oaie,vector<Oaie>,Compare> Q2;

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

    int i =1 ;
    bool ok = false;
    while(maxZona>=0){
        ok = false;
        while(i<=n){
            if(v[i].zona == maxZona) Q2.push(v[i++]),ok=true;
            else break;
        }
        if(!ok) i++;

        while(!Q1.empty() and Q1.top().zona >maxZona) Q1.pop();

        max1 = 0 ; max2 = 0;
        Oaie a1,a2,b1;
        if(!Q1.empty()){
            a1 = Q1.top();
            Q1.pop();
            if(!Q1.empty()){
                a2 = Q1.top();
                if(!Q2.empty()){
                    b1 = Q2.top();
                    if(a2.cantitateLana > b1.cantitateLana){
                        res+=a1.cantitateLana;
                    }
                    else {
                        res+=b1.cantitateLana;
                        Q1.push(a1);
                    }
                }
                else
                {
                     res+=a1.cantitateLana;
                }
            }
            else if (!Q2.empty()){
                res+=b1.cantitateLana;
                Q1.push(a1);
            }
            else{
                res+=a1.cantitateLana;
            }
        }
//        if(!Q1.empty())
//            max1 =  Q1.top().cantitateLana;
//        if(!Q2.empty())
//            max2 =  Q2.top().cantitateLana;
//
//        res += max(max1,max2);

        while(!Q2.empty())Q2.pop();

        maxZona--;
    }

    cout<<res;
}

int main() {

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