Cod sursa(job #2764898)

Utilizator MateiCatalinUrsache Matei MateiCatalin Data 23 iulie 2021 11:57:24
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <algorithm>

using namespace std;
struct formatie{int st,dr;};
ifstream fi("heavymetal.in");
ofstream fo("heavymetal.out");
int n;
formatie F[100001];
int OPT[100001];

int cmp(formatie a, formatie b)
{
    if (a.dr<b.dr)
        return 1;
    return 0;
}

int main()
{
    fi>>n;
    for (int i=1;i<=n;i++)
        fi>>F[i].st>>F[i].dr;
    sort(F+1,F+n+1,cmp);
    F[0].st=F[0].dr=-1;
    OPT[0]=0;
    for (int i=1;i<=n;i++)
    {
        /// se calculeaza OPT[i]
        OPT[i]=OPT[i-1];
        /// se cauta binar P[i]
        int le,ri;
        le=0;
        ri=i-1;
        while (le!=ri)
        {
            int m;
            m=(le+ri+1)/2;
            if (F[i].st>=F[m].dr)
                le=m;
            else
                ri=m-1;
        }
        if (F[i].dr-F[i].st+OPT[le]>OPT[i])
            OPT[i]=F[i].dr-F[i].st+OPT[le];
    }
    fo<<OPT[n];
    fi.close();
    fo.close();
    return 0;
}