Cod sursa(job #486685)

Utilizator andra23Laura Draghici andra23 Data 22 septembrie 2010 14:12:23
Problema Lupul Urias si Rau Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<fstream>
#define nmax 100005

using namespace std;

struct elem{
    int d, c;
    elem() {}
    elem(int a1, int b1){
        d = a1;
        c = b1;
    }
};

elem v[nmax];
int t[nmax];

int cmp(elem a, elem b){
    return (a.c > b.c) || (a.c == b.c && a.d > b.d);    
}

int find(int x){
    int rad = x, y;
    while (rad != t[rad])
        rad = t[rad];
    while (x != t[x]){
        y = t[x];
        t[x] = rad;
        x = y;    
    } 
    return rad;   
}

int main(){
    ifstream f("lupu.in");
    ofstream g("lupu.out");
    int n, x, l;
    f>>n>>x>>l;
    long long rez = 0;
    int i, j, k, d, c, y;
    elem o;
    for (i = 1; i <= n; i++){
        f>>d>>c;
        v[i] = elem(d, c);
    }
    
    sort(v+1, v+n+1, cmp);
    for (i = 1; i <= n; i++){
        o = v[i];
        if (o.d <= x){
            y = (x-o.d)/l+1;
            if (t[y] == 0)
                t[y] = y;
            else {
                y = find(y);
                y--;
            }
            if (y != 0){
                rez = rez + o.c;
                if (t[y-1] != 0)
                    t[y] = find(y-1); 
                if (t[y+1] != 0)
                    t[y+1] = t[y];
            }
        }      
    }
    
    g<<rez<<'\n';
    
    return 0;
}