Cod sursa(job #1675187)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 5 aprilie 2016 10:01:19
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
const int MAX  = 100002;
struct cell{
    int st, dr;
}v[MAX];
int n, dp[MAX];
bool cmp( cell a, cell b ){ return a.dr<b.dr; }
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
        cin >> v[i].st >> v[i].dr;
    sort(v+1, v+n+1, cmp);
    for(int i=1;i<=n;i++)
    {
        int st = 1;
        int dr = i - 1;
        while(st<=dr){
            int mij = (st+dr)/2;
            if(v[mij].dr<=v[i].st)
                st = mij + 1;
            else
                dr = mij - 1;
        }
        dp[i] = max( dp[i-1], dp[dr] + (v[i].dr-v[i].st) );
    }
    cout << dp[n];
    return 0;
}