Pagini recente » Cod sursa (job #591032) | Cod sursa (job #2177923) | Cod sursa (job #1586817) | Cod sursa (job #2314306) | Cod sursa (job #2824325)
#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;
}