Cod sursa(job #2464813)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 28 septembrie 2019 22:53:54
Problema Lupul Urias si Rau Scor 88
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>

#define d first
#define a second

using namespace std;

ifstream f("lupu.in");
ofstream g("lupu.out");

const int NMAX = 1e5 + 5;

int N, X, L;

long long ans = 0;

pair < int, int > A[NMAX];
int Time[NMAX];

map < int, vector < int > > mp;
vector < int > Keys;

priority_queue < int > Q;

static inline int Max_Moment (int Val)
{
    if(Val > X)
        return 0;

    return (X - Val) / L + 1;
}

static inline void Read ()
{
    f.tie(NULL);

    f >> N >> X >> L;

    for(int i = 1; i <= N; ++i)
    {
        f >> A[i].d >> A[i].a;

        Time[i] = Max_Moment(A[i].d);

        if(Time[i] == 0)
            continue;

        mp[Time[i]].push_back(A[i].a);
    }

    return;
}

static inline bool cmp (int a, int b)
{
    return (a > b);
}

int main()
{
    Read();

    int Last = 0, i = 0;

    for(auto it : mp)
        Keys.push_back(it.first);

    sort(Keys.begin(), Keys.end(), cmp);

    for(auto it : Keys)
    {
        for(auto j : mp[it])
            Q.push(j);

        ans += 1LL * Q.top();
        Q.pop();
        --N;

        if(N == 0)
            break;

        if(i == 0)
            Last = it;
        else
        {
            for(int i = Last - 1; i >= it + 1 && N; --i)
            {
                ans += 1LL * Q.top();
                Q.pop();

                --N;
            }

            Last = it;
        }

        ++i;

        if(N == 0)
            break;
    }

    g << ans << '\n';

    return 0;
}