Cod sursa(job #1723319)

Utilizator dani_mocanuDani Mocanu dani_mocanu Data 30 iunie 2016 13:30:38
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int nmax = 100005;
int n,dp[nmax];
struct manelica
{
    int st,dr;
};
manelica F[nmax];

inline bool CMP(const manelica A, const manelica B)
{
    if(A.dr == B.dr) return A.st < B.st;
    return A.dr < B.dr;
}

inline int Bsearch(int p)
{
    int st, dr, m , x, sol = 0;
    st = 1, dr = p-1, x = F[p].st;
    while(st <= dr)
    {
        m = (st + dr) >> 1;
        if(F[m].dr <= x)
        {
            sol = m;
            st = m+1;
        }
        else dr = m-1;
    }
    return sol;
}

int main()
{
    int i,p;
    fin >> n;
    for(i = 1; i <= n; i++)
        fin >> F[i].st >> F[i].dr;
    sort(F+1,F+n+1,CMP);
    for(i = 1;i <= n; i++)
    {
        dp[i] = dp[i-1];
        p = Bsearch(i);
        dp[i] = max(dp[i],dp[p] + (F[i].dr - F[i].st));
    }
    fout << dp[n] << "\n";
    fout.close();
    return 0;
}