Cod sursa(job #1810653)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 20 noiembrie 2016 13:48:24
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <fstream>
#include <algorithm>
#define DIM 100001
#define f first
#define s second
using namespace std;
long long n,x,l,maxi,i,j,k,c,p,sol,nr;
pair <int,int> v[DIM], heap[DIM];
ifstream fin ("lupu.in");
ofstream fout ("lupu.out");
int cmp (pair<int,int> a, pair<int,int> b){
    return a.f>b.f;
}
int main (){

    fin>>n>>x>>l;
    for (i=1;i<=n;i++){
        fin>>v[i].f>>v[i].s;
        if (v[i].f <= x){
            v[i].f = (x-v[i].f)/l;
            if (v[i].f > maxi)
                maxi = v[i].f;

        }
        else
            v[i].f = -1000000;

    }
    sort (v+1,v+n+1,cmp); // in ind am puse pozitiile nr din t in ordine crescatoare
    i = 0;
    k = 0;
    for (j=maxi;j>=0;j--){
        while (v[i+1].f == j){
            i++;
            heap[++k] = v[i];
            c = k;
            p = k/2;
            while (p!=0){
                if (heap[p].s < heap[c].s){
                    swap (heap[p],heap[c]);
                    c = p;
                    p = c/2;
                }
                else
                    break;
            }
        }
        if (k!= 0){
            sol += heap[1].s;
            // eliminam din heap pe max, adica heap[1];
            heap[1] = heap[k];
            //heap[1].f = heap[k].f;
            //heap[1].s = heap[k].s;
            k--;
            p = 1; c = 2;
            while (c <= k){
                if (c+1 <= k && heap[c+1].s > heap[c].s)
                    c++;
                if (heap[p].s < heap[c].s){
                    swap (heap[p],heap[c]);
                    p = c;
                    c = p*2;
                }
                else
                    break;
            }
        }

    }
    fout<<sol;




    return 0;
}