Cod sursa(job #2575766)

Utilizator darianegreanDaria Negrean darianegrean Data 6 martie 2020 15:20:22
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int n,dp[100005],j;
struct timp
{
    int r,l;
}v[100005];
bool comp(timp x, timp y)
{
    return (x.l<y.l or (x.l==y.l and x.r<y.r));
}
int cautbin(int st,int dr,int val)
{
    int j=0;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(v[mid].l<=val)
        {
            j=mid;st=mid+1;
        }
        else dr=mid-1;
    }
    return j;
}
int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
    {
        in>>v[i].r>>v[i].l;
    }
    sort(v+1,v+n+1,comp);
    dp[1]=v[1].l-v[1].r;
    for(int i=2;i<=n;i++)
    {
        int j=cautbin(1,i-1,v[i].r);
      dp[i]=max(dp[i-1],dp[j]+v[i].l-v[i].r);
    }
    out<<dp[n];
}