Cod sursa(job #2780664)

Utilizator CatalinPangaleanuCatalin Pangaleanu CatalinPangaleanu Data 7 octombrie 2021 16:29:52
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>

#pragma GCC optimize("Ofast")

using namespace std;

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

struct sheep
{
    int layer, wool;
    sheep(int layer, int wool) { this->layer = layer, this->wool = wool; }
};

vector<sheep> v;
multiset<int> ans;

int main()
{
    int n, x, l, i, d, a, layer;
    long long sol;
    fin >> n >> x >> l;
    v.reserve(n);
    for (i = 0; i < n; ++i)
    {
        fin >> d >> a;
        layer = (x - d) / l + 1;
        if (layer > 0)
            v.emplace_back(layer, a);
    }
    fin.close();
    sort(v.begin(), v.end(), [](const sheep& a, const sheep& b) { return a.layer < b.layer; });
    for (i = 0; i < v.size(); ++i)
        if (ans.empty())
            ans.insert(v[i].wool);
        else
        {
            if (ans.size() == v[i].layer)
            {
                if (v[i].wool > *ans.begin())
                {
                    ans.erase(ans.begin());
                    ans.insert(v[i].wool);
                }
            }
            else
                ans.insert(v[i].wool);
        }
    sol = 0;
    for (auto wool : ans)
        sol += wool;
    fout << sol;
    fout.close();

    return 0;
}