Cod sursa(job #1006040)

Utilizator poptibiPop Tiberiu poptibi Data 6 octombrie 2013 10:24:56
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

const int NMAX = 100010;

int N, Best[NMAX], Max[NMAX];
pair<int, int> V[NMAX];

int main()
{
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);

    scanf("%i", &N);
    for(int i = 1; i <= N; ++ i)
        scanf("%i %i", &V[i].second, &V[i].first);
    V[0] = make_pair(0, 0);

    sort(V, V + N + 1);

    for(int i = 1; i <= N; ++ i)
    {
        int Left = 0, Right = i - 1, Mid, Pos;
        while(Left <= Right)
        {
            Mid = (Left + Right) / 2;
            if(V[Mid].first <= V[i].second) Pos = Mid, Left = Mid + 1;
            else Right = Mid - 1;
        }

        Best[i] = Max[Pos] + V[i].first - V[i].second;
        Max[i] = max(Max[i - 1], Best[i]);
    }

    printf("%i\n", Max[N]);

    return 0;
}