Cod sursa(job #2761607)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 2 iulie 2021 21:07:21
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100003;

int n;

struct elem{
    int x,y;
}v[NMAX];
int dp[NMAX];

bool cmp(elem a,elem b){
    return a.y < b.y;
}

int cb(int val,int dr){
    int st = 1,last = 0;
    while(dr-st>=0){
        int mid = (st + dr)>>1;
        if(v[mid].y <= val ){
            st = mid + 1;
            last = mid;
        }else{
            dr = mid - 1;
        }

    }
    return last;
}

int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&v[i].x,&v[i].y);
    }
    sort(v+1,v+n+1,cmp);
    dp[1] = v[1].y - v[1].x;
    for(int i=2;i<=n;i++){
        dp[i] = max(dp[i-1], dp[cb(v[i].x,i-1)] + (v[i].y - v[i].x) );
    }
    printf("%d",dp[n] );


    return 0;
}