Cod sursa(job #1321711)

Utilizator leontinLeontin leontin Data 19 ianuarie 2015 14:37:47
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 1.04 kb
#include <fstream>
#include <algorithm>
#define dim 100003
#define x first
#define y second
using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");
pair <long long,long long> v[dim];
long long h[dim],N,i,j,X,L,a[dim],pp,nr,sol;
void insert(int x)
{
    a[++nr]=x;
    int c=nr,p=nr/2;
    while(p>=1 && a[p]<a[c])
    {
        swap(a[c],a[p]);
        c=p;
        p/=2;
    }
}
void down()
{
    a[1]=a[nr--];
    int p=1,c=2;
    while(c<=nr)
    {
        if(c+1<=nr && a[c+1]>a[c])
            c++;
        if(a[p]<a[c])
        {
            swap(a[c],a[p]);
            p=c;
            c*=2;
        }
        else
            break;
    }
}
int main()
{

    fin>>N>>X>>L;
    for(i=1; i<=N; i++)
        fin>>v[i].x>>v[i].y;
    sort(v+1,v+N+1);
    for(i=1; i<=N && v[i].x<=X; pp++)
    {
        while(i<=N && v[i].x<=pp*L)
            insert(v[i].y),i++;
        if(nr)
            sol+=a[1],down();
    }
    fout<<sol;
    fin.close();
    fout.close();
    return 0;
}