Cod sursa(job #1880189)

Utilizator cipri321Marin Ciprian cipri321 Data 15 februarie 2017 16:42:35
Problema Heavy metal Scor 100
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].second>>S[i].first;
    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].first>S[i].second)
                dr=mid-1;
            else
                st=mid;
        }
        D[i]=max(D[i-1],D[st]+S[i].first-S[i].second);
    }
    fo<<D[n];
    fi.close();
    fo.close();
    return 0;
}