Cod sursa(job #1634087)

Utilizator adiXMGemene Adrian adiXM Data 6 martie 2016 13:18:34
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
const int NMAX=100005;
struct Pct{
    long long init,cost,poz;
};
struct cmp{
    inline bool operator ()(int x,int y)
    {
        return x<=y;
    }
};
inline bool cmp1 (const Pct A, const Pct B)
{
    return A.init>=B.init;
}
Pct a[NMAX];
bool viz[NMAX];
priority_queue <int,vector <int>,cmp > Q;
int main()
{
    int n,x,d;
    f>>n>>x>>d;
    for(int i=1;i<=n;i++)
    {
        f>>a[i].init>>a[i].cost;
        a[i].poz=i;
    }
    sort(a+1,a+n+1,cmp1);
    //for(int i=1;i<=n;i++)
        //g<<a[i].init<<" "<<a[i].cost<<"\n";
    long long sol=0;
    int cnt=0;
    bool ok=0;
    for(int i=1;i<=n;i++)
    {
        int j=i+1;
        if(j>n)
            break;
        if(a[i].init<=x && viz[a[i].init]==0 && ok==0)
        {
            Q.push(a[i].cost);
            if(a[i].init==a[j].init && viz[a[i].init]==0)
            {
                while(a[i].init==a[j].init)
                {
                    Q.push(a[j].cost);
                    j++;
                }
                i=j-1;
            }
            if(!Q.empty())
            {
                ok=1;
                sol+=Q.top();
                cnt++;
            }
            while(!Q.empty())
                Q.pop();
            viz[a[i].init]=1;
        }
        else
            if(ok==1)
            {
                if(a[i].init+1LL*cnt*d<=x && viz[a[i].init]==0)
                {
                    Q.push(a[i].cost);
                    if(a[i].init==a[j].init  && viz[a[i].init]==0)
                    {
                        //g<<i<<" "<<j<<"\n";
                        while(a[i].init==a[j].init)
                        {
                            //g<<a[j].cost<<"\n";
                            Q.push(a[j].cost);
                            j++;
                        }
                        i=j-1;
                    }
                    if(!Q.empty())
                    {
                        //g<<Q.top()<<"\n";
                        sol+=Q.top();
                        cnt++;
                    }
                    while(!Q.empty())
                        Q.pop();
                    viz[a[i].init]=1;
                }
            }

    }
    g<<sol<<"\n";
    return 0;
}