Cod sursa(job #2350753)

Utilizator vladboss2323Ciorica Vlad vladboss2323 Data 21 februarie 2019 18:05:24
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

const int N=100005;

struct spectacol
{
    int st,fin;
};

spectacol a[N];
int n,d[N];

bool cmp(spectacol A,spectacol B)
{
    if(A.fin==B.fin)
        return A.st<B.st;
    return A.fin<B.fin;
}

int cautbin(int inceput,int dr)
{
    int st=1,mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(a[mid].fin<=inceput)
        {
            st=mid+1;
        }
        else
            dr=mid-1;
    }
    return dr;
}
int main()
{
    int i,j;
    in>>n;
    for(i=1; i<=n; i++)
        in>>a[i].st>>a[i].fin;
    sort(a+1,a+n+1,cmp);
    d[1]=a[1].fin-a[1].st;
    for(i=2; i<=n; i++)
    {
        j=cautbin(a[i].st,i-1);
        //caut cel mai bun j astfel incat A[i].st>=A[j].fin
        d[i]=max(d[i-1],d[j]+a[i].fin-a[i].st);
    }
    out<<d[n];
    return 0;
}