Cod sursa(job #1674465)

Utilizator tiberiu225Iancu Tiberiu tiberiu225 Data 4 aprilie 2016 17:49:07
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct luca{
    int x, y;
}v[100005];
bool cmp(luca a, luca b){
    return a.y < b.y;
}
int dp[100005];
int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int n; scanf("%d",&n);
    for(int i = 1; i <= n; ++i){
        int x, y; cin >> x >> y;
        v[i].x = x;
        v[i].y = y;
    }
    sort(v + 1, v + n + 1, cmp);
    for(int i = 1; i <= n; ++i){
        dp[i] = dp[i - 1];
        int st = 1;
        int dr = i - 1;
        while(st <= dr){
            int mid = (st + dr) / 2;
            if(v[mid].y > v[i].x) dr = mid - 1;
            else st = mid + 1;
        }
        if(dp[dr] + v[i].y - v[i].x > dp[i])
            dp[i] = dp[dr] + v[i].y - v[i].x;
    }
    printf("%d",dp[n]);
    return 0;
}