Cod sursa(job #852650)

Utilizator stoicatheoFlirk Navok stoicatheo Data 11 ianuarie 2013 15:44:16
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;
}