Cod sursa(job #1735356)

Utilizator liviu23Liviu Andrei liviu23 Data 29 iulie 2016 16:48:17
Problema Lupul Urias si Rau Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <algorithm>
#include <fstream>
#define f first
#define s second
using namespace std;

int n,x,l,tmx,*parent;
pair<int,int> v[100005];

bool check(int p) {
    while(parent[p]!=p&&p!=0)
        p=parent[p];
    parent[p]=p-1;
    if(parent[p]<0)
        return false;
    return true;
}

int main()
{
    ifstream fin("lupu.in");
    ofstream fout("lupu.out");
    fin>>n>>x>>l;
    for(int i=1;i<=n;i++) {
        fin>>v[i].s>>v[i].f;
        v[i].s=(x-v[i].s)/l+1;
        tmx=max(tmx,v[i].s);
    }
    parent=new int[tmx+5];
    for(int i=1;i<=tmx;i++)
        parent[i]=i;
    sort(v+1,v+n+1);
    int ans=0;
    for(int i=n;i>=1;i--)
        if(check(v[i].s))
            ans+=v[i].f;
    fout<<ans<<'\n';
    return 0;
}