Cod sursa(job #2049850)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 27 octombrie 2017 18:33:58
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int dp[100001];
struct str{
    int x,y;
}c[100001];
int st, dr, mid,n;
bool cmp ( str s1, str s2) {
    if (s1.y < s2.y)
        return 1;
    if (s1.y > s2.y)
        return 0;
    return s1.x < s2.x;
}
int main(void){
    in >> n;
    for (int i = 1; i <= n; i ++) {
        in >> c[i].x >> c[i].y;
    }
    sort (c + 1, c + n + 1, cmp);
    for (int i = 1; i <= n; i ++) {
        for ( st = 1, dr = i; st <= dr; ) {
            mid = (st + dr) >> 1;
            if (c[mid].y >= c[i].x) {
                st = mid  + 1;
            }
            else{
                dr = mid - 1;
            }
        }
        dp[i] = max (dp[i-1], dp[st] + (c[i].y-c[i].x+1));
    }
    out << dp[n];
}