Cod sursa(job #1013425)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 20 octombrie 2013 21:41:25
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct Participant{
int A;
int B;
} Array[100005];
int N,DP[100005];
bool compare(Participant a,Participant b)
{
    return a.B<b.B;
}
void Read()
{
    int i;
    f>>N;
    for(i=1;i<=N;i++)
        f>>Array[i].A>>Array[i].B;
    sort(Array+1,Array+N+1,compare);
}
int Binary_Search(int val,int poz)
{
    int st=1,dr=poz,mid,sol=0;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(Array[mid].B<=val)
            sol=mid,st=mid+1;
        else
            dr=mid-1;
    }
    return sol;
}
void Browse()
{
    int i;
    DP[1]=Array[1].B-Array[1].A;
    for(i=2;i<=N;i++)
        DP[i]=max(DP[i-1],DP[Binary_Search(Array[i].A,i-1)]+Array[i].B-Array[i].A);
    g<<DP[N]<<"\n";
}
int main()
{
    Read();
    Browse();
    return 0;
}