Cod sursa(job #2677467)

Utilizator cezarinfoTulceanu Cezar cezarinfo Data 26 noiembrie 2020 17:12:40
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<cstdio>
#include<queue>
#include<map>
#include<algorithm>
#include<iterator>
using namespace std;
FILE*in=fopen("lupu.in","r");
FILE*out=fopen("lupu.out","w");
int n,x,l,i,d,a,v[100004],k,maxx=0,siz;
long long s=0;
map<int,priority_queue<int,vector<int>,greater<int> > > m;
map<int,priority_queue<int,vector<int>,greater<int> > > ::iterator itr;
priority_queue<int,vector<int>,greater<int> > pq;
int main()
{
    fscanf(in,"%d%d%d",&n,&x,&l);
    for(i=1;i<=n;i++)
    {
        fscanf(in,"%d%d",&d,&a);
        if(d<=x)
        {
            k=(x-d)/l+1;
        }
        else
        {
            k=0;
        }
        m[k].push(a);
        if(m[k].size()>k)
        {
            m[k].pop();
        }
    }
    for(itr=m.begin();itr!=m.end();itr++)
    {
        k=itr->first;
        siz=m[k].size();
        maxx=min(maxx+siz,k);
        while(!m[k].empty())
        {
            pq.push(m[k].top());
            m[k].pop();
        }
        while(pq.size()>maxx)
        {
            pq.pop();
        }
    }
    for(i=1;i<=maxx;i++)
    {
        s=s+pq.top();
        pq.pop();
    }
    fprintf(out,"%lld",s);
}