Cod sursa(job #1934233)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 21 martie 2017 11:53:54
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
priority_queue<int> q;
pair<int, int> v[100005];
int n,m,x,i,j,t,l,a,b,lim;
long long ans;
int main()
{
    ifstream f("lupu.in");
    ofstream g("lupu.out");
    f>>n>>x>>l;
    for(lim=200001,m=0,i=1; i<=n; i++)
    {
        f>>a>>b;
        if(a<=x&&b)
        {
            if((x-a)/l>=lim)
            {
                ans=ans+b;
                lim++;
            }
            else
            {
                if((x-a)/l>=200001) a=200000;
                else a=(x-a)/l;
                m++;
                v[m]=make_pair(a,b);
            }
        }
    }
    n=m;
    sort(v+1,v+n+1);
    for(i=n, t=v[n].first; t>=0; t--)
    {
        for(; i>=1&&v[i].first==t; i--)
            q.push(v[i].second);
        if(!q.empty())
        {
            ans=ans+q.top();
            q.pop();
        }
    }
    g<<ans<<'\n';
    f.close(); g.close();
    return 0;
}