Cod sursa(job #1939757)

Utilizator edi_laitinLaitin Eduard edi_laitin Data 25 martie 2017 23:33:45
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int N,DP[100005],st,dr,mid,i,poz;

struct spectacol
{
    int in,sf;
};

spectacol a[100005];

int Compare(spectacol a, spectacol b)
{
    return a.sf<b.sf;
}

void Read()
{
    fin>>N;
    for(i=1;i<=N;i++)
    {
        fin>>a[i].in>>a[i].sf;
    }
    sort(a+1,a+N+1,Compare);
}

void Solve()
{
    for(i=1;i<=N;i++)
    {
        st=1;dr=i-1;
        poz=0;
        while(st<=dr)
        {
            mid=(st+dr)/2;
            if(a[mid].sf<=a[i].in)
            {
                poz=mid;
                st=mid+1;
            }
            else
            {
                dr=mid-1;
            }
        }
        DP[i]=max(DP[i-1],DP[poz]+a[i].sf-a[i].in);
    }
}

int main()
{

   Read();
   Solve();
   fout<<DP[N]<<"\n";
    return 0;
}