Cod sursa(job #1880183)

Utilizator cipri321Marin Ciprian cipri321 Data 15 februarie 2017 16:41:01
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fi("heavymetal.in");
ofstream fo("heavymetal.out");
pair<int,int> S[100001];
int i,n;
int st,dr,mid;
long long D[100001];
int main()
{
    fi>>n;
    for(i=1;i<=n;i++)
        fi>>S[i].first>>S[i].second;
    sort(S+1,S+n+1);
    for(i=1;i<=n;i++)
    {
        st=0,dr=i-1;
        while(st<dr)
        {
            mid=(st+dr+1)/2;
            if(S[mid].second>S[i].first)
                dr=mid-1;
            else
                st=mid;
        }
        D[i]=max(D[i-1],D[st]+S[i].second-S[i].first);
    }
    fo<<D[n];
    fi.close();
    fo.close();
    return 0;
}