Cod sursa(job #1695110)

Utilizator radarobertRada Robert Gabriel radarobert Data 26 aprilie 2016 16:29:41
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

pair<int, int> lamb[100100];
vector<int> level[100100];
int lv_nr[100100];
priority_queue<int> q;

bool compare(pair<int, int> a, pair<int, int> b)
{
    return a.first > b.first;
}

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

    int n, lmax, l;
    scanf("%d%d%d", &n, &lmax, &l);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &lamb[i].first, &lamb[i].second);
    sort(lamb+1, lamb+n+1, compare);

    int counter = 0;
    int nr = -2;
    long long sol = 0;
    for (int i = 1; i <= n; i++)
    {
        if (lamb[i].first > lmax)
            continue;
        int cur = ((lamb[i].first - 1) / l);
        if (lamb[i].first == 0)
            cur = -1;
        if (cur != nr)
        {
            lv_nr[++counter] = cur;
            nr = cur;
        }
        level[counter].push_back(lamb[i].second);
    }
    for (int i = 1; i <= counter; i++)
        sort(level[i].begin(), level[i].end());

    int last_lv = (lmax-1) / l;
    for (int i = 1; i <= counter; i++)
    {
        int cur = last_lv - lv_nr[i] + 1;
        while (q.size() < cur && !level[i].empty())
        {
            q.push(-level[i].back());
            sol += level[i].back();
            level[i].pop_back();
        }
        while (!level[i].empty())
            if (level[i].back() > -q.top())
            {
                sol += q.top();
                q.pop();
                q.push(-level[i].back());
                sol += level[i].back();
                level[i].pop_back();
            }
            else
                break;
    }

    cout << sol << '\n';

    return 0;
}