Cod sursa(job #2030969)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 2 octombrie 2017 16:04:39
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int x, n, l, i,j,t,maxi,c,p;
long long sol;
pair <int, int> v[100002], w[100002];


int cnp(pair<int, int> t, pair<int, int> u)
{
    return t.first>u.first;
}

void swap(int &a, int &b)
{
    int r;
    r=a;
    a=b;
    b=r;
}

int main(){
    fin>>n>>x>>l;
    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>maxi)
                maxi=v[i].first;
    }
    sort(v+1, v+n+1, cnp);
    for(i=maxi;i>=0;i--)
    {
        while(v[j+1].first==i)
        {
            j++;
            w[++t]=v[j];
            c=t;
            p=t/2;
            while(p!=0)
            {
                if(w[c].second>w[p].second)
                {
                    swap(w[c].first, w[p].first);
                    swap(w[c].second, w[p].second);
                    c=p;
                    p=t/2;
                }
                else
                    break;
            }
        }
        if(t!=0)
        {
            sol+=w[1].second;
            w[1]=w[t];
            t--;
            p=1;
            c=2;
            while(c<=t)
            {
                if(w[c+1].second>w[c].second&&c+1<=t)
                    c++;
                if(w[p].second<w[c].second)
                {
                    swap(w[c].first, w[p].first);
                    swap(w[c].second, w[p].second);
                    p=c;
                    c=p*2;
                }
                else
                    break;
            }
        }
    }
    fout<<sol;
    fin.close();
    fout.close();
    return 0;
}