Pagini recente » Cod sursa (job #730912) | Cod sursa (job #949036) | Cod sursa (job #865789) | Cod sursa (job #1190514) | Cod sursa (job #2504983)
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
long long n,i,x,l,sol,tmax,d,j;
struct oaie{
long long lana,pas;
bool operator<(const oaie &other) const { //am stat 1 ora sa caut cum fac operator de comparare
if (lana==other.lana) //pe structuri
return pas>other.pas;
return lana<other.lana;
}
};
vector<oaie> v[DIM];
oaie a,last;
priority_queue<oaie> q;
int main() {
fin>>n>>x>>l;
//calculam nr maxim de pasi dupa care poate ajunge lupul la o oaie
//si punem toate oile cu un anumit nr de pasi intr-un vector
for (i=1;i<=n;i++) {
fin>>d>>a.lana;
if (x>d) {
a.pas=(x-d)/l+1;
tmax=max(a.pas,tmax);
v[a.pas].push_back(a);
}
}
//metoda greedy->la fiecare pas de la tmax la 1 punem oile din v[pas] intr-un priority queue
//si extragem maximul din pq
for (i=tmax;i>=1;i--) {
for (j=0;j<v[i].size();j++)
q.push(v[i][j]);
if (!q.empty()) {
sol+=q.top().lana;
q.pop();
}
}
fout<<sol;
return 0;
}