Cod sursa(job #2145250)

Utilizator alexradu04Radu Alexandru alexradu04 Data 27 februarie 2018 11:00:59
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
/// d[i]= perioada maxima de concertare de la 1 la i.
#include <cstdio>
#include <algorithm>
#define NMAX 100002

using namespace std;
int dp[NMAX];
pair<int,int> v[NMAX];
int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int n,cc,st,dr,mid;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&v[i].second,&v[i].first);
    sort(v+1,v+n+1);
    dp[1]=v[1].first-v[1].second;
    for(int i=2;i<=n;i++)
    {
        cc=v[i].second;
        st=1;dr=i-1;
        while(st<=dr)
        {
            mid=(st+dr)/2;
            if(v[mid].first<=cc)
                st=mid+1;
            else
                dr=mid-1;
        }
        dp[i]=max(v[i].first-v[i].second+dp[dr],dp[i-1]);
    }
    printf("%d",dp[n]);
    return 0;
}