Pagini recente » Cod sursa (job #2814233) | Cod sursa (job #2739449) | Cod sursa (job #587215) | Cod sursa (job #2934759) | Cod sursa (job #2824471)
#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;
}