Cod sursa(job #2818458)

Utilizator proflaurianPanaete Adrian proflaurian Data 16 decembrie 2021 06:00:56
Problema Gutui Scor 100
Compilator cpp-64 Status done
Runda teme_upb Marime 1.84 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("gutui.in");
ofstream g("gutui.out");
const int N = 100010;
int n,hMaxim,hInitial,crestere,greutate,gutuiMax,gutuiPuse;
int64_t sol;
vector<int> greutati[N];
priority_queue<int> candidati;
int main()
{
    int hMaxim,crestere;
    f>>n>>hMaxim>>crestere;
    for(int i=1;i<=n;i++)
    {
        int hInitial,greutate;
        f>>hInitial>>greutate;
        if(hInitial<=hMaxim)
        {
            /// Care este numarul maxim de gutui <gutuiMax> pe care le pot culege inainte sa culeg aceasta gutuie?
            /// hInitial+gutuiMax*crestere<=hMaxim
            /// gutuiMax*crestere<=hMaxim-hInitial
            /// gutuiMax<=(hMaxim-Hinitial)/crestere;
            gutuiMax=(hMaxim-hInitial)/crestere;
            /// daca moment>=n inseamna ca si daca as pune toate gutuile tot as ajunge la aceasta gutuie
            /// deci pot sa o pun la solutie in cele din urma
            /// altfel pun gutuia la momentul minim la care poate fi adaugata
            if(gutuiMax>=n)
                sol+=greutate;
            else
                greutati[gutuiMax].push_back(greutate);
        }
    }
    for(gutuiMax=0;gutuiMax<n;gutuiMax++)
        if(greutati[gutuiMax].size())
        {
            for(auto Greutate:greutati[gutuiMax])
            {
                if(gutuiPuse<=gutuiMax)
                {
                    sol+=Greutate;
                    candidati.push(-Greutate);
                    gutuiPuse++;
                }
                else
                    if(Greutate>-candidati.top())
                {
                    sol+=candidati.top();
                    sol+=Greutate;
                    candidati.pop();
                    candidati.push(-Greutate);
                }
            }
        }
    g<<sol;
    return 0;
}