Cod sursa(job #2709488)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 20 februarie 2021 12:37:38
Problema Lupul Urias si Rau Scor 92
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

map<int, vector<int> > oi;
vector<int> sol;

bool heapcmp(int &a, int &b)
{
    return a>b;
}

int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);


    int n,x,l;
    long long int s=0;
    int imx=-1,imn=INT_MAX;
    scanf("%i %i %i",&n,&x,&l);
    for(int i=0;i<n;i++)
    {
        int d,v;
        scanf("%i %i",&d,&v);
        if(d<x)
        {
            oi[(x-d)/l].push_back(v);
            if(imx<(x-d)/l) imx=(x-d)/l;
            if(imn>(x-d)/l) imn=(x-d)/l;
        }
    }
    for(int i=imn;i<=imx;i++)
    {
        sort(oi[i].begin(),oi[i].end());
        int jbegin=0;
        if(oi[i].size()>i) jbegin=oi[i].size()-i-1;
        for(int j=jbegin;j<oi[i].size();j++)
            {
                if(sol.size()<=i)
                {
                    sol.push_back(oi[i][j]);
                    push_heap(sol.begin(),sol.end(),heapcmp);
                }
                else if (sol.front()<oi[i][j])
                {
                    pop_heap(sol.begin(),sol.end(),heapcmp);
                    sol.pop_back();
                    sol.push_back(oi[i][j]);
                    push_heap(sol.begin(),sol.end(),heapcmp);

                }
            }
    }
    for(int i=0;i<sol.size();i++) {s+=sol[i];}
    printf("%lli",s);
    return 0;
}