Cod sursa(job #2121650)

Utilizator FredyLup Lucia Fredy Data 3 februarie 2018 23:37:42
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <algorithm>
#include <fstream>

using namespace std;

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

#define lim 100010
int n, pos;
struct formatie {int st,dr;} ini[lim];
int rez, dp[lim];   /// dp[i] = suma max obtinuta daca ultimul concert are capatul <= ini[i].dr

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


/// cea mai mare p<=x care are ini[p].dr <= ini[x].st
int b_s (int x)
{
    int mask=0, p;
    for (mask=1; mask<=x; mask<<=1);
    for (p=0; mask>0; mask>>=1)
        if (p+mask <= x)
            if (ini[p+mask].dr <= ini[x].st)  p+=mask;
    return p;
}

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++)
    {
        pos = b_s (i);
        dp[i] = max (dp[i-1], dp[pos]+ini[i].dr-ini[i].st);
        rez = max (rez, dp[i]);
    }
    fout<<rez;

    fout.close();
    return 0;
}