Cod sursa(job #2464817)

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

#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 < long long, long long > A[NMAX];
long long Time[NMAX];

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

priority_queue < long long > Q;

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

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

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

        if(A[i].d <= X)
            ans += 1LL * A[i].a;
    }

    g << ans << '\n';

    return;
}

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

    f >> N >> X >> L;

    if(L == 0)
    {
        SpecialCase();

        exit(0);
    }

    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
        {
            if(Last - 1 >= it + 1)
            {
                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;
}