Cod sursa(job #2498021)

Utilizator andreighinea1Ghinea Andrei-Robert andreighinea1 Data 23 noiembrie 2019 13:36:30
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define Nmax 100001

using namespace std;

ifstream f("heavymetal.in");
ofstream o("heavymetal.out");

struct form{
    int a,b;
}fo[Nmax];

bool cmp(form &f1,form &f2){
    return f1.b < f2.b;
}

int i,j,n,dp[Nmax],d,v;

int bin(int v,int n){
    int s=1,d=n,g=0,m;

    while(s<=d){
        m=(s+d)>>1;
        if(fo[m].b<=v){
            s=m+1;
            g=max(g,m);
        }
        else
            d=m-1;
    }

    return g;
}

int main()
{
    f >> n;
    for(i=1;i<=n;++i)
        f >> fo[i].a >> fo[i].b;
    sort(fo+1,fo+n+1,cmp);

    dp[1]=fo[1].b-fo[1].a;
    for(i=2;i<=n;++i){
        v=fo[i].a;
        d=fo[i].b-v;
        dp[i]=dp[i-1];
        dp[i]=max(dp[i],dp[bin(v,i-1)]+d);
    }
    o << dp[n];

    return 0;
}