Cod sursa(job #2694263)

Utilizator tomaionutIDorando tomaionut Data 8 ianuarie 2021 16:49:24
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct vrajeala
{
    int x,y;
}a[100005];
int n,dp[100005],ma;
bool cmp(vrajeala o, vrajeala p)
{
    if (o.x==p.x)
        return o.y<p.y;
    return o.x<p.x;
}
int main()
{
    int i,j,st,dr,sol,mij;
    fin >> n;
    for (i=1; i<=n; i++)
        fin >> a[i].x >> a[i].y;
    sort(a+1, a+n+1, cmp);
    for (i=1; i<=n; i++)
    {
        st=1;
        dr=i-1;
        sol=0;
        while (st<=dr)
        {
            mij=(st+dr)/2;
            if (a[mij].y<=a[i].x)
            {
                sol=mij;
                st=mij+1;
            }
            else dr=mij-1;
        }
        dp[i]=max(dp[i-1],dp[sol]+a[i].y-a[i].x);
    }
    for (i=1; i<=n; i++)
        ma=max(ma,dp[i]);
    fout << ma;
    return 0;
}