Cod sursa(job #2106301)

Utilizator dianamichesaRosu Diana Michesa dianamichesa Data 15 ianuarie 2018 16:21:46
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
const long long N=100001;
pair <long long,long long> v[N];
long long n,dp[N],fn[N],m;
long long cautare(long long x)
{
    long long p=1<<16,r=0;
    while(p!=0){
        if(fn[r+p]<=x && r+p<=m)
           r+=p;
        p/=2;
    }
    return r;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++){
        f>>v[i].second>>v[i].first;
        fn[i]=v[i].first;
    }
    sort(fn+1,fn+n+1);
    sort(v+1,v+n+1);
    long long j,i;
    for(i=2,j=1;i<=n;i++)
        if(fn[i]!=fn[i-1])
           fn[++j]=fn[i];
    m=j;
    for(int i=1;i<=n;i++){
        long long st=cautare(v[i].second);
        long long dr=cautare(v[i].first);
        dp[dr]=max(dp[dr],dp[st]-v[i].second+v[i].first);
        dp[dr]=max(dp[dr],dp[dr-1]);
    }
    g<<dp[m];
    return 0;
}