Cod sursa(job #1396973)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 23 martie 2015 10:33:52
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<bits/stdc++.h>
#define mp make_pair
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

const int NMAX=100005;
const int XMAX=200005;

int n,x,l,f[XMAX];
PII a[NMAX];
long long sol;

inline int Father(int x)
{
    int w,z;
    z=x;
    while (x!=f[x]) x=f[x];
    while (z!=f[z])
    {
        w=f[z];
        f[z]=x;
        z=w;
    }
    return x;
}

int main()
{
    int i,aux;
    fin>>n>>x>>l;
    for (i=1;i<=n;i++) fin>>a[i].se>>a[i].fi;
    sort(a+1,a+n+1);
    for (i=1;i<XMAX;i++) f[i]=i;
    for (i=n;i>=1;i--)
    {
        if (x<a[i].se) aux=0;
        aux=((x-a[i].se)/l)+1;
        if (aux==0) continue;
        aux=Father(min(200000,aux));
        if (aux==0) continue;
        f[aux]=aux-1;
        sol+=a[i].fi;
    }
    fout<<sol<<"\n";
    return 0;
}