Cod sursa(job #2518369)

Utilizator marian013Giugioiu Marian Constantin marian013 Data 5 ianuarie 2020 16:47:12
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct in{
    int x,y;
} v[100005];
bool cmp(in a,in b){
    return a.y < b.y;
}
int n,dp[100005];
int main()
{
    f>>n;
    for(int i=1;i<=n;i++) f>>v[i].x>>v[i].y;
    sort(v+1,v+1+n,cmp);
    dp[1]=v[1].y-v[1].x;
    for(int i=2;i<=n;i++)
    {
        dp[i]=dp[i-1];
        int d=v[i].y-v[i].x;
        int st=1,dr=i,M=0;
        while(st<=dr)
        {
            int m=(st+dr)/2;
            if(v[m].y<=v[i].x)
            {
                st=m+1;
                M=max(M,m);
            }
            else dr=m-1;
        }
        dp[i]=max(dp[i],dp[M]+d);
    }
    g<<dp[n];
}