Cod sursa(job #2818460)

Utilizator proflaurianPanaete Adrian proflaurian Data 16 decembrie 2021 07:29:10
Problema Gutui Scor 100
Compilator cpp-64 Status done
Runda teme_upb Marime 2.45 kb
/// ALTERNATE SOLUTION

#include <bits/stdc++.h>

using namespace std;
ifstream f("gutui.in");
ofstream g("gutui.out");
const int N = 100010;
int n,H,G;
struct gutuie
{
    int greutate,timp;
    gutuie()
    {
        int x,y;
        f>>x>>y;
        greutate = y;
        if(x>H)timp=-1;
        else if(x+n*G<=H)timp=N;
        else timp=(H-x)/G;
    }
};
bool crit(gutuie A,gutuie B)
{
    if(A.greutate>B.greutate)
        return true;
    if(A.greutate<B.greutate)
        return false;
    return A.timp>=B.timp;
}
vector<gutuie> GU;
set<int> timpi;
int64_t sol;
int main()
{
    f>>n>>H>>G;
    for(int i=0; i<n; i++)
    {
        timpi.insert(-i);
        gutuie gu;
        if(gu.timp==N)
            sol+=gu.greutate;
        else if(gu.timp>=0)
            GU.push_back(gu);
    }
    sort(GU.begin(),GU.end(),crit);
    for(auto it:GU)
    {
        auto IT=timpi.lower_bound(-it.timp);
        if(IT!=timpi.end())
        {
            sol+=it.greutate;
            timpi.erase(IT);
        }
    }
    g<<sol;
    return 0;
}



/// PRIMARY SOLUTION
//#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)
//        {
//            gutuiMax=(hMaxim-hInitial)/crestere;
//            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;
//}