Cod sursa(job #1818077)

Utilizator Liviu_Ionut_MoantaMoanta Ionut Liviu Liviu_Ionut_Moanta Data 28 noiembrie 2016 20:08:39
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int cmp(pair<int,int>t,pair<int,int>u){
    return t.first>u.first;
}
int n,x,l,maxim,i,j,c,p,t,aux,sol;
pair<int,int>v[100005];
pair<int,int>w[100005];
int main(){
    fin>>n>>x>>l;
    sol=0;
    for(i=1;i<=n;i++){
        fin>>v[i].first>>v[i].second;
        v[i].first=(x-v[i].first)/l;
        if(v[i].first<=x){
            if(v[i].first>maxim){
                maxim=v[i].first;
            }
        }
    }
    sort(v+1,v+n+1,cmp);
    j=0;
    t=0;
    for(i=maxim;i>=0;i--){
        while(v[j+1].first==i){
            j++;
            w[++t]=v[j];
            c=t;
            p=t/2;
            while(p!=0){
                if(w[p].second<w[c].second){
                    aux=w[p].first;
                    w[p].first=w[c].first;
                    w[c].first=aux;
                    aux=w[p].second;
                    w[p].second=w[c].second;
                    w[c].second=aux;
                    c=p;
                    p=c/2;
                }
                else{
                    break;
                }
            }
        }
        if(t!=0){
            sol+=w[1].second;
            w[1]=w[t];
            t--;
            p=1;
            c=2;
            while(c<=t){
                if(c+1<=t&&w[c+1].second>w[c].second){
                    c++;
                }
                if(w[p].second<w[c].second){
                    aux=w[p].first;
                    w[p].first=w[c].first;
                    w[c].first=aux;
                    aux=w[p].second;
                    w[p].second=w[c].second;
                    w[c].second=aux;
                    p=c;
                    c=p*2;
                }
                else{
                    break;
                }
            }
        }
    }
    fout<<sol;
    return 0;
}