Cod sursa(job #1875623)

Utilizator raluca1234Tudor Raluca raluca1234 Data 11 februarie 2017 13:16:06
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <algorithm>

#define maxN 100000

using namespace std;

struct interval{
    int st, dr;
}v[maxN+1];
int best[maxN+1];

bool cmp(interval A, interval B){
    if (A.dr==B.dr)
        return A.st<B.st;
    return A.dr<B.dr;
}

inline int maxim(int A, int B){ return (A>B ? A:B);}

int binarySearch(int l, int r, int val){
    int mid, pos=r;
    while (l<=r){
        mid=(l+r)/2;
        if (v[mid].dr<=val){
            pos=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    return pos;
}


int main(){
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);
    int N, i, pos;
    scanf("%d", &N);
    for (i=1; i<=N; i++)
        scanf("%d%d", &v[i].st, &v[i].dr);
    sort(v+1, v+N+1, cmp);
    for (i=1; i<=N; i++){
        pos=binarySearch(1, i, v[i].st);
        best[i]=maxim(best[i-1], best[pos]+v[i].dr-v[i].st);
    }
    printf("%d\n", best[N]);
    return 0;
}