Cod sursa(job #2106262)

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