Cod sursa(job #2046124)

Utilizator FredyLup Lucia Fredy Data 23 octombrie 2017 14:51:51
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

#define lim 100010
int n,dp[lim],rez;
struct pct{int st,dr;}  ini[lim];

bool cmp (pct A, pct B)
{
    if (A.dr < B.dr)  return 1;
    if (A.dr == B.dr)   return A.st<B.st;
    return 0;
}


int caut_bin(int x)
{
    int l=1,r=n,mid=(l+r)/2;
    while (l<=r)
    {
        mid = (l+r)/2;
        if (ini[mid].dr <= x)   l = mid+1;
        else    r = mid-1;
    }
    return r;
}


int main()
{
    fin>>n;
    for (int i=1; i<=n; i++)    fin>>ini[i].st>>ini[i].dr;
    sort (ini+1, ini+n+1, cmp);

    for (int i=1; i<=n; i++)
    {
        int aux = caut_bin(ini[i].st);
        dp[i] = max (dp[i-1], dp[aux]+ini[i].dr-ini[i].st);
        rez = max(rez, dp[i]);
    }
    fout<<rez;

    fin.close();
    fout.close();
    return 0;
}