Cod sursa(job #1670346)

Utilizator tqmiSzasz Tamas tqmi Data 31 martie 2016 17:47:35
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 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 spec
{
    int in,sf;
};
spec a[100005];
int comp(spec a, spec b)
{
    return a.sf<b.sf;
}
int main()
{
    fin>>N;
    for(i=1;i<=N;i++)
    {
        fin>>a[i].in>>a[i].sf;
    }
    sort(a+1,a+N+1,comp);
    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);
    }
    fout<<dp[N]<<"\n";
    return 0;
}