Cod sursa(job #1818833)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 29 noiembrie 2016 21:18:03
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin ("lupu.in");
ofstream fout("lupu.out");
pair<int, int> v[100010];
int i,l,x,n,ok,aux,a,maxi,j, h[100010],k;
long long sum;

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

void add(int i)
{
    while(h[i]>h[i/2]&&i/2>0)
    {
        swap(h[i], h[i/2]);
        i/=2;
    }
}

void verificare(int n)
{
    int c, p;
    p=1;c=2;
    while(c<=n)
    {
        if(h[c+1]>h[c]&&c+1<=n)
            c++;
        if(h[p]<h[c])
            swap(h[p], h[c]);
        else
            break;
        p=c;
        c=c*2;
    }
}

int main ()
{
    fin>>n>>x>>l;
    for(i=1;i<=n;i++)
    {
        fin>>a>>v[i].first;
        aux=(x-v[i].first)/l;ok=0;
        ok=aux%l;
        v[i].second=ok;
        if(maxi<ok)
            maxi=ok;
    }
    for(i=maxi;i>=1;i--)
    {
        for(j=1;j<=n;j++)
            if(v[j].second==i)
            {
                k++;
                h[k]=v[j].first;
                add(k);
            }
        sum+=h[1];
        swap(h[1], h[k]);
        h[k]=0;
        k--;
        verificare(k);
    }
    fout<<sum;
    fin.close();
    fout.close();
    return 0;
}