Cod sursa(job #2541132)

Utilizator CleliaClelia Maria Dobrescu Clelia Data 8 februarie 2020 10:05:47
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
struct ura
{
    int a,b;
};
ura v[100001];
int dp[100001];
bool cmp(ura x,ura y)
{
    if (x.b>y.b)
        return false;
    else
        return true;
}
int main ()
{
    int n,i,l1,l2,poz,m;
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i].a>>v[i].b;
    sort (v+1,v+n+1,cmp);
    for (i=1;i<=n;i++)
    {
        l1=1;
        l2=i-1;
        poz=0;
        while (l1<=l2)
        {
            m=(l1+l2)/2;
            if (v[m].b<=v[i].a)
            {
                poz=m;
                l1=m+1;
            }
            else
                l2=m-1;
        }
        if (dp[i-1]>dp[poz]+v[i].b-v[i].a)
            dp[i]=dp[i-1];
        else
            dp[i]=dp[poz]+v[i].b-v[i].a;
    }
    fout<<dp[n];
    return 0;
}