Cod sursa(job #2628811)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 17 iunie 2020 16:43:22
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n,i,dp[100005],m,ans;
struct trupe
{
    int s,f;
}v[100005];
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
bool comp(trupe a, trupe b)
{
    return a.f<b.f;
}
int cautbin(int val, int st, int dr)
{
    ans=0;
    while (st<=dr)
    {
        m=(st+dr)/2;
        if (v[m].f<=val)
        {
            ans=m;
            st=m+1;
        }
        else dr=m-1;
    }
    return ans;
}
int main()
{
   in>>n;
   for (i=1;i<=n;i++)
    in>>v[i].s>>v[i].f;
   sort(v+1,v+n+1,comp);
   dp[1]=v[1].f-v[1].s;
   for (i=2;i<=n;i++)
   {
       int p=cautbin(v[i].s,1,i-1);
       dp[i]=max(dp[i-1],dp[p]+v[i].f-v[i].s);
   }
   out<<dp[n];
}