Cod sursa(job #808512)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 6 noiembrie 2012 20:40:30
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <algorithm>

#define MAX 100005

using namespace std;

struct spectacol
{
    int s, e;
} v[MAX];

int n;
long long dp[MAX];

bool cmp(spectacol a, spectacol b) {return a.e < b.e;}

long long src(int val, int r)
{
    int l = 1, m;
    long long ans = 0;
    while(l <= r)
    {
        m = (l + r) >> 1;
        if(v[m].e <= val)
        {
            ans = max(ans, dp[m]);
            l = m + 1;
        }
        else
            r = m - 1;
    }
    return ans;
}

int main()
{
    ifstream in("heavymetal.in");
    in>>n;
    for(int i = 1; i <= n; i++) in>>v[i].s>>v[i].e;
    in.close(); sort(v + 1, v + n + 1, cmp);
    for(int i = 1; i <= n; i++)
        dp[i] = max(dp[i - 1], src(v[i].s, i - 1) + v[i].e - v[i].s);
    ofstream out("heavymetal.out"); out<<dp[n]; out.close();
    return 0;
}