Cod sursa(job #2378772)

Utilizator vladstanciuVlad Stanciu vladstanciu Data 12 martie 2019 16:50:36
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream in("heavymetal.in");
ofstream out("heavymetal.out");

const int N=100004;

struct interval
{
    int in,sf;
}v[N];

bool cmp(interval a , interval b)
{
    return a.sf < b.sf;
}

int cautbin(int a)
{
    int st,dr,max1=0,x;
    st=1;
    dr=v[a].in;
    while(st<dr)
    {
        x=(st+dr)/2;
        if(v[x].sf<=v[a].in)
        {
            if(x>max1)
            {
                max1=x;
            }
            st=x;
        }
        else
        {
            dr=x;
        }
    }
    return max1;
}

int d[N];

int main()
{
    int n,i,x;
    in>>n;
    for(i=1 ; i<=n ; i++)
    {
        in>>v[i].in>>v[i].sf;
    }
    sort(v+1,v+n+1,cmp);
    d[1]=v[1].sf-v[1].in;
    for(i=2 ; i<=n ; i++)
    {
        x=cautbin(i);
        d[i]=max(d[i-1],d[x]+v[i].sf-v[i].in);
    }
    out<<d[n];
    return 0;
}