Cod sursa(job #1323274)

Utilizator laurionLaurentiu Ion laurion Data 20 ianuarie 2015 21:46:58
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 0.82 kb
#include <fstream>
#include <algorithm>
using namespace std;

typedef long long int lli;
struct DA{lli d,a;};

int const maxn=100*1000;
DA A[maxn];int H[maxn];

bool cmp1(DA const &x,DA const &y){return x.d>y.d;}
bool cmp2(int x,int y){return A[x].a>A[y].a;}

int main()
{   ifstream is("lupu.in");
    ofstream os("lupu.out");
    lli N,X,L,i,m,s;is>>N>>X>>L;
    for(i=0;N>i;++i){is>>A[i].d>>A[i].a;}
    make_heap(A,A+N,cmp1);
    sort_heap(A,A+N,cmp1);
    i=0;while((i<N)&&(A[i].d>X)){++i;}
    m=0;
    while(i<N)
    {   if(A[i].d+m*L<=X)
        {H[m]=i;++m;push_heap(H,H+m,cmp2);}
        else
        {   if(A[H[0]].a<A[i].a)
            {   pop_heap(H,H+m,cmp2);
                H[m-1]=i;push_heap(H,H+m,cmp2);
            }
        }
        ++i;
    }
    s=0;
    for(i=0;m>i;++i){s+=A[H[i]].a;}
    os<<s<<endl;
    return 0;
}