Cod sursa(job #2970561)

Utilizator user12345user user user user12345 Data 25 ianuarie 2023 15:53:27
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

int n, bound, stage;
pair <int, int> v[100001];
int maxi[100001], poz[100001];
bitset <100001> used;

int main()
{
    fin >> n >> bound >> stage;

    for (int i = 1; i <= n; i++)
        fin >> v[i].first >> v[i].second;

    sort(v + 1, v + n + 1);

    maxi[0] = -1;
    for (int i = 1; i <= n; i++)
        if (v[i].first > maxi[i - 1])
            maxi[i] = v[i].first, poz[i] = i;
        else
            maxi[i] = maxi[i - 1], poz[i] = poz[i - 1];

    int k = n;

    while (k && v[k].first > bound)
        k--;

    long long total = 0;

    while (bound >= 0)
    {
        int maxVal = -1;

        while (k && v[k].first > bound - stage)
        {
            if (used[k])
            {
                k--;
                continue;
            }

            maxVal = max(maxVal, v[k--].second);
        }

        bound -= stage;

        if (maxVal != -1)
            total += maxVal;
        else
        {
            used[poz[bound]] = true;
            total += maxi[bound];
        }
    }

    fout << total;

    return 0;
}