Cod sursa(job #1053157)

Utilizator andreiiiiPopa Andrei andreiiii Data 12 decembrie 2013 13:57:00
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#include <algorithm>
#define PII pair<int, int>
#define x first
#define y second

using namespace std;

const int N=100003;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

class Heap
{
    private:
        int h[N];
    public:
        int top() {return h[1];}
        bool empty() {return h[0]==0;}
        void upheap(int k)
        {
            int f;
            while(k>1)
            {
                f=k>>1;
                if(h[k]>h[f])
                {
                    swap(h[k], h[f]);
                    k=f;
                }
                else break;
            }
        }
        void downheap(int k)
        {
            int f;
            while(k<=h[0])
            {
                f=k<<1;
                if(f<=h[0])
                {
                    if(f+1<=h[0]&&h[f+1]>h[f]) f++;
                    if(h[f]>h[k])
                    {
                        swap(h[f], h[k]);
                        k=f;
                    }
                    else break;
                }
                else break;
            }
        }
        void push(int n)
        {
            h[++h[0]]=n;
            upheap(h[0]);
        }
        void pop()
        {
            h[1]=h[h[0]--];
            downheap(1);
        }
};

PII a[N];
Heap h;

int main()
{
    int n, t, x, i;
    long long sol=0;
    fin>>n>>x>>t;
    for(i=1;i<=n;i++)
    {
        fin>>a[i].x>>a[i].y;
        a[i].x=(x-a[i].x)/t;
    }
    sort(a+1, a+n+1);
    for(i=n, t=a[n].x;t>=0;t--)
    {
        for(;i&&a[i].x==t;i--) h.push(a[i].y);
        if(!h.empty())
        {
            sol+=h.top();
            h.pop();
        }
    }
    fout<<sol;
}