Cod sursa(job #2106290)

Utilizator dianamichesaRosu Diana Michesa dianamichesa Data 15 ianuarie 2018 16:10:24
Problema Heavy metal Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 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 x)
{
    int 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].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 st=cautare(v[i].first);
        int dr=cautare(v[i].second);
        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;
}