Pagini recente » Cod sursa (job #2773862) | Cod sursa (job #2851405) | Cod sursa (job #3230111) | Cod sursa (job #2939278) | Cod sursa (job #2953905)
#include <fstream>
#include<algorithm>
#define MAXN 100000
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int sefi[MAXN*6];///timpii in care ies oile
pair<int, int> a[MAXN];
bool cmp(pair<int, int> x, pair<int, int> y){
return x.first>y.first;
}
int find(int x){
if(sefi[x]==x)
return x;
else
return sefi[x]=find(sefi[x]);///compresia caii
}
void unify(int x, int y){
int sefX=find(x), sefY=find(y);
sefi[sefY]=sefX;
}
int main()
{
int n, dist, delta; fin>>n>>dist>>delta;
int maxTime=0;
for(int i=0; i<n; i++){
fin>>a[i].second>>a[i].first;
a[i].second=((dist-a[i].second)/delta)+1;///timpul in care oaia iese din interval
maxTime=max(maxTime, a[i].second);
}
for(int i=0; i<maxTime+1; i++)
sefi[i]=i;
sort(a, a+n, cmp);///voi vrea sa iau cele mai lanoase oi, daca pot
long long checo=0;
for(int i=0; i<n; i++){
int x=a[i].second;
int place=find(x);
if(x>0){
if(place>0&&a[i].second>0){///daca se mai poate lua oaie
checo+=(long long)a[i].first;
unify(place-1, place);///nota: unify il leaga pe primul la al doilea, asa ca trb in ord asta
}
}
}
fout<<checo;
return 0;
}